数据结构-栈与队列

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

栈与队列概述

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

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

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

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

栈的实现

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

顺序栈

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

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--];
	}
}

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

链栈

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

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

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始终指向队尾元素的下一个元素下面是顺序队列的程序示例。

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,即认为队满,也就是少用一个元素的空间。下面是循环队列的程序示例。

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;
	}
}

栈与递归的关系

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