数据结构-栈和队列

数据结构-栈和队列

一、栈

1.栈是只允许在一端进行插入或删除 *** 作的线性表。

2.链栈通常采用单链表实现，并规定所有 *** 作都是在单链表的表头进行。

3.链栈不存在栈满上溢的情况。

4.栈的应用：括号匹配、表达式求值、递归。

二、队列

1.队列是一种只允许在表的一端进行插入，而在表的另一端进行删除的线性表。

2.链队列实际上是一个同时带有队头指针和队尾指针的单链表。

3.队列的应用：层次遍历、解决主机与外设速度不匹配、资源竞争问题。

4.假溢出：系统作为队列用的存储区还没满，但队列却发生了溢出。

解决办法：

（1）将队列元素向前“平移”，即占用0至rear-front-1；

（2）将队列视为循环队列，即0..m-1；

（3）设标记Tag：

        Tag=0，若因删除导致front=rear，则为队空；

        Tag=1，若因插入导致front=rear，则为队满。