- 一、队列的基本概念
- 二、队列的顺序存储结构
- 1.队列的顺序存储
- 2.循环队列的操作
- 三、队列的链式存储结构
- 1.队列的链式存储
- 2.链式存储的操作
- 四、完整代码
一、队列的基本概念
队列是一种操作比较受限的线性表，因为它只允许在表的一段进行插入，而在表的另一端进行删除。遵行的是一个先进先出的原则。
队列的顺序存储也是跟栈和简单顺序表一样，在一开始需要定义元素存储的大小。之后设置两个指针，分别指向队头和队尾。队列的顺序存储类型为：
#define MaxSize 6 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct {
ElemType data[MaxSize]; //只能存放MaxSize-1个元素
int front, rear; //定义一个队头指针和一个队尾指针
}SqQueue;
（1）在定义一个队列元素的最大个数之后，真正可以存储数据的只有MaxSize-1个元素，因为需要拿出一个存储单元来使队尾指针指向它，不然在判断队空还是队满的时候，队头指针和队尾指针都指向一个存储单元之后会导致判断不了，如图所示：
（2）当第一个元素入队时，队头指针就会一直指向它，除非它出队列了，而队尾指针则指向插入元素后的一个存储单元。每插入一个元素后，队尾指针都会向后移一个位置。而每当出队一个元素之后，队头指针也会往后移一个位置。
（1）初始化
//初始化
void InitQueue(SqQueue& Q)
{
Q.front = Q.rear = 0;
}
（2）判断队列是否为空
//判断队列是否为空
bool isEmpty(SqQueue Q)
{
if (Q.front == Q.rear) //当队头、队尾指针指向同一个存储单元时队列为空
{
return true;
}
return false;
}
（3）入队操作
//入队操作
bool EnQueue(SqQueue& Q, ElemType x)
{
if ((Q.rear + 1) % MaxSize == Q.front) //判断队列是否满了
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize; //在队尾插入元素后，尾指针往后进1位
return true;
}
插入数据之后设置一个断点可以看到插入的相应值，分别是2，3，4，5。
（4）出队操作
//出队
bool DeQueue(SqQueue &Q, ElemType &x)
{
if (Q.front == Q.rear) //判断队列是否为空
{
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize; //当队头弹出一个元素后，队头指针往后进1位
return true;
}
三、队列的链式存储结构
1.队列的链式存储
队列的链式又称为链队列，同时带有队头结点和队尾结点的单链表。
队列的链式存储结构类型为：
typedef int ElemType;
typedef struct LinkNode { //链式队列结点
ElemType data;
struct LinkNode* next;
}LinkNode;
typedef struct { //链式队列
LinkNode* front, * rear; //队列的队头和队尾指针
}LinkQueue;
2.链式存储的操作
（1）初始化
//初始化
void InitQueue(LinkQueue& Q)
{
Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode)); //建立头结点
Q.front->next = NULL;
}
（2）判断队列是否为空
当队头结点等于队尾结点的时候，则队列为空。
//判断是否为空
bool InEmpty(LinkQueue Q)
{
if (Q.front == Q.rear)
return true;
else
return false;
}
（3）入队操作
//入队
void EnQueue(LinkQueue& Q, ElemType x)
{
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode)); //创建新的结点，并为其申请空间
s->data = x;
s->next = NULL;
Q.rear->next = s;
Q.rear = s;
}
设置一个断点查看入队的元素，分别为2，3，4，5。
（4）出队操作
//出队
bool DeQueue(LinkQueue& Q, ElemType& x)
{
if (Q.front == Q.rear)
return false;
LinkNode* p = Q.front->next; //因为存在头结点，且头结点里面没数据，所以指向下一个
x = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front; //如果队里中只有一个结点，则出队之后队列变空
free(p);
return true;
}
四、完整代码
（1）队列的顺序存储
#include#include #define MaxSize 6 //定义队列中元素的最大个数 typedef int ElemType; typedef struct { ElemType data[MaxSize]; //只能存放MaxSize-1个元素 int front, rear; //定义一个队头指针和一个队尾指针 }SqQueue; //初始化 void InitQueue(SqQueue& Q) { Q.front = Q.rear = 0; } //判断队列是否为空 bool isEmpty(SqQueue Q) { if (Q.front == Q.rear) { return true; } return false; } //入队操作 bool EnQueue(SqQueue& Q, ElemType x) { if ((Q.rear + 1) % MaxSize == Q.front) //判断队列是否满了 return false; Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MaxSize; //在队尾插入元素后，尾指针往后进1位 return true; } //出队 bool DeQueue(SqQueue &Q, ElemType &x) { if (Q.front == Q.rear) //判断队列是否为空 { return false; } x = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize; //当对头弹出一个元素后，队头指针往后进1位 return true; } int main() { SqQueue Q; bool ret; ElemType element; InitQueue(Q); EnQueue(Q, 2); EnQueue(Q, 3); EnQueue(Q, 4); EnQueue(Q, 5); EnQueue(Q, 6); ret = EnQueue(Q, 7); //已经超出了范围，所以7入不了队 if (ret) { printf("入队成功n"); } else { printf("入队失败n"); } ret = isEmpty(Q); if (ret) { printf("队列为空n"); } else { printf("队列不为空n"); } ret= DeQueue(Q, element); if (ret) { printf("出队成功,元素值为%dn",element); } else { printf("出队失败：n"); } ret = DeQueue(Q, element); if (ret) { printf("出队成功,元素值为%dn", element); } else { printf("出队失败：n"); } return 0; }
（2）队列的链式存储
#include#include typedef int ElemType; typedef struct LinkNode { //链式队列结点 ElemType data; struct LinkNode* next; }LinkNode; typedef struct { //链式队列 LinkNode* front, * rear; //队列的队头和队尾指针 }LinkQueue; //初始化 void InitQueue(LinkQueue& Q) { Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode)); Q.front->next = NULL; } //判断是否为空 bool InEmpty(LinkQueue Q) { if (Q.front == Q.rear) return true; else return false; } //入队 void EnQueue(LinkQueue& Q, ElemType x) { LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode)); s->data = x; s->next = NULL; Q.rear->next = s; Q.rear = s; } //出队 bool DeQueue(LinkQueue& Q, ElemType& x) { if (Q.front == Q.rear) return false; LinkNode* p = Q.front->next; //因为存在头结点，且头结点里面没数据，所以指向下一个 x = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; //如果队里中只有一个结点，则出队之后队列变空 free(p); return true; } int main() { LinkQueue Q; bool ret; ElemType element; InitQueue(Q); EnQueue(Q, 2); EnQueue(Q, 3); EnQueue(Q, 4); EnQueue(Q, 5); ret = DeQueue(Q, element); if (ret) { printf("出队成功，出队元素为：%dn", element); } else { printf("出队失败n"); } ret = DeQueue(Q, element); if (ret) { printf("出队成功，出队元素为：%dn", element); } else { printf("出队失败n"); } return 0; }
