栈和队列都是什么结构

栈和队列是计算机科学中两个重要的基础数据结构。它们都是一种线性结构，可以用于模拟现实世界中许多物理和抽象概念，例如汽车堵塞、打印机任务、空调等待时间等等。本文将从多个角度分析这两种数据结构。

定义

栈和队列都是由一系列节点组成的序列，不同的是它们对数据的操作方式不同。

栈(Stack)是一种遵循先进后出原则的线性结构。我们可以把栈看成一个桶，先放进去的东西在下面，后放进去的在上面。操作栈的操作只有两个：push（入栈）和pop（出栈）。入栈会将元素加入到栈顶，出栈则会将栈顶元素删除并返回。

队列(Queue)是一种遵循先进先出原则的线性结构。我们可以把队列看成是一个管子，先放进去的叫 front，后放进去的叫 rear。操作队列的操作有三个：enqueue（入队）、dequeue（出队）、peek（返回队列的第一个元素值，但不删除它）。

使用场景

栈和队列有许多实际的应用场景。在现实生活中我们常常看到各种各样的应用，如退栈式抽屉、打印机任务队列等。

在编程中，栈的应用非常广泛，例如函数调用栈、表达式求值、括号匹配等等。函数调用时，函数会被压入栈中，直到函数返回时出栈。表达式求值时，数字被压入栈中，操作符出现时将栈中的数弹出进行相应操作，结果继续入栈。括号匹配时，将左括号入栈，右括号出现时将最近的左括号匹配。这些都需要使用栈这种数据结构。

队列也有许多应用，例如广度优先搜索、消息队列、操作系统的进程调度等。广度优先搜索中，我们需要将前一层的所有节点全部遍历后才能遍历下一层，因此需要使用队列。消息队列是一种可靠地消息传输机制，它们将消息放在队列中，等待消费者按照顺序依次使用。操作系统中，进程会加入到队列中等待分配CPU时间片使用。

实现方式

栈和队列可以通过数组或链表实现，每种方式都有其优缺点。

在数组中实现栈和队列的最大优点是速度快，因为数组的内存连续，可以随机访问某个元素。但是，数组的缺点是大小固定，无法进行动态扩容。当增加到数组大小时，需要将元素从当前数组复制到更大的数组。

链表的最大优点是可以动态扩容，结构可以自由改变，没有固定大小的限制。但是，链表的缺点是访问元素的时间复杂度是 O(n)，需要遍历整个链表。