数据结构-第二节-堆栈与队列

一、概念：

堆栈与队列也是线性表，但是：

堆栈：只能在一个端进行插入删除，此端称为栈顶。（特点：后来居上）

队列：在一端进行插入（队尾），一端进行删除（队头）。（特点：先进先出）

二、堆栈：

1.顺序栈：

2.多栈共享空间问题：

以两个栈为例：设置两个指针维护栈顶，当两个指针相遇才会栈满。

3.链式栈：

以链表实现堆栈结构，不会出现栈满。

三、队列：

1.循环队列：

（1）假溢出问题：

每出队列一次，需要把整个队列依次往前提1位，否则出现看似溢出，实则前面有空位。

解决：循环队列。

（2）实现：

利用取模确定位置。

2.链式队列：

即用链表形式，实现队列结构。