文章目录
前言
队列是一种“先进先出”的线性表，仅在表的一端进行插入（入队），称为队尾，在另一端进行删除（出队），称为对头，即“尾进头出”。队列只有对头和队尾可以被外界访问，所以不可以遍历。生活中的各种排队都是队列。
队列有两种存储方式：顺序存储和链式存储。采用顺序存储的队列称为顺序队列，采用链式存储的队列称为链式队列。
一、顺序队列
顺序队列采用数组方式存储队列中的元素，使用头指针(front)和尾指针(rear)分别指向队列的对头和队尾。
/*----------------------------------------------------------------
设立一个队首指针front ，一个队尾指针rear ，分别指向队首和队尾元素。
◆ 初始化：front=rear=0。
◆ 队列为空：front==rear。
◆ 队满：rear==MaxSize。
◆ 入队：将新元素插入rear所指的位置，然后rear加1。
◆ 出队：删去front所指的元素，然后加1并返回被删元素。
◆ 取队首元素：返回front指向的元素值
-----------------------------------------------------------------*/
#include <stdio.h>
#include <assert.h>
#include <Windows.h>
#define MaxSize 10 //队列的最大容量
typedef int DataType; //队列中元素类型
typedef struct Queue
{
DataType Queue[MaxSize];
int fornt; //队头指针
int rear; //队尾指针
}SeqQueue;
//队列初始化，将队列初始化为空队列
void InitQueue(SeqQueue *SQ)
{
SQ->fornt = SQ->rear = 0; //把对头和队尾指针同时置0
}
//判断队列为空
int IsEmpty(SeqQueue* SQ)
{
if (SQ->fornt == SQ->rear)
{
return 1;
}
return 0;
}
//判断队列是否为满
int IsFull(SeqQueue* SQ)
{
if (SQ->rear == MaxSize)
{
return 1;
}
return 0;
}
//入队,将元素data插入到队列SQ中
void EnterQueue(SeqQueue* SQ,DataType data)
{
if (IsFull(SQ))
{
printf("队列已满\n");
return 0;
}
SQ->Queue[SQ->rear] = data; //在队尾插入元素data
SQ->rear = SQ->rear + 1; //队尾指针后移一位
}
//出队，将队列中队头的元素data出队，出队后队头指针front后移一位
int DeleteQueue(SeqQueue* SQ,DataType* data)
{
if (IsEmpty(SQ))
{
printf("队列为空！\n");
return 0;
}
*data = SQ->Queue[SQ->fornt]; //出队元素值
SQ->fornt = (SQ->fornt)+1; //队尾指针后移一位
return 1;
}
//获取队首元素
int GetHead(SeqQueue* SQ,DataType* data)
{
if (IsEmpty(SQ))
{
printf("队列为空!\n");
}
return *data = SQ->Queue[SQ->fornt];
}
//清空队列
void ClearQueue(SeqQueue* SQ)
{
SQ->fornt = SQ->rear = 0;
}
//打印队列中的与元素
void PrintQueue(SeqQueue* SQ)
{
assert(SQ);
int i = SQ->fornt;
while(i<SQ->rear)
{
printf("%-3d", SQ->Queue[i]);
i++;
}
printf("\n");
}
int main()
{
SeqQueue SQ;
DataType data;
//初始化队列
InitQueue(&SQ);
//入队
EnterQueue(&SQ, 1);
EnterQueue(&SQ, 2);
EnterQueue(&SQ, 3);
EnterQueue(&SQ, 4);
EnterQueue(&SQ, 5);
EnterQueue(&SQ, 6);
EnterQueue(&SQ, 8);
EnterQueue(&SQ, 10);
EnterQueue(&SQ, 12);
EnterQueue(&SQ, 15);
EnterQueue(&SQ, 16);
//打印队列中的元素
printf("队列中的元素为：");
PrintQueue(&SQ);
printf("\n");
//出队
DeleteQueue(&SQ, &data);
printf("出队元素为：%d\n", data);
printf("\n");
DeleteQueue(&SQ, &data);
printf("出队元素为：%d\n", data);
printf("\n");
printf("队列中的元素为：");
PrintQueue(&SQ);
printf("\n");
//获取队首元素
data = GetHead(&SQ, &data);
printf("队首元素为：%d\n", data);
printf("#元素16入队#\n");
//元素16入队
EnterQueue(&SQ, 16);
printf("队列中的元素为：");
PrintQueue(&SQ);
printf("\n");
system("pause");
return 0;
}
结果为：
从上可以看出，一旦队列满了之后，即使有元素出队，也不能进行入队操作，这是因为顺序队列的“假溢出现象”。假溢出现象就是队头由于出队操作，会产生新的空间，但队尾指针已经到达数组的末尾，队尾指针就会越出数组的上界而造成溢出。这种溢出不是因为存储空间不足而造成的溢出，而是经过多次的插入和删除引起的，像这种有存储空间却不能插入元素的操作称为”假溢出“。如下图所示：
二、循环队列
为了充分利用存储空间，消除”假溢出现象“，可以将队列分配的空间看作一个首尾相接的环，这样的队列叫做循环队列。
循环队列在队空或者队满时，头指针和尾指针都指向同一位置，即front = =rear;为了区分这两种情况，可以：
- 设一个标志量tag区分队空和队满。
- 设一个计数器对元素计数，为0表示队空，与队容量相等表示队满。
- 少用一个元素空间，队尾rear指向的是实际队尾的后一个元素。
队空：front == rear;
队满：（rear + 1）% MaxSize = = front。
/*----------------------------------------------------------------
设立一个队首指针front ，一个队尾指针rear ，分别指向队首和队尾元素。
◆ 初始化：front=rear=0。
◆ 队列为空：front==rear。
◆ 队满：（rear + 1) % MaxSize == fornt
◆ 入队：将新元素插入rear所指的位置，然后rear加1。
◆ 出队：删去front所指的元素，然后加1并返回被删元素。
◆ 取队首元素：返回fornt指向的元素值
-----------------------------------------------------------------*/
#include<stdio.h>
#include<Windows.h>
#include<assert.h>
#define MaxSize 10
typedef int DataType;
typedef struct SeqQueue
{
DataType Queue[MaxSize];
int fornt;
int rear;
}SeqCirQueue;
//队列初始化
void InitSeqCirQueue(SeqCirQueue* SCQ)
{
SCQ->fornt = SCQ->rear = 0;
}
//判断队列是否为空
int IsEmpty(SeqCirQueue* SCQ)
{
if (SCQ->fornt == SCQ->rear)
{
return 1;
}
return 0;
}
//判断队列是否为满
int IsFull(SeqCirQueue* SCQ)
{
//尾指针+1追上队头指针，标志队列已经满了
if ((SCQ->rear + 1) % MaxSize == SCQ->fornt)
{
return 1;
}
return 0;
}
//入队操作
int EnterSeqCirQueue(SeqCirQueue* SCQ, DataType data)
{
if (IsFull(SCQ))
{
printf("队列已满，不能入队！\n");
return 0;
}
SCQ->Queue[SCQ->rear] = data;
SCQ->rear = (SCQ->rear + 1) % MaxSize; //重新设置队尾指针
}
//出队操作
int DeleteSeqCirQueue(SeqCirQueue* SCQ,DataType* data)
{
if (IsEmpty(SCQ))
{
printf("队列为空！\n");
return 0;
}
*data = SCQ->Queue[SCQ->fornt];
SCQ->fornt = (SCQ->fornt + 1) % MaxSize; //重新设置队头指针
}
//取队首元素
int GetHead(SeqCirQueue* SCQ,DataType* data)
{
if (IsEmpty(SCQ))
{
printf("队列为空！\n");
return 0;
}
*data = SCQ->Queue[SCQ->fornt];
return *data;
}
//清空队列
void ClearSeqCirQueue(SeqCirQueue* SCQ)
{
SCQ->fornt = SCQ->rear = 0;
}
//打印队列元素
void PrintSeqCirQueue(SeqCirQueue* SCQ)
{
assert(SCQ); //断言SCQ不为空
int i = SCQ->fornt;
if (SCQ->fornt < SCQ->rear)
{
for (; i < SCQ->rear; i++)
{
printf("%-3d", SCQ->Queue[i]);
}
}
else
{
for (i; i <SCQ->rear + MaxSize; i++)
{
printf("%-3d", SCQ->Queue[i]);
}
}
printf("\n");
}
int main()
{
SeqCirQueue SCQ;
DataType data;
//初始化队列
InitSeqCirQueue(&SCQ);
//入队
EnterSeqCirQueue(&SCQ, 1);
EnterSeqCirQueue(&SCQ, 2);
EnterSeqCirQueue(&SCQ, 4);
EnterSeqCirQueue(&SCQ, 6);
EnterSeqCirQueue(&SCQ, 8);
EnterSeqCirQueue(&SCQ, 9);
EnterSeqCirQueue(&SCQ, 10);
EnterSeqCirQueue(&SCQ, 12);
EnterSeqCirQueue(&SCQ, 13);
printf("队列中元素为：\n");
//打印队列中元素
PrintSeqCirQueue(&SCQ);
EnterSeqCirQueue(&SCQ, 15);
//出队
DeleteSeqCirQueue(&SCQ, &data);
printf("出队元素为：%d\n", data);
printf("\n");
printf("队列中元素为：\n");
PrintSeqCirQueue(&SCQ);
printf("15入队：\n");
EnterSeqCirQueue(&SCQ, 15);
printf("队列中元素为：\n");
PrintSeqCirQueue(&SCQ);
system("pause");
return 0;
}
结果为：元素出队后，会释放空间，新的元素可以入队，消除了”假溢出现象“。
三、链式队列
链式队列是限制仅在表头进行删除操作和表尾进行插入操作的单链表，链式队列的操作实际上就是单链表的操作，只不过出队在表头进行，入队在表尾进行。链式队列的入队和出队可参考下图：
#include <stdio.h>
#include <Windows.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
typedef struct Node
{
DataType _data;
struct Node* _next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode* front;
LinkQueueNode* rear;
}LinkQueue;
//初始化队列
void InitLinkQueue(LinkQueue* LQ)
{
//创建一个头结点
LinkQueueNode* pHead = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
assert(pHead);
LQ->front = LQ->rear = pHead; //队头和队尾指向头结点
LQ->front->_next = NULL;
}
//判断队列是否为空
int IsEmpty(LinkQueue* LQ)
{
if (LQ->front->_next == NULL)
{
return 1;
}
return 0;
}
//入队操作
void EnterLinkQueue(LinkQueue* LQ, DataType data)
{
//创建一个新结点
LinkQueueNode* pNewNode = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
assert(pNewNode);
pNewNode->_data = data; //将数据元素赋值给结点的数据域
pNewNode->_next = NULL; //将结点的指针域置空
LQ->rear->_next = pNewNode; //将原来队列的队尾指针指向新结点
LQ->rear = pNewNode; //将队尾指针指向新结点
}
//出队操作
void DeleteLinkQueue(LinkQueue* LQ,DataType* data)
{
if (IsEmpty(LQ))
{
printf("队列为空！\n");
return;
}
//pDel指向队头元素，由于队头指针front指向头结点，所以pDel指向头结点的下一个结点
LinkQueueNode* pDel = LQ->front->_next;
*data = pDel->_data; //将要出队的元素赋给data
LQ->front->_next = pDel->_next; //使指向头结点的指针指向pDel的下一个结点
//如果队列中只有一个元素,将队列置空
if (LQ->rear = pDel)
{
LQ->rear = LQ->front;
}
free(pDel); //释放pDel指向的空间
}
//取队头元素
int GetHead(LinkQueue* LQ, DataType* data)
{
if (IsEmpty(LQ))
{
printf("队列为空!\n");
return 0;
}
LinkQueueNode* pCur;
pCur = LQ->front->_next; //pCur指向队列的第一个元素，即头结点的下一个结点
*data = pCur->_data; //将队头元素值赋给data
return *data; //返回队头元素值
}
//清空队列
void ClearQueue(LinkQueue* LQ)
{
while (LQ->front != NULL)
{
LQ->rear = LQ->front->_next; //队尾指针指向队头指针的下一个结点
free(LQ->front); //释放队头指针指向的结点
LQ->front = LQ->rear; //队头指针指向队尾指针
}
}
//打印队列中的元素
void PrintLinkQueue(LinkQueue* LQ)
{
assert(LQ);
LinkQueueNode * pCur;
pCur = LQ->front->_next;
while (pCur)
{
printf("%-3d", pCur->_data);
pCur = pCur->_next;
}
printf("\n");
}
int main()
{
LinkQueue LQ;
DataType data;
//初始化队列
InitLinkQueue(&LQ);
//入队
EnterLinkQueue(&LQ, 1);
EnterLinkQueue(&LQ, 2);
EnterLinkQueue(&LQ, 3);
EnterLinkQueue(&LQ, 4);
EnterLinkQueue(&LQ, 5);
EnterLinkQueue(&LQ, 6);
EnterLinkQueue(&LQ, 7);
EnterLinkQueue(&LQ, 8);
printf("队列中的元素为：");
//打印队列中元素
PrintLinkQueue(&LQ);
printf("\n");
//取队头元素
data = GetHead(&LQ, &data);
printf("队头元素为：%d\n", data);
printf("\n");
//出队
DeleteLinkQueue(&LQ, &data);
printf("出队的元素为：%d\n", data);
printf("\n");
printf("队列中的元素为：");
PrintLinkQueue(&LQ);
printf("\n");
data = GetHead(&LQ, &data);
printf("队头元素为：%d\n", data);
printf("\n");
ClearQueue(&LQ);
system("pause");
return 0;
}
结果为：
四、queue容器
构造函数：
queue<T> que; //采用模板类实现
queue(const queue &que); //拷贝构造函数
赋值操作：
queue & operator= (const queue &que); //重载=操作符
数据存取：
push(elem); //入队，往队尾添加元素
pop(); //移除队头第一个元素
back(); //返回最后一个元素
front(); //返回第一个元素
大小操作：
empty(); //判断队列是否为空
size(); //返回栈的大小
#include <iostream>
#include <queue>
#include <string>
using namespace std;
//队列
class Person
{
public:
Person(string name, int age)
{
this->m_Name = name;
this->m_Age = age;
}
string m_Name;
int m_Age;
};
void test()
{
//创建队列
queue<Person> q;
//准备数据
Person p1("coco",10);
Person p2("dudu", 20);
Person p3("kiki", 18);
Person p4("vivi", 24);
//入队
q.push(p1);
q.push(p2);
q.push(p3);
q.push(p4);
cout << "队列大小：" << q.size() << endl;
//只要队列不为空，就查看队头元素和队尾元素,出队
while (!q.empty())
{
//查看队头元素
cout << "队头元素 —— 姓名:" << q.front().m_Name << " 年龄:" << q.front().m_Age << endl;
//查看队尾元素
cout << "队尾元素 —— 姓名:" << q.back().m_Name << " 年龄:" << q.back().m_Age << endl;
//出队
q.pop();
cout << "队列大小：" << q.size() << endl;
}
}
int main()
{
test();
return 0;
}
结果为：