从简单的线性数据结构开始：栈与队列

在计算机领域离不开算法和数据结构，而在数据结构中尤为重要与基础的便是两个线性数据结构：栈与队列，本文将简单的介绍栈(Stack)和队列(Queue)的实现

栈与队列

1. 栈 (Stack)是一种后进先出(last in first off，LIFO)的数据结构

2. 队列(Queue)则是一种先进先出 (fisrt in first out，FIFO)的结构

动画如下：

栈

image

队列

image

栈 (Stack)

栈是一种线性结构，与数组相比，栈对应的操作是数组的子集。

它只能从一端添加元素，也只能从一端取出元素(这一端称之为栈顶)。

Stack这种数据结构用途很广泛，在计算机的使用中，大量的运用了栈，比如编译器中的词法分析器、Java虚拟机、软件中的撤销操作（Undo）、浏览器中的回退操作，编译器中的函数调用实现等等。

栈的实现

接口	说明	复杂度
void push(E e)	向栈中加入元素	O(1) 均摊
E pop()	弹出栈顶元素	O(1) 均摊
E peek()	查看栈顶元素	O(1)
int getSize()	获取栈中元素个数	O(1)
boolean isEmpty()	判断栈是否为空	O(1)

说明：push和pop操作在最后面进行，有可能触发resize，但均摊来算是O(1)的。
如果你想了解更多时间复杂度的分析，欢迎关注笔者后续要更新的文章：O(n)说明的是什么问题？

栈的实现可以通过 数组 或者 链表 实现，在这里我们使用 数组来实现上述接口。

在栈的设计中，用户只关注栈顶元素存取和栈长度，因此设计代码如下：

image

读者可以使用 栈这种数据结构去解决LeetCode上的第20号问题：有效的括号，也可以查看前面的文章。

队列 Queue

队列也是一种线性数据结构，与数组相比，队列对应的操作是数组的子集。

只能从一端 (队尾) 添加元素，只能从另一端 (队首) 取出元素。

队列的应用可以在播放器上的播放列表，数据流对象，异步的数据传输结构(文件IO，管道通讯，套接字等)上体现，当然最直观的的就是排队了。

队列的实现

接口	说明	复杂度
void enqueue(E e)	入队	O(1) 均摊
E dequeue()	出队	O(n)
E getFront()	获取队首元素	O(1)
int getSize()	获取队列元素个数	O(1)
boolean isEmpty()	判断队列是否为空	O(1)

入队是从队尾开始，有可能触发resize，因此均摊下来是O(1)。出队是在队首，数组实现每次都要挪动所有元素,O(n)。

image