数据结构 03第三章、栈和队列

第三章、栈和队列目标1、掌握栈和队列的定义和特点2、熟练掌握顺序栈的的基本操作实现算法3、熟练掌握循环队列和链队列的基本操作实现算法栈用铁路调度站表示栈栈的定义和特点1、定义：只能在表的一端（栈顶）进行插入和删除运算的线性表2、逻辑结构：与线性表相同，仍为一对一关系3、存储结构：用顺序栈或链栈存储均可，但以顺序栈更常见4、运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）

的原则5、实现方式：关键是编写入栈和出栈函数队列队列是一种先进先出的线性表.

在表一端插入,在另一端删除。队列的定义和特点1、定义：只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表2、逻辑结构：与线性表相同，仍为一对一关系3、存储结构：用顺序队列或链队存储均可4、运算规则：先进先出5、实现方式：关键是编写入队和出队函数，具体实现依顺序队或链队的不同而不同栈、队列与一般线性表的区别栈、队列是一种特殊（操作受限）的线性表区别：仅在于运算规则不同一般线性表逻辑结构：一对一存储结构：顺序表、链表运算规则：随机、顺序存取栈逻辑结构：一对一存储结构：顺序栈、链栈运算规则：后进先出队列逻辑结构：一对一存储结构：顺序队、链队运算规则：先进先出顺序栈的初始化顺序栈的初始化操作就是为顺序栈动态分配一个预定义大小的数组空间。顺序栈入栈(1)判断是否栈满，若满则出错(2)元素e压入栈顶(3)栈顶指针加1def

push(self,e):#将元素压入栈ifself.top-self.base==self.stack_size:#栈满

raiseException('栈空间已满')self.elem[self.top]=e#元素e压入栈顶,栈顶指针加1self.top+=

1顺序栈出栈(1)判断是否栈空，若空则出错(2)栈顶指针减1，栈顶元素出栈def

pop(self):#将栈顶元素弹出ifself.top==self.base:raiseException('栈已空')self.top-=1#栈顶指针减1，并返回栈顶元素

returnself.elem[self.top]取栈顶元素(1)

判断是否空栈，若空则返回错误(2)

否则通过栈顶指针获取栈顶元素队列的顺序表示front=rear=0空队标志：

front==rear入队：

rear+=

1base[rear]=x出队：

front+=

1x=base[front]顺序队列存在的问题（假溢出）front=0rear=M时再入队—真溢出front≠0rear=M时再入队—假溢出设大小为M链队列链队列的初始化def

init

(self):#构造一个空队列self.front=QNode()#生成新结点作为头结点，队头和队尾指针指向此结点self.rear=self.front链队列的初始化操作就是构造一个只有一个头结点的空队列链队列的入队defen_queue(self,e):#插入元素e为新的队尾元素p=

QNode(e)self.rear.next=p#将新结点插入到队尾self.rear=p#修改队尾指针链队列的出队def

de_queue(self):#删除队头元素，并返回if

self.front==self.rear:#若队列空，则抛出异常raiseException('队列已空')

p=self.front.next#p指向队头元素e=p.data#e保存队头元素的值self.front.next=p.next#修改头结点的指针域if

self.rear==p:#最后一个元素被删，队尾指针指向头结点

self.rear=self.frontreturnp链队列的取队头元素defget_head(self):#返回队头元素，不修改队头指针

ifself.front!=self.rear:#