数据结构--栈和队列

1. 栈的定义

是限定仅在表尾进行插入或删除操作的线性表

表尾即栈顶Top

表头即栈底Base

特点：后进先出

2. 栈的存储结构

栈的顺序存储：顺序栈

栈顶链式存储：链栈

2.1 顺序栈

设置Top指针：top指在栈顶元素之后一个位置

设置Base指针：指示栈底元素在顺序的位置

stackszie表示栈可使用的最大容量

2.2 链栈

链栈是运算受限的单链表，只能在链表表头进行操作

链表的头指针是栈顶

不需要头结点

基本不存在栈满的情况

空栈相当于头指针指向空

插入和删除仅在栈顶处进行

3.栈的应用

数制转换

括号匹配

迷宫求解（深度优先搜索？

表达式求值

后缀表达式

?

4.队列的定义

是限定只能在表的一段（表尾）进行插入，在表的另一端（表头）进行删除的线性表

队尾rear：允许插入的一端

队头front：允许删除的一端

先进先出

5.队列的存储结构

队列的顺序表示

5.1 循环队列

1.初始化建空队列时，令front = rear =0

2. 每当插入新的队列尾元素时，队尾指针增1

3. 每当删除队列头元素时，头指针增1

头指针始终指向队列头元素

尾指针始终指向队列尾元素的下一个位置

?

约定：队列头指针在队列尾指针的下一位置上时，作为队列呈满状态的标志

循环队列的队满条件：(sq. rear +1)%maxsize == sq.front

链队列结构