Data Structures and Algorithms DotNet － 5、栈和队列

Created at 2016-09-15 Updated at 2018-05-01 Category Data Structures and Algorithms Tag Data Structures and Algorithms / DotNet

数据结构与算法－5、栈和队列

栈和队列都是面相表的数据结构。

1、栈

栈被广泛用于编程语言的实现，和表达式计算里。
数据只能从栈顶存储访问。可以将它想象成餐厅的一摞盘子，每个人都会拿走最上面的那个，洗好的盘子也会摞到上面。这就是Last In First Out数据结构。
栈有三个最基本的操作，Pop出栈，Push入栈，Peek取数，相信大家都很清楚了。

1.1、栈的内部实现

1. 内部首先需要一个数据表
2. 同时也需要一个指针，一直指向栈顶元素
3. 入栈时，将数据项压入栈顶，指针向上偏移一位
4. 出栈时，将栈顶数据项移出，指针向下偏移一位
5. 取数时，指针不移动

说到这儿，想起十年前Reinhard读大一的情景。讲数据结构的周老师，在黑板上画栈操作时，内存里的变化。。。。岁月是把杀猪刀啊。
栈的特点是数据进去后，就不再移动，只有指针在动来动去。

1.2、栈的应用

1.2.1、回文判断

回文，就像这样，12521，这在电话号码里称为摆子号。
实现的原理也简单，先将字符串一个字符一个字符从头到尾地压入栈中，再一个一个地出栈，与原字符串中的字符依次比较。

1.2.2、算术运算

1.2.3、进制转换

1.3、

2、队列

队列是First In First Out的数据结构。入队成为Enqueue，出队称为Dequeue。

2.1、队列的实现

1. 内部首先需要一个数据表
2. 入队时，把数据项放在最后一个位置上
3. 出队时，把第一个位置的数据项移出，并将剩下的数据项统统向前移一位

2.2、优先队列

队列中的数据项有不同的优先级，出队时，优先级高的数据项先出队。