摘要 自上一章讲述了数据结构最基本的内容线性表之后,本章继续讲述线性表的两个特殊现象,但是有着极其重要作用的栈与队列。总而言之,栈与队列是操作受限的线性表,其逻辑定义和存储结构与线性表一模一样,但是定义在其上的操作却有着一定的特殊性。首先,我们只需要了解,栈是一种后进先出结构,而队列则是一种先进先出结构,其它详细信息将在接下来的内容中讲述。

栈与队列概述

栈属于一种后进先出的结构,只允许在同一端进行插入和删除元素,这一称之为栈顶;而队列属于先进先出的线性结构,只允许在一端插入元素,在另一端删除元素,其中插入元素的一端称之为队尾,删除元素的一端称之为队头。

栈类似于生活中的叠盘子,洗完的盘子,只能从顶部开始叠,要取盘子上菜,也只能从顶部开始一个一个地取,栈的用途非常广泛。栈的应用例子如下:

  • 数制转换(取模)
  • 文本编辑器括号匹配问题{[]},只能是右括号匹配左括号
  • 文本编辑,先存入字符缓冲区(栈),再刷新至文本区
  • 迷宫求解(穷举法,配合回退)
  • 算数表达式求值的算符优先算法

在我们经常使用的递归算法,其底层实现与栈也有着不可分割的关系。队列在操作系统以及线程进程之间的通信都非常重要。

栈的实现

按其存储结构,栈的实现可以划分为顺序栈和链式栈。顺序栈就是操作受限的顺序表,由于栈只有栈顶一端需要不断变化,因此我们在定义栈的结构时,通常定义一个栈顶指针便于运算。

顺序栈

在顺序栈中,栈顶指针顺序移动,因此类似于数组中的下标,其实顺序栈的底层就是数组。下面是顺序栈的程序示例。

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
class SeqStack{
public static final int STACK_SIZE = 10;
private int data[] = new int[STACK_SIZE];
private int top = -1;

public int length(){
return top+1;
}

public boolean isFull(){
return (top == STACK_SIZE-1);
}

public boolean isEmpty(){
return (top == -1);
}

public boolean push(int val){
if(this.isFull())
return false;
data[++top] = val;
return true;
}

public int pop(){
if(this.isEmpty())
return -1;
return data[top--];
}
}

从以上程序示例可以看出,栈相对线性表,其插入和删除元素有着特殊的含义,分别称之为压栈和弹栈操作。在整个操作过程中修改的只是栈底指针的顺序滑动,因此理解起来非常简单。

链栈

使用链式存储结构来表示栈,其底层就不是数组了,而且插入元素的个数也将不受限制,因此没有判断栈是否为满的操作。

通常链式存储结构的结点都包含一个数据域和指针域,链栈也一样。定义了链栈结点之后,我们为了定义链,同样由于只有栈顶指针发生变化,我们只需要定义一个栈顶指针结点即可。下面是链式栈的程序示例。

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
class LinkStack{

private class StackNode{
private int data;
private StackNode next;
}

private StackNode top = null;

public int length(){
int length = 0;
StackNode p = top;
while(p != null){
length++;
p = p.next;
}
return length;
}

public boolean isEmpty(){
return (this.length() == 0);
}

public boolean push(int val){
StackNode oldTop = this.top;
StackNode newNode = new StackNode();
newNode.data = val;
newNode.next = null;
this.top = newNode;
this.top.next = oldTop;
return true;
}

public int pop(){
int data = this.top.data;
top = top.next;
return data;
}
}

上述程序示例以内部类的形式定义链栈结点,初始化设栈顶指针为空,对应顺序栈中top=-1,进行压栈操作时,需要生成新的栈顶结点,修改栈顶指针指向该位置,修改栈顶指针的next指向上一个栈顶指针位置。

队列的实现

与栈的实现一样,队列也可以分为顺序队列和链式队列。但是对于队列,这里为了简单起见,我只介绍顺序队列,另外还向大家介绍一种特殊的顺序队列即循环队列。

队列在插入元素的时候,只能在队尾插入,因此需要定义一个队尾指针不断地移动来插入元素;另外在删除元素的时候,只能在队头删除,因此还需要定义一个队头指针向后移动来删除元素。

顺序队列

在顺序队列中,这两个指针也类似于数组的下标。其中队头指针front始终指向队头元素,即队列中的第一个元素,队尾指针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
class SeqQueue{
public static final int QUEUE_SIZE = 10;
private int data[] = new int[QUEUE_SIZE];
private int front = 0;
private int rear = 0;

public int length(){
return rear-front;
}

public boolean isEmpty(){
return (front == rear);
}

public boolean isFull(){
return (rear == QUEUE_SIZE-1);
}

public boolean enQueue(int val){
if(this.isFull())
return false;
data[rear++] = val;
return true;
}

public int deQueue(){
if(this.isEmpty())
return -1;
return data[front++];
}
}

从以上顺序队列的程序示例,也可以看出,队列相对于线性表,其插入和删除操作也有着特殊的定义,分别称之为入队和出队。当队头和队尾指针相等的时候,队列为空。另外,由于在插入元素的时候,队尾指针不断向后移动直至最大位置,删除元素的时候,队头指针也是不断向后移动追赶队尾指针,由于移动方向一样,这就造成了,队尾指针已经到达最大位置,但实际上只包含几个元素,也就是一种假上溢现象,即队列空间并没有好好利用,为了克服队列的假上溢现象,引入循环队列的概念,下面为大家介绍循环队列。

循环队列

循环队列为了克服假上溢现象,定义插入和删除的规则为,队尾指针和队头指针并不只是一直向后移动达到最大位置就停止,而是到达最大位置之后,队列的第一个位置为空,队尾指针又可以循环到队列的第一个位置开始插入,队头指针在删除元素的时候也一样。这里的移动队头和队尾指针就不仅仅是加1操作,而是加1之后对队列大小进行取模,而且,这种情况下,front==rear并不能判断队列是空还是满,因此定义在插入元素的时候如果满足(rear+1)%QUEUE_SIZE == front,即认为队满,也就是少用一个元素的空间。下面是循环队列的程序示例。

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
class CirQueue{
public static final int QUEUE_SIZE = 5;
private int data[] = new int[QUEUE_SIZE];
private int front = 0;
private int rear = 0;

public int length(){
if(rear > front)
return (rear-front)%QUEUE_SIZE;
else
return (QUEUE_SIZE-front)+rear;
}

public boolean isEmpty(){
return rear == front;
}

public boolean isFull(){
return (rear+1)%QUEUE_SIZE == front;
}

public boolean enQueue(int val){
if(this.isFull())
return false;
data[rear] = val;
rear = (rear+1)%QUEUE_SIZE;
return true;
}

public int deQueue(){
if(this.isEmpty())
return -1;
int val = data[front];
front = (front+1)%QUEUE_SIZE;
return val;
}
}

栈与递归的关系

最后讲述一下,递归操作时,栈的作用:

  • 调用函数时:系统将会为调用者构造一个由参数表和返回地址组成的活动记录,并将其压入到由系统提供的运行时刻栈的栈顶,然后将程序的控制权转移到被调函数。若被调函数有局部变量,则在运行时刻栈的栈顶也要为其分配相应的空间。因此,活动记录和这些局部变量形成了一个可供被调函数使用的活动结构。

  • 被调函数执行完毕时:系统将运行时刻栈栈顶的活动结构退栈,并根据退栈的活动结构中所保存的返回地址将程序的控制权转移给调用者继续执行。