语言用链表实现循环队列

语言用链表实现循环队列？

循环队列：

1.循环队列中判断队空的方法是判断front==rear，队满的方法是判断front=（rear+1）%maxSize。（我曾经想过为什么不用一个length表示队长，当length==maxSize时队满）原因就是，在频繁的队列操作中，多出一个变量会大量的增加执行时间，所以不如浪费一个数组空间来得划算。

2.用单链表表示的链式队列特别适合于数据元素变动较大的情形，而且不存在溢出的情况。

1 template

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.入队"<

3 cout<<"2.获取队首元素"<

4 cout<<"3.出队"<

5 cout<<"4.队列置空"<

6 cout<<"5.获取队中元素数量"<

7 cout<<"6.退出"<

8 }

9

10 void function(int num,SeqQueue *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<

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<

30 break;

31 default:

32 exit(1);

33 }

34 }

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

36 SeqQueue *sq=new SeqQueue;

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

2 using namespace std;

3 template

4 struct LinkNode{

5 T data;

6 LinkNode *link;

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

8 data=x;

9 link=l;

10 }

11 };

12 template

13 class LinkedQueue{

14 protected:

15 LinkNode *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(x);

26 else{

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

28 }

29 return true;

30 }

31 bool deQueue(T& x){

32 if(isEmpty()) return false;

33 LinkNode *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 *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 *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.入队"<

68 cout<<"2.获取队首元素"<

69 cout<<"3.出队"<

70 cout<<"4.队列置空"<

71 cout<<"5.获取队中元素数量"<

72 cout<<"6.退出"<

73 }

74

75 void function(int num,LinkedQueue *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<

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<

95 break;

96 default:

97 exit(1);

98 }

99 }

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

101 LinkedQueue *lq=new LinkedQueue;

102 int num;

103 while(true){

104 menu();

105 cin>>num;

106 function(num,lq);

107 }

108 delete lq;

109 return 0;

110 }