栈和队列

2014/9/16 posted in  算法&数据结构

从数据结构的角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集。他们是操作受限的线性表(其实,更可以认为栈和队列是两种思想,而线性表是它们的具体实现),但在现实上,栈和队列和线性表是大不相同的两类重要的抽象数据类型。

:是限定仅在表尾进行插入或者删除操作的线性表。因此,对栈来说,表尾端有特殊含义,称栈顶,相应的,表头元素称为栈底。

栈又称先进先出(Last In First Out,LIFO)的线性表。

栈的基本操作除了在栈顶进行插入或删除外,还有栈的初始化、判空及取栈顶元素等。

和线性表相似,栈也有两种存储表示方法:

顺序栈:即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。

在应用过程中,当站的空间不够使用的时候再逐段扩大。

链式栈:用链表来模拟栈,灰常节省内存。

栈的应用:

  1. 数制(进制)转换(逆序)
  2. 括号匹配(延时判断)
  3. 行编辑程序(延时处理)
  4. 表达式求值(延时计算)
  5. 走迷宫(DFS)

求迷宫从入口到出口的所有的路径是一个经典的程序设计问题。由于计算解迷宫问题时通常用到的是“穷举求解”的方法,即从入口出发,顺着某一方向向前探索,若能走通,则继续往前走,否则原路返回,换一个方向再继续探索直至所有可能的通路都探索为止。但所求线路必须为简单路径,即在求得的路径上不能重复出现同一通道块。

设定当前位置的初值的入口位置

do{
    若当前位置可通过且没有走过
    则{
        将当前位置插入栈顶;
        若该位置是出口位置,则结束
        否则切换当前位置的相邻方块为新的当前位置;
    }
    否则
        若栈不空且站定位置尚有其他方向未经探索
        则设定新的当前位置为沿顺时针方向旋转找到栈顶位置的下一相邻块
        若栈不空但栈顶位置的四周均不可通
        则{
            删去栈顶位置
            若栈不同,这重新测试新的栈顶位置
                直至找到一个可通 的相邻快或者栈空
        }
}while(栈不空)

其实就是用循环实现DFS,因为DFS用大量递归,且递归本来就慢些,因此,循环将消耗更少的时间。

递归的本质就是栈,只不过使用栈的是编译器,而不是程序员本身。有的数据结构如二叉树、广义表等,由于结构本事固有递归的特性,则它们 的操作可递归地描述,还有的一类问题,虽然本身没有明显的递归结构,但用递归求解比迭代求解更简单,如八皇后问题、Hanoi塔问题。

汉诺塔问题,可以把整个问题抽象化为

  1. 将第1-n-1个盘子通过使用Y、Z移动到Y柱子上
  2. 将第n个盘子移动到Z柱子上
  3. 将1-n-1个盘子通过使用X、Y移动到Z柱子上。

伪代码:

void move(int x,int n,int z)
{
//c为记录步数的全局变量
printf("%d Move disk %d frome %c to %cn",++c,n,x,z);
}

void hanoi(int n,char x,char y,char z)
{
if(n==1)
move(x,1,z);
else
{
hanoi(n - 1,x,z,y);
move(x,n,z);
hanoi(n - 1,y,x,z);
}
}

这就是把大问题化简为为小的问题然后用递归处理的过程。

在汇编程序设计中,主程序和子程序之间的链接及信息交换相类似,在高级语言编制的程序中,调用函数和被调函数之间的链接及信息交换需通过栈来进行。

通常为在一个函数的运行期间,调用一另个函数时,在运行被调用函数之前,系统需要完成3件事:

  1. 将所有的实在参数返回地址等信息传递给被调用函数
  2. 为被调用函数的局部变量非配存储空间
  3. 将控制转移到被调函数入口。

而从被调用函数返回调用函数之前,系统也应完成3件事:

  1. 保证被调函数的计算结果
  2. 释放被调函数的数据区
  3. 依照被调函数保存的返回地址将控制转移到调用函数

当有多个函数构成的嵌套调用时,按照“后调用先返回”的原则,上述函数之间的信息传递和控制转移必须通过“栈”来实现,即系统将整个程序运行时所需的数据空间安排到一个栈里,每当调用一个函数时,就为它在栈顶分配一个存储区,每当从一个函数退出时,就释放他的存储区,则当前正运行的函数的数据区必在栈顶。

这也就是为什么递归深度太大导致“爆栈”。

系统需设立一个“递归工作域”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”,其中包括所有的实在参数,所有局部变量以及上一层的返回地址。

每进入一层递归,就会产生一个新的纪录压入栈顶。每出一层递归,就从栈顶弹出一个工作记录,成这个记录为“活动记录”,并称指示活动记录的栈顶指针为“当前环境指针”。

队列

和栈相反,队列是一种先进先出(First In First Out,FIFO)的线性表,它之允许在表的一端进行插入,而在另一端删除元素。

在队列中,允许拆入的一段叫做队尾,允许删除的一端则称作队头。除了栈和队列之外,还有一种限定性数据结构是双向队列(双端队列)。

两个方向均可以出入,分为左入,左出,右入,右出等操作,但应用远不如栈和队列。

就像链栈一样,队列一样有两种存储结构(相性表的两种实现)

用链表表示的队列简称链队列,一个链队列虽然需要两个分别指向队头和队尾的指针(分别称作头指针尾指针)才能唯一确定。空的链队列的操作即为单向链表的插入和删除操作的特殊情况,只是尚需修改尾指针或头指针。

循环队列

在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附属 两个指针front和rear分别只是队列头元素及队列尾元素的位置。

初始化建空队列时,另front = rear = 0,每当插入新的队列尾元素时,头指针增1,因此,在非空队列中,头指针始终指向队列头元素,而尾指针始终指向尾元素的下一个位置。

但这样的操作有个致命的问题,如果不知道队列元素最多是多少,就需要开尽量大的空间,原因头尾指针只增不减,已经被使用过的空间就此浪费。因此为了更经济,为了存放更多的元素,循环队列诞生了。

将顺序队列臆造为一个环状的空间,指针和队列之间的关系不变,判断“空”还是“满”,可有两种处理方法:1.设另一个标志位以区别队列是“空”还是“满”;2.少用一个元素空间,约定以队列头指针在队列尾的下一位置作为队列满的状态。

队列还有很多应用,也有很多拓展,不如优先队列,在先进先出的基础上,为每个元素添加优先级,使队列中优先级高的先先出,在BFS等搜索中,可以进行优化。