顺序循环队列

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. typedef int Status;
  5. typedef int QElemType;
  7. #define OVERFLOW -1
  8. #define ERROR 0
  9. #define OK 1
  10. #define MAXSIZE 100
  12. /**
  13.  * 循环队列——队列的顺序表示和实现
  14.  * 
  15.  * 操作：初始化、队列长度、入队、出队、取队头元素
  16.  */
  18. /* 存储形式 */
  19. typedef struct {
  20.     QElemType *base;
  21.     int front;
  22.     int rear;
  23. } SqQueue;
  25. /* 初始化 */
  26. Status InitQueue(SqQueue &queue) {
  27.     // 初始化这个base地址为一个有最大容量的数组初地址
  28.     queue.base = new int[MAXSIZE];
  29.     if (!queue.base) {
  30.         return OVERFLOW;
  31.     }
  32.     queue.front = queue.rear = 0;
  33.     return OK;
  34. }
  36. /* 求队列长度 */
  37. Status QueueLength(SqQueue &queue) {
  38.     return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
  39. }
  41. /* 入队 */
  42. Status EnQueue(SqQueue &queue, QElemType e) {
  43.     if ((queue.rear+1)%MAXSIZE == queue.front) {
  44.         return OVERFLOW;
  45.     }
  46.     queue.base[queue.rear] = e;
  47.     queue.rear = (queue.rear + 1) % MAXSIZE;
  48.     return OK;
  49. }
  51. /* 出队 */
  52. Status DeQueue(SqQueue &queue) {
  53.     if ((queue.rear+1)%MAXSIZE == queue.front) {
  54.         return OVERFLOW;
  55.     }
  56.     QElemType e = queue.base[queue.front];
  57.     queue.front = (queue.front + 1) % MAXSIZE; //队头指针+1
  58.     return e;
  59. }
  61. /* 取队头元素 */
  62. Status GetHead(SqQueue &queue) {
  63.     if (queue.front != queue.rear) {
  64.         return queue.base[queue.front];
  65.     }
  66. }
  69. int main() {
  70.     SqQueue test;
  71.     InitQueue(test);
  72.     EnQueue(test, 10);
  73.     EnQueue(test, 15);
  74.     EnQueue(test, 20);
  75.     cout << "队列长度为：" << QueueLength(test) << "\n";
  76.     cout << GetHead(test)<<" "<< GetHead(test)<<" "<< GetHead(test)<<" "<<"\n";
  77.     cout << DeQueue(test)<<" "<< DeQueue(test)<<" "<< DeQueue(test)<<" "<<"\n";
  78. }

链队

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. typedef int Status;
  5. typedef int QElemType;
  7. #define OVERFLOW -1
  8. #define ERROR 0
  9. #define OK 1
  10. #define MAXSIZE 100
  12. /**
  13.  * 链队——队列的链式表示和实现
  14.  * 
  15.  * 操作：初始化、入队、出队、取队头元素
  16.  */
  18. /* 存储形式 */
  19. typedef struct QNode{ //链队用的结点
  20.     QElemType data;
  21.     struct QNode *next;
  22. }QNode,*QueuePtr;
  24. typedef struct {
  25.     QueuePtr front;
  26.     QueuePtr rear;
  27. }LinkQueue;
  29. /* 初始化 */
  30. Status InitQueue(LinkQueue &queue) {
  31.     queue.front = queue.rear = new QNode;
  32.     queue.front->next = NULL;
  33.     return OK;
  34. }
  36. /* 入队 */
  37. Status EnQueue(LinkQueue &queue, QElemType e) {
  38.     QueuePtr temp = new QNode;
  39.     temp->data = e;
  40.     temp->next = NULL;
  41.     queue.rear->next = temp;
  42.     queue.rear = temp;
  43.     return OK;
  44. }
  46. /* 出队 */
  47. Status DeQueue(LinkQueue &queue) {
  48.     if (queue.front == queue.rear) {
  49.         return OVERFLOW;
  50.     }
  51.     QElemType e = queue.front->next->data;
  52.     queue.front->next = queue.front->next->next;
  53.     // 考虑最后一个元素被删，队尾指针指向头结点
  54.     if (queue.rear == queue.front) {
  55.         queue.front = queue.rear;
  56.     }
  57.     return e;
  58. }
  60. /* 取队头元素 */
  61. Status GetHead(LinkQueue &queue) {
  62.     if (queue.front != queue.rear){
  63.         return queue.front->next->data;
  64.     }
  65. }
  68. int main() {
  69.     LinkQueue test;
  70.     InitQueue(test);
  71.     EnQueue(test, 10);
  72.     EnQueue(test, 15);
  73.     EnQueue(test, 20);
  74.     // cout << "队列长度为：" << QueueLength(test) << "\n";
  75.     cout << GetHead(test)<<" "<< GetHead(test)<<" "<< GetHead(test)<<" "<<"\n";
  76.     cout << DeQueue(test)<<" "<< DeQueue(test)<<" "<< DeQueue(test)<<" "<<"\n";
  77. }