数据结构之队列

队列的定义：

只允许在一端进行插入（入队），在另一端删除（出队）的线性表。

举例：

在队末进行入队，在对头进行出队。

队列的特点：

先进入队列的元素先出队（先进先出）

空队列：

对头和队尾元素：

队列的基本操作：

定义队列：

#define Maxsize 10
typedef struct
{
	ElemType data[Maxsize];//用静态数组存放队列元素
	int front, rear;//队头和队尾指针
}SqQueue;
1
2
3
4
5
6

InitQueue(&Q):初始化队列，构造一个空队列Q。

void InitQueue(SqQueue&Q)
{
	Q.rear = Q.front = 0;//初始化时，队头，队尾指针指向0
}
1
2
3
4

DestoryQueue(&Q):销毁队列，销毁并释放队列Q所占用的内存空间。

EnQuquq(&Q,x):入队，若队列Q未满，将x加入，使之成为新的队尾。

bool EnQueue(SqQueue& Q, ElemType x)
{
	if (队列已满)//判断队列是否存满
		return false;
	Q.data[Q.rear] = x;//将x插入队尾
	Q.rear = (Q.rear + 1)%Maxsize;//队尾指针加1取模
	return true;
}
1
2
3
4
5
6
7
8

那么队列已满的条件是不是rear==Maxsize?

那当然不是！

举例：

如果是上述这种情况，虽然此时rear==Maxsize，但是队列中的前几个元素已经出队列了，此时的队列并没有存满。

正确的判断条件是：

方案一：

(Q.rear + 1)%Maxsize//(9+1)%10=0使rear指向0
1

相当于将线性存储在逻辑结构上变成了环状：

队列已满的条件：

队尾指针的再下一个位置是对头，即（Q.rear+1）%Maxsize==Q.front

注意：这里无法将所有的空间都使用，因为如果当rear和front指向同一个位置，那么这不就恰好成为了空队列的条件吗？因此我们必须牺牲一个存储单元。

方案二：

方案三：

当rear指向的是队尾元素时的基本操作：

队列元素个数：

（rear+Maxsize-front）%Maxsize

DeQueue(&Q,&x):出队，若队列Q非空，删除对头元素，并用x返回。

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;
}
1
2
3
4
5
6
7
8
9
10

GetHead(Q,&x):读对头元素，若队列Q非空，则将对头元素赋值给x。

bool GetHead(SqQueue Q, ElemType& x)
{
	if (Q.rear == Q.front)//队空则报错
		return false;
	x = Q.data[Q.front];
	return true;
}
1
2
3
4
5
6
7

QueueEmpty(Q):判队列空，若队列Q为空返回true,否则返回false.

bool QueueEmpty(SqQueue Q)
{
	if (Q.rear == Q.front)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7

队列的链式实现：

typedef struct LinkNode//链式队列结点
{
	ElemType data;
	struct LinkNode* next;
}LinkNode;
typedef struct//链式队列
{
	LinkNode* front, * rear;//队列的对头和队尾指针
}LinkNode;
1
2
3
4
5
6
7
8
9

链队列：链式存储实现的队列

链式队列的初始化：

//带头结点
void InitQueue(LinkQueue& Q)
{
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));//使指针都指向头结点
	Q.front->next = NULL;
}
1
2
3
4
5
6

//不带头结点
void InitQueue(LinkQueue& Q)
{
	Q.front = NULL;
	Q.rear = NULL;
}
1
2
3
4
5
6

链式队列的判空操作：

//带头结点
bool IsEmpty(LinkQueue Q)
{
	if (Q.front == Q > rear)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7
8

//不带头结点
bool IsEmpty(LinkQueue Q)
{
	if (Q.front == NULL)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7
8

链式队列的入队：

//带头结点
void EnQueue(LinkQueue& Q, ElemType x)
{
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	Q.rear->next=s;//新节点插入rear之后
	Q.rear = s;//修改表尾指针
}
1
2
3
4
5
6
7
8
9

//不带头结点
void EnQueue(LinkQueue& Q, ElemType x)
{
	LInkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	if (Q.front == NULL)//在空队列中插入第一个元素
	{
		//修改队头队尾指针
		Q.front = s;
		Q.rear = s;
	}
	else
	{
		Q.rear->next = s;//新节点插入到rear节点之后
		Q.rear = s;//修改rear指针
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

链式队列的出队操作：

//带头结点
bool DeQueue(LinkQueue& Q, ELemType& x)
{
	if (Q.front == Q.rear)//空队
		return false;
	LinkNode* p = Q.front->next;
	x = p->data;//用变量x返回队头元素
	Q.front->next = p->next;//修改头结点的next指针
	if (Q > rear == p)//最后一个节点出队
	{
		Q.rear = Q.front;//修改rear指针
	}
	free(p);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//不带头结点
bool DeQueue(LinkQueue& Q, ElemType& x)
{
	if (Q.front == NULL)//空队列
		return false;
	LinkNode* p = Q.front;//p指向此次出队列的节点
	x = p->data;//用变量x返回队头元素
	Q.front = p->next;//修改front指针
	if (Q.rear == p)//最后一个节点出队
	{
		Q.front = NULL;
		Q.rear = NULL;
	}
	free(p);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

上面我们提到如果是顺序存储，那么当预分配的空间耗尽时，就代表此时队列已满，而对于链式存储来说，一般情况下，队列是不会满的，除非内存不足。

双端队列：

前面我们学习过，栈是只允许从一端插入和删除的线性表，队列是只允许从一端插入，另一端删除的线性表，而双端队列是只允许从两端插入，两端删除的线性表。

判断输出序列的合法性：

若数据元素输入序列为1,2,3,4,则那些输出序列是合法的？那些是非法的？

对数据元素1,2,3,4的输出共有24种：

在栈中：
红色字体代表非法输出，绿色字体代表合法输出！

举例分析：

当为1,2,3,4的顺序时：

数据1，输入再输出，数据2输入再输出，直到数据四完成输出。

当为2,4,1,3的顺序时：

数据2作为第一个元素输出，那么，输入1,2，输出2，接下来要输出数据4，那么，输入3,4，输出4，此时栈中剩余1,3,1是在3之前输入的，要想输出1，就必须先输出3，因此无法完成这组的输出。

其他结果也可按此进行分析。

注：在栈中合法的输出序列，在双端序列中一定合法。

对于计算合法输出序列，我们可以使用卡特兰数：

在输入受限的双端队列中：
红色字体代表非法输出，绿色字体代表合法输出！

在输出受限的双端队列中：

红色字体代表非法输出，绿色字体代表合法输出！

输出/输入受限的双端队列中判断序列的输出是合法还是非法，和在栈中判断方法基本相同，只需要注意栈只能在一端，而输出/输入受限的双端队列虽然可以在两端，但会有不同的限制！