迴圈佇列：

1.迴圈佇列中判斷隊空的方法是判斷front==rear，隊滿的方法是判斷front=（rear+1）%maxSize。（我曾經想過為什麼不用一個length表示隊長，當length==maxSize時隊滿）原因就是，在頻繁的佇列操作中，多出一個變數會大量的增加執行時間，所以不如浪費一個數組空間來得划算。

2.用單鏈表表示的鏈式佇列特別適合於資料元素變動較大的情形，而且不存在溢位的情況。

1 template<class T>

2 class SeqQueue{

3 protected:

4 T *element;

5 int front,rear;

6 int maxSize;

7 public:

8 SeqQueue(int sz=10){

9 front=rear=0;

10 maxSize=sz;

11 element=new T[maxSize];

12 }

13 ~SeqQueue(){

14 delete[] element;

15 }

16 bool EnQueue(const T& x){//入隊

17 if(isFull()) return false;

18 element[rear]=x;

19 rear=(rear+1)%maxSize;

20 return true;

21 }

22 bool DeQueue(T& x){//出隊

23 if(isEmpty()) return false;

24 x=element[front];

25 front=(front+1)%maxSize;

26 return true;

27 }

28 bool getFront(T& x){//獲取隊首元素

29 if(isEmpty()) return false;

30 x=element[front];

31 return true;

32 }

33 void makeEmpty(){//佇列置空

34 front=rear=0;

35 }

36 bool isEmpty()const{//判斷佇列是否為空

37 return (rear==front)?true:false;

38 }

39 bool isFull()const{//佇列是否為滿

40 return ((rear+1)%maxSize==front)?true:false;

41 }

42 int getSize()const{

43 return (rear-front+maxSize)%maxSize;

44 }

45 };

測試程式碼如下：

1 void menu(){

2 cout<<"1.入隊"<<endl;

3 cout<<"2.獲取隊首元素"<<endl;

4 cout<<"3.出隊"<<endl;

5 cout<<"4.佇列置空"<<endl;

6 cout<<"5.獲取隊中元素數量"<<endl;

7 cout<<"6.退出"<<endl;

8 }

9

10 void function(int num,SeqQueue<int> *sq){

11 switch(num){

12 int x;

13 case 1:

14 cin>>x;

15 sq->EnQueue(x);

16 break;

17 case 2:

18 sq->getFront(x);

19 cout<<x<<endl;

20 break;

21 case 3:

22 sq->DeQueue(x);

23 break;

24 case 4:

25 sq->makeEmpty();

26 break;

27 case 5:

28 x=sq->getSize();

29 cout<<x<<endl;

30 break;

31 default:

32 exit(1);

33 }

34 }

35 int main(int argc, char** argv) {

36 SeqQueue<int> *sq=new SeqQueue<int>;

37 int num;

38 while(true){

39 menu();

40 cin>>num;

41 function(num,sq);

42 }

43 delete sq;

44 return 0;

45 }

之後是鏈式佇列，實現類程式碼和測試程式碼如下：

1 #include <iostream>

2 using namespace std;

3 template<class T>

4 struct LinkNode{

5 T data;

6 LinkNode<T> *link;

7 LinkNode(T& x,LinkNode<T> *l=NULL){

8 data=x;

9 link=l;

10 }

11 };

12 template<class T>

13 class LinkedQueue{

14 protected:

15 LinkNode<T> *front,*rear;

16 public:

17 LinkedQueue(){

18 front=rear=NULL;

19 }

20 ~LinkedQueue(){

21 makeEmpty();

22 }

23 bool enQueue(T& x){

24 if(front==NULL)

25 front=rear=new LinkNode<T>(x);

26 else{

27 rear=rear->link=new LinkNode<T>(x);

28 }

29 return true;

30 }

31 bool deQueue(T& x){

32 if(isEmpty()) return false;

33 LinkNode<T> *p=front;

34 x=front->data;

35 front=front->link;

36 delete p;

37 return true;

38 }

39 bool getFront(T& x)const{

40 if(isEmpty()) return false;

41 x=front->data;

42 return true;

43 }

44 void makeEmpty(){

45 LinkNode<T> *p;

46 while(front!=NULL){

47 p=front;

48 front=front->link;

49 delete p;

50 }

51 }

52 bool isEmpty()const{

53 return (front==NULL)?true:false;

54 }

55 int getSize()const{

56 LinkNode<T> *p;

57 int count=0;

58 p=front;

59 while(p!=NULL){

60 count++;

61 p=p->link;

62 }

63 return count;

64 }

65 };

66 void menu(){

67 cout<<"1.入隊"<<endl;

68 cout<<"2.獲取隊首元素"<<endl;

69 cout<<"3.出隊"<<endl;

70 cout<<"4.佇列置空"<<endl;

71 cout<<"5.獲取隊中元素數量"<<endl;

72 cout<<"6.退出"<<endl;

73 }

74

75 void function(int num,LinkedQueue<int> *lq){

76 switch(num){

77 int x;

78 case 1:

79 cin>>x;

80 lq->enQueue(x);

81 break;

82 case 2:

83 lq->getFront(x);

84 cout<<x<<endl;

85 break;

86 case 3:

87 lq->deQueue(x);

88 break;

89 case 4:

90 lq->makeEmpty();

91 break;

92 case 5:

93 x=lq->getSize();

94 cout<<x<<endl;

95 break;

96 default:

97 exit(1);

98 }

99 }

100 int main(int argc, char** argv) {

101 LinkedQueue<int> *lq=new LinkedQueue<int>;

102 int num;

103 while(true){

104 menu();

105 cin>>num;

106 function(num,lq);

107 }

108 delete lq;

109 return 0;

110 }