[TOC]
一、循环队列（队列的顺序存储）
如果用户的应用程序中设有循环队列，就必须为它设定一个最大队列长度。
1.定义
1
2
3
4
5
6
7
8
9
10
11
12
13
| #define MAXQSIZE 100 //队列可能达到的长度
typedef struct{
int *base; //存储空间的基地址
int front; //头指针，若队列不空，指向队列头元素（实位）
int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置（虚位）
}SqQueue;
SqQueue Q;
|
顺序队列——非循环队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 初始化队列：Q.front=Q.rear=0;
入队：新元素按 rear 指示位置加入，再将队尾指针加一，即
Q.base[Q.rear] = e;
Q.rear = Q.rear+1;
出队：将front指示的元素取出，再将队头指针加一，即
e=Q.base[O.front];
Q.front= Q.front+ 1;
队空：Q.front==Q.rear;
队满：Q.rear-Q.front==MAXQSIZE;
求队长：Q.rear-Q.front;
|
存在“假上溢”的现象：因数组越界而导致的程序非法操作错误，并且此时队列的实际可用空间并未占满。
循环队列
防假上溢：少用一个元素空间，即队列空间大小为m时，有m-1个元素就认为是队满。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 队列初始化： Q.front = Q.rear =0;
队空：Q.front == Q.rear;
队满：(Q.rear + 1)%MAXQSIZE ==Q.front;
入队：（1）队列不满，新元素e插入Q.rear所指的位置
Q.base[Q.rear] = e;
（2）Q.rear = (Q.rear+1)%MAXQSIZE;
出队：（1）队列不空，删除Q.front所指的元素
e = Q.base[Q.front];
（2）Q.front = (Q.front+1)%MAXQSIZE;
求队长：
(Q.rear - Q.front + MAXQSIZE)%MAXQSIZE;
|
2.初始化
- 分配一个最大容量为MAXQSIZE的存储空间Q.base = new int[]
- 判断分配失败
- 否则将头指针和尾指针置为0，表示队列为空
1
2
3
4
5
6
7
8
9
10
11
12
| int InitQueue(SqQueue &Q){
//构造一个空队列
Q.base = new int[MAXQSIZE]; //分配存储空间
if(!Q.base) return -1; //分配失败
Q.front = Q.rear=0; //头指针、尾指针置为0，表示队列为空
return 1;
}
|
3.入队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int EnQueue(SqQueue &Q,int e){
//插入元素e为Q的新队尾元素
if((Q.rear+1)%MAXQSIZE==Q.front)
//尾指针在循环意义上+1后等于头指针，表示队满
return -1;
Q.base[Q.rear] = e; //新元素插入队尾
Q.rear = (Q.rear+1)%MAXQSIZE; //队尾指针+1
return 1;
}
|
4.出队
1
2
3
4
5
6
7
8
9
10
11
12
| int DeQueue(SqQueue &Q,int &e){
//删除Q的队头元素，用e返回其值
if(Q.front == Q.rear) return -1;//队空
e = Q.base[Q.front]; //保存队头元素
Q.front = (Q.front + 1 )%MAXQSIZE； //队头指针+1
return 1;
}
|
5.取队头元素
1
2
3
4
5
6
7
8
| int GetHead(SqQueue Q){
//返回Q的队头元素，不修改队头指针
if(Q.front!=Q.rear) //非空
return Q.base[Q.front];//返回队头
}
|
二、链栈
采用链式存储结构实现的队列称为链队列。
为了使操作更加方便，将队头指针指向链队列的头结点，而队尾指针指向终端结点。
空队列时，front和rear都指向头结点，即front==rear
1.定义
1
2
3
4
5
6
7
8
9
| typedef struct QNode{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
|
2.初始化
构造一个只有一个头结点的空队。
- 生成新结点作为头结点，队头和队尾指针指向此结点
- 头结点的指针域置空
1
2
3
4
5
6
7
8
9
10
11
| int InitQueue(LinkQueue &Q){
//构造一个空队列Q
Q.front = Q.rear =new QNode; //生成新结点作为头结点，队头和队尾指针指向此结点
Q.front->next = NULL; //头结点的指针域置空
return 1;
}
|
3.入队
链队在入队前不需要判断队满，需要为入队元素分配结点空间。
- 为入队元素分配结点空间，用指针p指向
- 将新结点数据域置为e
- 将新结点插入到队尾
- 修改队尾指针为p
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int EnQueue(LinkQueue &Q,int e){
//插入元素e为Q的新队尾元素
p = new QNode; //分配新结点
p->data = e; //把p的数据域置为e
p->next = NULL; Q.rear->next = p;//把新结点插到队尾
Q.rear = p; //修改队尾指针
return 1;
}
|
4.出队
链队在出队前需要判断队列是否为空，不同的是，链队在出队后需要放出队头元素的所占空间。
- 判断队空
- 否则临时保存队头元素的空间，等待释放
- 修改头结点的指针域，指向下一个结点
- 判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值，指向头结点
- 释放原队头元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int DeQueue(LinkQueue &Q,int &e){
//删除Q的队头元素，用e返回其值
if(Q.front==Q.rear) retrun -1; //队空
p = Q.front->next; //p指向队头元素
e = p->data; //e保存队头元素的值
Q.front->next = p->next; //修改头结点的指针域
if(Q.rear == p) Q.rear = Q.front; //最后一个元素被删，队尾指针指向头结点
free(p); //释放原队头元素
return 1;
}
|
5.求队头元素
1
2
3
4
5
6
7
8
| int GetHead(LinkQueue Q){
//返回Q的队头元素，不修改队头指针
if(Q.front!=Q.rear)
return Q.front->next->data;
}
|