2.队列
2.1 队列的定义
-
定义
只允许在一端进行插入，另一端删除的线性表。
-
特征：先进先出（First In First Out->FIFO）
-
重要术语：队头、队尾、空队列
-
2.2 队列的顺序存储
2.2.1 初始化
- 结构体
typedef struct{
ElemType data[MaxSize]; //静态数组存放队列元素
int front; //队头指针
int rear; //队尾指针
}SqQueue;
-
初始化
void InitQueue(SqQueue &Q){ Q.rear=Q.front=0; } -
判空
bool QueueEmpty(SqQueue &Q){ if(Q.rear==Q.front) return true; else return false; }
2.2.2 循环队列
-
假溢出问题
当rear走到队尾，队头出栈后仍然有存储空间。
所以，根据
rear==MaxSize判溢出会导致存储空间的浪费。
-
用循环队列解决假溢出问题：
把队列看成一个环，rear走到最后一个存储空间时，会重新回到第一个存储空间重新判断。
- 用取模运算实现环。
-
队满实现
- 注：不能以
rear==front来判断队满，因为已经用rear==front这个条件判断空队列，所以判满必须牺牲一个存储单元。
- 注：不能以
-
另外一些操作
- 队首指针进1：
Q.front=(Q.front+1)%MaxSize - 队尾指针进1：
Q.rear=(Q.rear+1)%MaxSize - 队列长度：
(Q.rear+MaxSize-Q.front)%MaxSize
- 队首指针进1：
-
若要求不能浪费那一块存储空间：
-
方法一：设置size变量记录队中的元素个数：
typedef struct{ ElemType data[MaxSize]; int front,rear; int size; //队列当前长度 }SqQueue; //初始化时 rear=front=0; size=0; //队满条件 size=MaxSize; //队空条件 size=0; -
方法二：设置tag记录最新一次的操作是删除还是插入
typedef struct{ ElemType data[MaxSize]; int front,rear; int tag; //最近进行的是删除/插入操作 }SqQueue; //tag的定义： //插入操作成功时：tag=1； //删除操作成功时：tag=0。 //只有删除操作，才可能导致队空 //只有插入操作，才可能导致队满 //初始化 rear=front=0; tag=0; //队空条件 front==rear&&tag==0 //队满条件 front==rear&&tag==1
-
2.2.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; //队尾加一取模
return true;
}
2.2.4 出队
bool DeQueue(SqQueue &Q,ElemType &x){
if(Q.rear==Q.front)return false; //队空报错
x=Q.data[Q.front]; //返回出队元素
Q.front=(Q.front+1)%MaxSize; //队头指针后移
return true;
}
2.2.5 获取队头元素
bool GetHead(SqQueue Q,ElemType &x){
if(Q.rear==Q.front)return false;
x=Q.data[Q.front];
return true;
}
*完整代码 顺序队列
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define ElemType int
#define MaxSize 5
typedef struct {
ElemType data[MaxSize];
int front, rear;
}SqQueue;
void InitQueue(SqQueue& Q) {
Q.front = Q.rear = 0;
}
bool QueueEmpty(SqQueue& Q) {
if (Q.rear == Q.front)
return true;
else
return false;
}
int Length(SqQueue& Q) {
return (Q.rear + MaxSize - Q.front) % MaxSize;
}
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;
return true;
}
bool DeQueue(SqQueue& Q,ElemType &x) {
if (Q.rear == Q.front)return false;
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
bool GetHead(SqQueue Q, ElemType& x) {
if (Q.rear == Q.front)return false;
x = Q.data[Q.front];
return true;
}
//从队头开始打印
void PrintQ(SqQueue Q) {
int p = Q.front;
while (p!=Q.rear) {
printf("%d ", Q.data[p]);
p = (p +1) % MaxSize;
}
printf("\n\n");
}
int main(){
SqQueue Q;
InitQueue(Q);
printf("入栈：\n");
EnQueue(Q, 1);
EnQueue(Q, 2);
EnQueue(Q, 3);
EnQueue(Q, 4);
PrintQ(Q);
printf("队列长度：%d\n", Length(Q));
printf("出栈：\n");
int x;
DeQueue(Q, x);
printf("出栈元素为：%d\n", x);
DeQueue(Q, x);
printf("出栈元素为：%d\n", x);
PrintQ(Q);
GetHead(Q, x);
printf("栈顶元素：%d\n", x);
printf("循环队列测试：\n");
EnQueue(Q, 5);
EnQueue(Q, 6);
EnQueue(Q, 7);
PrintQ(Q);
DeQueue(Q, x);
PrintQ(Q);
}
2.3 队列的链式存储
-
就是一个有队头指针和队尾指针的单链表。
//链式队列结点
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
//链式队列
typedef struct{
LinkNode *front,*rear;
}LinkQueue;
*完整代码 链队
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define ElemType int
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 = Q.rear->next = NULL;
}
bool isEmpty(LinkQueue& Q) {
if (Q.front == Q.rear)
return true;
else
return false;
}
void EnQueue(LinkQueue& Q, ElemType x) {
LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));
p->data = x;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
}
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;
}
void PrintQ(LinkQueue& Q) {
LinkNode* p = Q.front->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n\n");
}
int main() {
LinkQueue Q;
InitQueue(Q);
printf("入栈：\n");
EnQueue(Q, 1);
EnQueue(Q, 2);
EnQueue(Q, 3);
EnQueue(Q, 4);
PrintQ(Q);
printf("出栈：\n");
int x;
DeQueue(Q, x);
printf("出栈元素为：%d\n", x);
DeQueue(Q, x);
printf("出栈元素为：%d\n", x);
PrintQ(Q);
}
2.4 双端队列
-
定义
也是插入和删除受限的线性表：
-
还有输入受限或输出受限的双端队列：
-
