Queue

Overview

前面学习的栈是后进先出[LIFO],与之相对的是队列的先进先出[FIFO]。这里我们通过两种方式实现Queue,分别是Array和List。在Array实现的时候要注意,实际上,整个过程都是在一维的数组上操作的,但是,为了在enqueue[插入]和dequeue[弹出]数据的时候有效地利用空间,我们将其看作一个圆环,这样,前面dequeue留下的空间,还可以共之后enqueue使用。

Code

Array实现—genArrayQueue.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

//
// Created by shensir on 17-5-10.
//

#ifndef CPPPROJECTS_GENARRAYQUEUE_H
#define CPPPROJECTS_GENARRAYQUEUE_H

#include <iostream>

template <class T, int size=100>
class ArrayQueue{

private:
int first, last;
T storage[size];
int total_num=0; // 用于计数,方便打印
public:

ArrayQueue(){
first = last = -1;
}

void enqueue(T);

T dequeue();

bool isFull(){
return first==0 && last==size-1 || first == last+1;
}

bool isEmpty(){
return first == -1;
}

void printQueue(){
// 由于dequeue只是移动首部的位置,并不是真正的删除,所以打印的时候不能直接循环打印
for (int i = first; i < total_num+first; i++) {
std::cout<<storage[i]<<" ";
}
}

};


template <class T, int size>
void ArrayQueue<T,size>::enqueue(T el) {
total_num += 1;
if(!isFull()){
if(last==size-1 || last == -1){
storage[0] = el;
last = 0;
if(first == -1)
first = 0;
}
else storage[++last] = el;
}
else std::cout<<"Full queue.\n";
}


template <class T, int size>
T ArrayQueue<T, size>::dequeue() {
total_num -= 1;
T tmp;
tmp = storage[first];
if(first == last)
last = first = -1;
else if(first == size-1)
first = 0;
else first++;
return tmp;
}


#endif //CPPPROJECTS_GENARRAYQUEUE_H


main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include "genArrayQueue.h"
#include <iostream>

using namespace std;

int main(){
ArrayQueue<int> AQ;
AQ.enqueue(2);
AQ.enqueue(3);
AQ.enqueue(4);

AQ.dequeue();

AQ.printQueue();
return 0;
}

输出:

3 4

List实现—genQueue.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

//
// Created by shensir on 17-5-11.
//

#ifndef CPPPROJECTS_GENQUEUE_H
#define CPPPROJECTS_GENQUEUE_H

#include <list>
#include <iostream>

using namespace std;

template <class T>
class Queue{

private:
list<T>lst;

public:
Queue(){};

void clear(){
lst.clear();
}

bool isEmpty()const {
return lst.empty();
}

T& front(){
return lst.front();
}

T dequeue(){
T el = lst.front();
lst.pop_front();
return el;
}

void enqueue(const T& el){
lst.push_back(el);
}


void printListQueue(){
for(typename list<T>::iterator i = lst.begin(); i != lst.end(); i++){
std::cout<<*i<<" ";
}
}
};

#endif //CPPPROJECTS_GENQUEUE_H


main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <iostream>
#include "genQueue.h"

using namespace std;


int main(){
Queue<int> AQ;
AQ.enqueue(2);
AQ.enqueue(3);
AQ.enqueue(4);

AQ.dequeue();

AQ.printListQueue();
return 0;
}

输出:

3 4

本文标题:Queue

文章作者:不秩稚童

发布时间:2017年05月11日 - 00:23:24

最后更新:2017年05月11日 - 14:12:03

原始链接:http://datahonor.com/2017/05/11/Queue/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

击蒙御寇