这是数据结构类重新复习笔记的第 二 篇，同专题的其他文章可以移步：https://www.jianshu.com/nb/39256701
栈（stack）
栈（stack）是限制插入和删除操作只能在末尾位置上进行的表，该末尾成为栈的顶（top）。是一种后进先出的表（LIFO，Last In First Out）。
栈
栈的实现
- 链表实现：使用单向链表实现
- 数组实现：使用数组实现，是更加常用的方式。由C++中的vector中的back、push_back和pop_back可以很简单地实现一个栈。每个栈需要一个用于存储栈数据的数组（stackArray）和一个记录栈顶索引的值（topOfStack）（当空栈时索引为-1）
常用操作
-
push：入栈操作，将topOfStack+1，然后令stackArray[topOfStack]=newElement; -
pop：出栈操作，outElement=stackArray[topOfStack]，然后将topOfStack-1 -
top：返回栈顶元素，返回stackArray[topOfStack]
所有操作均为常数时间O(1)运行
队列（Queue）
队列也是表，是一种先进先出（First In First Out，FIFO）的数据结构，入队列的一端成为队尾，出队列的一端成为队头。
队列
队列的实现
队列也可以使用链表来实现，但通常使用循环数组来实现。
一个队列需要一个用于存储队列中数据的数组queueArray和两个位置front、back，用于记录队列的两端。为了判定队列是否空还是满，通常还增设一个元素currentSize来记录队列中现有的元素个数。
常用操作
-
enqueue：入队列
back = (back+1)%queueArray.size();
queueArray[back]=newElement;
currentSize++;
-
dequeue：出队列
outElement = queueArray[front];
fornt = (front+1)%queueArray.size();
currentSize--;
-
back：返回队尾元素，直接返回queueArray[back] -
front：返回队头元素，直接返回queueArray[front]
以上操作均以常数时间O(1)运行
转载请注明出处，本文永久更新链接：https://blogs.littlegenius.xin/2019/08/08/【数据结构】二栈与队列/
