队列和栈不同，队列是先进先出，实现方法也有两种：顺序表和链表。下面是线性表的实现代码：
//队列的存储
#include"pch.h"
#include <iostream>
#define MAXQSIZE 4//我们需要存储多少个元素，那么就需要多存一个因为有一位是空位
using namespace std;
typedef struct
{
int *base;//存储空间的首地址
int front;//头指针，其实就是数组的下标
int rear;
}sqQueue;
//循环队列的初始化
bool InitQueue(sqQueue &Q)
{
//这里用.是因为传入的Q是结构体的地址,.是直接对结构体变量进行指向
//而->是结构体指针的时候用的，所以我们在搞顺序栈的时候用.搞链表的时候用->
Q.base = new int[MAXQSIZE];
if (!Q.base) return false;
Q.front = Q.rear = 0;
return true;
}
//求循环队列的长度
int QueueLength(sqQueue Q)
{
return (Q.rear - Q.front) % MAXQSIZE;
}
//循环队列的入列
bool EnQueue(sqQueue &Q, int e)
{
//如果队尾指针+1等于队头的话，就说明队列满了，因为我们需要预留一位空位
if ((Q.rear + 1) % MAXQSIZE == Q.front) return false;
Q.base[Q.rear] = e;//新入列元素插入队尾
Q.rear = (Q.rear + 1) % MAXQSIZE;//这样做的目的是当队尾指针指向最大值的时候，再加1回回到0
return true;
}
//循环队列的出列
bool DeQueue(sqQueue &Q, int &e)
{
if (Q.front == Q.rear) return false;
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return true;
}
//打印循环队列
bool PrintQueue(sqQueue &Q)
{
if (Q.front == Q.rear) return false;
cout << "front:" << Q.front << "rear:" << Q.rear << endl;
for (int i = Q.front; (i) % MAXQSIZE != Q.rear;)
{
cout << Q.base[i] << endl;
i = (i + 1) % MAXQSIZE;
}
cout << "-------------------" << endl;
}
int main()
{
sqQueue *Q = new sqQueue;
if (!InitQueue(*Q)) return false;
EnQueue(*Q, 1);
EnQueue(*Q, 2);
EnQueue(*Q, 3);
PrintQueue(*Q);
int e = 0;
DeQueue(*Q, e);
cout << "出列的元素:" << e << endl;
PrintQueue(*Q);
EnQueue(*Q, 4);
PrintQueue(*Q);
DeQueue(*Q, e);
cout << "出列的元素:" << e << endl;
EnQueue(*Q, 5);
PrintQueue(*Q);
return 0;
}
链队的话也很简单，只是前面需要预留一个空元素，用于判断队列是否为空。
//队列的存储
#include"pch.h"
#include <iostream>
using namespace std;
//这个是队列的结构，一个放数据一个放下一个队列的指针
typedef struct QNode
{
//这里我们给这个结构体命名为QNode因为
//下面那个next需要用到它，如果结构体里面不需要本身作为指针的话，可以不给结构体命名
int data;
struct QNode *next;
}QNode,*QueuePtr;
//下面这个是队列的信息，主要存放着队列的头部和尾部
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//队列的初始化就是让队列的头部和尾部指向一个空队列
//然后在让队列头部的指针为空
bool InitQueue(LinkQueue &Q)
{
//这里Q是指针，相当于*a，所以可以直接用.,而Q.front是a它也是指针，但是相当于a，存的是地址
//所以我们需要使用->
Q.front = Q.rear = new QNode;
Q.front->next = NULL;
return true;
}
//链队的入列
bool EnQueue(LinkQueue &Q,int e)
{
QueuePtr q = new QNode;
q->next = NULL;
q->data = e;
Q.rear->next = q;
Q.rear = q;
return true;
}
//链队的出列
bool DeQueue(LinkQueue &Q, int &e)
{
if (Q.front == Q.rear) return false;
QueuePtr p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p) Q.rear = Q.front;//如果最后一个元素被删除那么就应该把头指针和尾指针指向同一个位置
delete p;
return true;
}
//打印链队
bool PrintQueue(LinkQueue Q)
{
if (Q.front == Q.rear) return false;
QueuePtr q = Q.front;
while (q->next)
{
q = q->next;
cout << q->data<<endl;
}
cout << "----------------" << endl;
}
int main()
{
LinkQueue *Q = new LinkQueue;
InitQueue(*Q);
EnQueue(*Q, 1);
EnQueue(*Q, 2);
EnQueue(*Q, 3);
PrintQueue(*Q);
int e = 0;
DeQueue(*Q, e);
cout << "出列的元素为" << e << endl;
PrintQueue(*Q);
EnQueue(*Q, 4);
PrintQueue(*Q);
return 0;
}
