考研复习之队列

循环队列

队列为满的条件

      队列为满的条件需要特殊处理，因为当队列满时，队尾指针的下一个位置应该是队头指针。但是，我们不能直接比较 rear + 1 和 front 是否相等，因为 rear + 1 可能会超出数组索引的范围。因此，我们需要使用模运算 % 来确保索引在数组范围内循环。

        

        浪费一个空间：
        在这种方法中，我们故意让队列中始终保持一个空闲位置，这样当 rear 的下一个位置是 front 时，队列就是满的。

(Q.rear + 1) % MAX_SIZE == Q.front

入队  出队

#include<iostream>
#define Maxsize 6
using namespace std;typedef struct {int data[Maxsize]; // 数组，存储Maxsize-1个元素int front, rear;   // 队列头和队列尾
} SqQueue;void init(SqQueue &Q) {Q.front = Q.rear = 0;
}bool enqueue(SqQueue &Q, int x) {if ((Q.rear + 1) % Maxsize == Q.front) // 判断循环队列是否满了return false;else {Q.data[Q.rear] = x; // 放入元素Q.rear = (Q.rear + 1) % Maxsize; // 改变队尾标记return true;}
}bool dequeue(SqQueue &Q, int &data) {if (Q.rear == Q.front) // 判断队列是否为空return false;else {data = Q.data[Q.front]; // 取出队头元素Q.front = (Q.front + 1) % Maxsize; // 改变队头标记return true;}
}bool isEmpty(SqQueue Q) {return Q.rear == Q.front;
}int main() {SqQueue Q;bool ret;int data;init(Q); // 初始化队列ret = isEmpty(Q);if (ret) {cout << "kong" << endl;} else {cout << "bu wei kong " << endl;}ret = dequeue(Q, data);if (ret) {cout << "出队的元素是" << data << endl;} else {cout << "kong zhan" << endl;}// 测试入队和出队enqueue(Q, 1);enqueue(Q, 2);enqueue(Q, 3);enqueue(Q, 4);enqueue(Q, 5);while (dequeue(Q, data)) {cout << "出队的元素是" << data << endl;}return 0;
}

链队列

用链表表示队列

#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct node {int data;struct node *next;
}LinkNode; typedef struct {LinkNode * front ,* rear;//链表头，链表尾，即对头和队尾 
}LinkQueue;//用带头结点的链表来实现队列 
void init(LinkQueue &Q)
{Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode)); Q.front->next=NULL;
}void enqueue(LinkQueue &Q,int x)
{LinkNode *newnode;newnode=(LinkNode *)malloc(sizeof(LinkNode));newnode->data=x;Q.rear->next=newnode;Q.rear=newnode;//rear指向新的尾部 newnode->next=NULL;}int dequeue(LinkQueue &Q,int &data)
{if(Q.rear==Q.front ){cout<<"栈空"<<endl;}else{LinkNode * q=Q.front->next;//指向第一个元素 Q.front->next=q->next;data=q->data; //获取出队的元素值 if(Q.rear=q)//队列只剩一个元素，被删除后要改变rear; {Q.front=Q.rear;}}return data;
}
bool IsEmpty(LinkQueue Q)
{if(Q.front==Q.rear ){return true;}else{return false;}
}
int main()
{LinkQueue Q;init(Q); enqueue(Q,1);enqueue(Q,2);enqueue(Q,3);enqueue(Q,4);enqueue(Q,5);int data;data=dequeue(Q,data);cout<<"出对的元素值是"<<data<<" "<<endl;return 0;}