队列

介绍

队列属于线性表的一种，具有"先进先出"的特点，与之对应的是栈，栈的特点是"先进后出''.顺序队列可以视为环形结构：

开始的时候头指针和尾指针都直线0的位置，有新元素进入队列时将元素放进尾指针所指向的位置，尾指针向后移动一位，由于是环形结构因此更新后的尾指针应为：(rear + 1) % maxsize。

删除元素的时候将头指针向后移动一位即可，同样更新后的头指针应为：(front + 1) % maxsize。

判断队列空的条件为头指针与尾指针是否重合，即：rear == front。

队列满时同样是头指针与尾指针指向同一地址，此时无法与栈空区分，此时一般采用空出一块存储空间做做法，将队列满的判断条件改为：(rear + 1) % maxsize == front。

代码

 //线性表中的顺序队列
 #include <iostream>
 using namespace std;
 ​
 #define MaxSize 50 //队列中元素最大个数
 ​
 template <class T>
 class SqQueue
 {
 public:
     T data[MaxSize]; //存放队列元素
     int front, rear; //队头指针和队尾指针
 };
 ​
 template <class T>
 void InitQueue(SqQueue<T> &Q) //初始化队列
 {
     Q.front = 0;
     Q.rear = 0;
 }
 ​
 template <class T>
 bool QueueEmpty(SqQueue<T> Q) //判断队列是否为空
 {
     return Q.front == Q.rear;
 }
 ​
 template <class T>
 bool EnQueue(SqQueue<T> &Q, T x) //入队
 {
     if ((Q.rear + 1) % MaxSize == Q.front) //判断队列是否已满
         return false;
     Q.data[Q.rear] = x;
     Q.rear = (Q.rear + 1) % MaxSize; //更新rear指针
     return true;
 }
 ​
 template <class T>
 bool DeQueue(SqQueue<T> &Q, T &x) //出队
 {
     if (QueueEmpty(Q)) //判断队列是否为空
         return false;
     x = Q.data[Q.front];
     Q.front = (Q.front + 1) % MaxSize; //更新front指针
     return true;
 }
 ​
 template <class T>
 bool GetHead(SqQueue<T> Q, T &x) //读元素
 {
     if (QueueEmpty(Q)) //判断队列是否为空
         return false;
     x = Q.data[Q.front];
     return true;
 }
 ​
 template <class T>
 bool Destroy(SqQueue<T> &Q) //销毁队列
 {
     Q.front = 0;
     Q.rear = 0;
     return true;
 }
 ​
 int main()
 {
     SqQueue<int> Q; //整数队列
     InitQueue(Q);   //初始队列
     for (int i = 0; i < 10; i++)
         EnQueue(Q, i); //入队
     int x;
     GetHead(Q, x); //读取队首元素
     cout << "队首元素的值为:" << x << endl;
     DeQueue(Q, x); //出队
     GetHead(Q, x); //读取队首元素
     cout << "队首元素的值为:" << x << endl;
     if (Destroy(Q)) //销毁队列
         cout << "队列销毁成功。" << endl;
     system("pause");
     return 0;
 }

结果：

链式队列只需在普通队列添加一个尾指针，入队即在头指针出插入节点，出队即删除尾节点即可，改动较少，不再复现。

标签：学习笔记, c/c++