数据结构基础之队列

  上一篇博客中我们总结了栈的相关知识,其实,在数据结构的教材中栈和队列通常是放在同一章进行讲解的,因为他们都是操作受限的线性表,只是具体的限制不同。队列是只允许在表的一段进行插入操作,而在另一端进行删除操作的线性表,它的应用也是比较广泛的,比如在操作系统的处理进程对CPU资源的竞争以及我们常常提及的优先级队列等等。

队列的基本概念

  定义:只允许在表的一段进行插入操作,而在另一端进行删除操作的线性表。

  队头:允许进行删除操作的一端。

  队尾:允许进行插入操作的一端。

顺序队列

8-1

  采用顺序存储结构,即在内存中用一组地址连续的存储单元一次存放从队头到队尾的数据元素,同时设置两个指针 frontrear 分别指示队头元素和队尾元素的位置。

1
2
3
4
typedef struct{
ElemType data[MAXSIZE]; //存放数据元素的数组
int front,rear; //头尾指针
}SeqQueue;

  队头指针:指示队头元素所在位置。

  队尾指针:指示队尾元素的下一个位置。

  入队操作:rear = rear + 1

  出队操作:front = front + 1

  当 rear = MAXSIZE 时,队列不一定真的占满整个数组空间,因为不管入队还是出队指针都是加,头指针一直加就会使得数组的前端可能出现许多空的单元,这种现象称为假溢出。为了充分利用数组空间,于是引入了循环队列。

循环队列

8-2

  将队列的存储空间看成一个环状的空间,即将队列的首、尾的位置连接起来形成的结构称为循环队列。

  入队操作:Q->rear = (Q->rear + 1) % MAXSIZE

  出队操作:Q->front = (Q->front + 1) % MAXSIZE

区分队空还是队满的方式

  1、牺牲一个单元来区分队空和队满,约定以队头指针在队尾指针的下一个位置作为队满的标志,则有:

1
2

  2、类型中增设表示元素个数的数据成员,则有:

1
2
3
队空满条件:Q->size == 0
队满条件:Q->size == MAXSIZE

  3、类型中增设tag数据成员,则有:

  tag 等于 0 的情况下,若因删除导致 Q->front == Q->rear 则为队空,tag 等于 1 的情况下,若因插入导致 Q->front == Q->rear 则为队满。

基本操作实现

  下面例子采用第一种处理方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define false 0
#define true 1
#define MAXSIZE 100
typedef struct{
ElemType data[MAXSIZE]; //存放数据元素的数组
int front,rear; //头尾指针
}SeqQueue;
/*********初始化队列*********/
void InitQueue(SeqQueue *Q){
Q->front = Q->rear = 0;
}
/*******判断队列是否为空*******/
int QueueEmpty(SeqQueue *Q){
if(Q->front == Q->rear)
return true;
else
return false;
}
/*************入队操作*************/
int EnQueue(SeqQueue *Q,ElemType e){
if((Q->rear+1)%MAXSIZE == Q->front) //队满
return false;
Q->data[Q->rear] = e; //将e插入队尾
Q->rear = (Q->rear+1)%MAXSIZE; //修改尾指针
return true;
}
/*************出队操作**************/
int DeQueue(SeqQueue *Q,ElemType *e){
if(Q->front == Q->rear) //队空
return false;
*e = Q->data[Q->front]; //得到删除的队头元素
Q->front = (Q->front+1)%MAXSIZE; //修改头指针
return true;
}
/*************取队头元素**************/
int GetFront(SeqQueue *Q,ElemType *e){
if(Q->front == Q->rear) //队空
return false;
*e = Q->data[Q->front]; //取得队头元素
return true;
}
int main()
{
SeqQueue Q;
InitQueue(&Q);
....
进行入队、出队、判空等操作
....
return 0;
}

链式队列

8-3

  采用链表形式的队列,队列中每个元素对应链表中的一个结点的,并设置两个分别指向队头和队尾的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define false 0
#define true 1
typedef struct LinkQNode{
ElemType data; //数据域
struct LinkQNode *next; //指针域
}LinkQNode;
typedef struct{
LinkQNode *front; //队头指针
LinkQNode *rear; //队尾指针
}LinkQueue;
/*********初始化队列*********/
void InitQueue(LinkQueue *Q){
LinkQNode *p = (LinkQNode *)malloc(sizeof(LinkQNode)); //构建头结点
if(p == NULL) //存储空间分配失败
return false;
Q->front = Q->rear = p; //队头指针和队尾指针都指向头结点
Q->front->next = NULL; //头结点指针域至为空
return true;
}
/*******判断队列是否为空*******/
int QueueEmpty(LinkQueue *Q){
if(Q->front == Q->rear)
return true;
else
return false;
}
/*************入队操作*************/
int EnQueue(LinkQueue *Q,ElemType e){
LinkQNode *p = (LinkQNode *)malloc(sizeof(LinkQNode)); //构建新结点
if(p == NULL) //存储空间分配失败
return false;
p->data = e; //设置新结点数据域
p->next = NULL; //设置新结点指针域
Q->rear->next = p; //将新结点插入队尾
Q->rear = p; //修改队尾指针
return true;
}
/*************出队操作**************/
int DeQueue(LinkQueue *Q,ElemType *e){
LinkQNode *p;
if(Q->front == Q->rear) //队列空
return false;
p = Q->front->next; //得到第一个结点
*e = p->data; //得到删除结点的值
Q->front->next = p->next; //结点p出队
if(Q->rear == p) //队列中只有一个结点p,则出队后队列为空
Q->rear = Q->front;
free(p); //释放存储空间
return true;
}
/*************取队头元素**************/
int GetFront(LinkQueue *Q,ElemType *e){
LinkQNode *p;
if(Q->front == Q->rear) //队空
return false;
p = Q->front->next; //得到第一个结点
*e = p->data; //得到第一个结点的值
return true;
}
int main()
{
LinkQueue Q;
InitQueue(&Q);
....
进行入队、出队、判空等操作
....
return 0;
}

双端队列

8-4

  双端队列是指允许两端都可以进行入队和出队操作的队列。

  输出受限的双端队列:允许在一端进行插入和删除,但在另一端只允许插入的双端队列。

  输入受限的双端队列:允许在一端进行插入和删除,但在另一端只允许删除的双端队列。

  尽管双端队列看起来似乎比栈和队列更灵活,但实际上在应用程序中远不及栈和队列有用,所以在这里就不详细的介绍啦!

坚持原创技术分享,您的支持将鼓励我继续创作!