数据结构——栈和队列

栈:只允许在表的末端进行插入和删除的线性表

特点:FILO。

栈的操作:进(入)栈(PUSH)、出栈(POP)、栈顶(TOP)、置空(setEmpty)、判断是否为空(isEmpty)、栈满(isFull)。

栈的表示方法:数组、单链表。

栈与递归

递归的定义:若一个对部分地包含它自己,或用它自己给自己定义,则称这个对象是递归;若一个过程直接或间接地调用自己,则称这个过程是递归的过程。

以下三种情况常常用到递归的方法:定义是递归的;数据结构是递归的;问题的解法是递归的。

问题的解法是递归的:汉诺塔(Tower of Hanoi)问题的解法——有3根票号为A、B、C的柱子,A柱上又叠着64个从小到大排放的盘子。目的是要将A柱的盘子全部移到C柱上。移动条件是一次只能移动一个盘子,移动过程中大盘子不能放在小盘子上面。

求解汉诺塔问题的递归算法

若n=1,将盘子直接从A柱移到C柱。

否则,执行以下三步:

用C柱做过滤,将A柱上的(n-1)个盘子移到B柱上;

将A柱上最后一个盘子直接移到C柱上;

用A柱做过渡,将B柱上的(n-1)个盘子移到C柱上。

用栈将递归转换为非递归

 队列

定义:队列是只允许在一端删除,在另一端插入的线性表。

允许删除的一端叫做队头(front),允许插入的一端叫做队尾(rear)。

特点:先进先出(FIFO)。

队列的操作:

入队,出队,判断是否为空,队列满。

队列的数组表示(循环队列)

入队:在rear处加入数据,rear=(rear+1)%SIZE

出队:在front处取出数据,front=(front+1)%SIZE

队满:(rear+1)%SIZE==front

队空:rear==front

 

队列的单链表表示

队列的数组个表示可能队列满。队列的单链表表示无队列满问题。入队在表尾进行插入操作。出队在表头进行删除操作。

队列的应用,电路布线参见这篇文章:《使用队列求电路图的最短布线》

未经允许不得转载:TacuLee » 数据结构——栈和队列

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址