数据结构系列：栈？队列？这俩货应该这么理解和掌握

上篇文章 数据结构系列：列表？线性表？这俩货到底什么关系？ 我们主要介绍了线性表的经典实现之一：列表。本篇将主要分享栈和队列这两种线性表结构的特点和一些经典应用。代码都是基于python语言。

文章链接:数据结构系列：列表？线性表？这俩货到底什么关系？

01 栈

1) 概念

栈（stack）是一种数据结构，属于线性表的一种实现。既然是线性表，那么肯定数据之间也有一定的特征，栈的特征如下

-数据项的加入和移除都限制在一端，这个端点一般称之为栈顶

-专业点的描述就是：后进先出（LIFO），越早进入栈结构的数据越晚离开栈

2) 生活中的例子（加深理解）

-一摞盘子，想取的话只能先取最上面的一个，然后下一个，依次类推，但如果想放新的盘子上去，也只能将新盘子放在所有盘子的最上面，然后再摞一个，以此类推。这个（顶端）用来拿或者取盘子的位置，抽象出来一个概念，称之为栈顶。盘子最下面不参与任何的操作，称之为栈底。

-子弹夹，永远只能从一端压入子弹，且从同一端弹出子弹。这样的结果就是，最先压进去的子弹会最后才被弹出，而最后压进去的子弹会最先弹出，这个弹出的位置就称之为栈顶

3) 栈的实现(基于python)

栈的底层同样可以基于数组或者链表实现，但这里为了简单，就基于python的内置结构列表构造一个简单的栈结构。你要知道，作为任何数据结构，用什么实现不重要，重要的是你设计出来的栈结构的接口要满足后进先出的结构特点

这里要强调一下，虽然从代码上看，确实满足了栈的特点，但这并不是一个严格意义上的栈，因为内部的一些列表方法都是可以使用的，而在抽象结构中这些方法应该谨慎地使用。

4) 栈的经典应用

a) 编译器基本功能中的对于各种括号（"(){}[]"）的正确匹配

b) 程序运行中作为数据的隔离

c) 回溯算法

d) 管理计算机内存支持函数和方法的调用

e) 中缀表达式转换为后缀表达式；计算后缀表达式(思路如下)

i) 如果遇到操作数，我们就直接将其输出

ii) 如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。

iii) 如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。

iiii) 如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) “的情况下我们才弹出” ( “，其他情况我们都不会弹出” ( "

iiiii) 如果我们读到了输入的末尾，则将栈中所有元素依次弹出

我这里分享两个通过栈结构实现的经典应用：进制转换和中缀转后缀表达式

5) 10进制转换为2/8/16进制的字符串格式

 6) 中缀转后缀表达式

 7) 计算后缀表达式

 8) 测试代码如下

 02 队列

队列是一种有次序的数据集合，表现为向队列中添加数据时，永远在尾端添加，而移除数据则永远从队首删除，专业化的表述为：先进先出的结构特点（FIFO），越早进入栈结构的数据越早离开栈

1) 生活中的例子（加深理解）

-排队买票，一般情况下，你应该从买票队伍的最后一个位置进入列队

-一台打印机面向多个用户或是程序的情况

2) 队列实现

队列也可以由数组或是链表结构设计实现，数组的实现（循环数组的方法）要难于链表，但是性能更优，这里还是基于python的列表实现

 3) 经典应用

-模拟打印机处理多任务

-模拟道路交通，超市结账排队情况等

-CPU访问

-多个进程访问同一个CPU，新进程会被添加到队列，这个队列就是等待CPU使用的进程

4) 经典实现

约瑟夫/热土豆理论

热土豆问题：几个小朋友，围成一圈，用一个热土豆（或别的什么东西），数一个数就抛给下一个人，每数到3，手上有土豆的人就站出来，然后继续，问哪个位置的人最后剩下？

生产者消费者模型

这应该是最常用的了，经常要构建消息队列

 03 总结

本文基于python，分享了关于栈结构和线性表的相关实现和特点，并辅以相关的代码用各自的结构实现经典应用。希望你对这两种线性表有了一定的了解(数据结构是干嘛的，就是提高效率的，某些场景通过数据结构的套路辅以相关的算法，就会容易很多)

我是一名奋战在编程界的pythoner，工作中既要和数据打交道，也要和erp系统，web网站保持友好的沟通……时不时的会分享一些提高效率的编程小技巧，在实际应用中遇到的问题以及解决方案，或者源码的阅读等等，欢迎大家一起来讨论！如果觉得写得还不错，欢迎关注点赞，谢谢。