队列的定义
队列是一种操作受限的线性表,只允许表的一端在进行插入,而在表的另一端进行删除,其操作特征为先进先出.
队头:允许删除的一端
队尾:允许插入的一端
队列的基本操作
InitQueue(&Q) 初始化
isEmpty(Q) 判断空
EnQueue(&Q,x)入队
DeQueue(&Q,&x)出队
GetHead(Q,&x)读队头元素
队列的顺序存储结构
定义队列
#include<stdio.h>
#define MaxSize 5
//定义队列
typedef struct sQuene {int data[MaxSize];int front, rear;
}sQuene;
初始化队列
//初始化
void InitQueue(sQuene &s) {s.front = s.rear = 0;//初始化队首队尾指针
}
判断空
/判断队列空
bool isEmpty(sQuene s) {if (s.front==s.rear){return true;//为空}return false;
}
入队
//插入/入队
bool EnQueue(sQuene &s,int x) {//判断是否队满if ((s.rear+1)%MaxSize==s.front){return false;}s.data[s.rear] = x;s.rear=(s.rear+1)%MaxSize;//队尾指针+1取模
}
出队
//删除/出队
bool DeQueue(sQuene&s,int &e) {//判断队列是否为空if (s.front==s.rear){return false;}e = s.data[s.front];s.front=(s.front + 1) % MaxSize;return true;
}
读取
bool GetHead(sQuene s,int &e) {//判断是否为空if (s.front==s.rear){return false;}e = s.data[s.front];return true;
}
其他考点
(1)判断队列是否已空
方法一:牺牲一个存储单元
方法二:定义队列时加入int size,记录队列长度
#include<stdio.h>
#define MaxSize 5
//定义队列
typedef struct sQuene {int data[MaxSize];int front, rear;int size;
}sQuene;
//初始化
void InitQueue(sQuene& s) {s.size = 0;s.front = s.rear = 0;//初始化队首队尾指针
}
//判断队列空
bool isEmpty(sQuene s) {if (s.size==0){return true;//为空}return false;
}//插入/入队
bool EnQueue(sQuene& s, int x) {//判断是否队满if (s.size==MaxSize){printf("队列已满\n");return false;}s.data[s.rear] = x;s.rear = (s.rear + 1) % MaxSize;//队尾指针+1取模s.size++;
}
//删除/出队
bool DeQueue(sQuene& s, int& e) {//判断队列是否为空if (s.size==0){printf("队列已空\n");return false;}e = s.data[s.front];s.front = (s.front + 1) % MaxSize;s.size--;return true;
}
//读取
int main() {sQuene s;int e;}
方法三:加入int tag,删除0,插入1
判断队满:front==Rear&&tag==1
判断队满:front==Rear&&tag==0
(2)队尾指针指向哪个位置
1.指向队尾元素的后一个位置
2.指向队尾元素