2 栈与队列

Wu Jun 2019-05-23 19:48:38
01 数据结构与算法 > 数据结构 > 01 数据结构

一、栈

1 基本概念

2 栈的顺序存储结构 - 顺序栈

1)存储结构

栈是线性表的特例,栈的顺序存储是线性表顺序存储的简化。

2)基本操作
3)两栈共享空间

一个数组来存储两个具有相同数据类型的栈,数组两端为栈底,向中间靠拢。

通常都是当两个栈的空间需求有相反关系时,才使用这样的数据结构。

3 栈的链式存储结构 - 链栈

1)存储结构
2)基本操作
3)顺序栈与链栈对比

4 栈的应用

1)递归

编译器使用栈实现递归

2)四则运算表达式求值

【todo】 https://blog.csdn.net/yzl_rex/article/details/7745341 https://www.jianshu.com/p/a908f067670b

1. 将中缀表达式转化为后缀表达式(栈用来进出运算的符号)。
2. 将后缀表达式进行运算得出结果(栈用来进出运算的数字)。

二、队列

1 基本概念

2 队列的顺序存储结构 - 循环队列

1)存储结构
2)基本操作

3 队列的链式存储结构 - 链队列

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。

2)基本操作
3)循环队列与链队列对比

4 队列的应用

键盘输入显示器输出

排队