栈（stack）：是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。
栈又称为后进先出（Last In First Out），简称LIFO结构。
栈的插入操作（push），叫作进栈，也称压栈、入栈。类似子弹入弹夹。
栈的删除操作（pop），叫作出栈，也有的叫作弹栈。类似子弹出弹夹。
来张图认识一下这些概念：
栈也是线性表，前一章我们介绍了线性表，所以栈依然拥有顺序存储和链式存储两种结构。 每种结构我们需要重点关注其插入和删除操作的算法实现。也是我们说的进栈和出栈操作，一般用push和pop进行表示。
来一张图认识一下顺序存储结构栈：
java语言实现：
public class TestStack { public static void main(String[] args) { //第一步：创建栈对象的实例 SqStack sqStack = buildSqlStack(2); if (sqStack == null) { System.out.println("创建栈失败"); return; } printStackInformation(sqStack); //第二步：把e这个数据元素压入栈中（进栈） System.out.println("---------插入数据e（进栈）-----------"); ResultEnum insertResultEnum = push(sqStack, "e"); if (insertResultEnum == ResultEnum.ERROR) { System.out.println("error：栈满溢出"); } else if (insertResultEnum == ResultEnum.OK) { printStackInformation(sqStack); } //第三步：把栈顶的有值数据从栈中移除（出栈） System.out.println("---------删除栈顶有值元素（出栈）-----------"); ResultEnum deleteResult = pop(sqStack); if (deleteResult == ResultEnum.ERROR) { System.out.println("error：栈满溢出"); } else if (deleteResult == ResultEnum.OK) { printStackInformation(sqStack); } } private static void printStackInformation(SqStack sqStack) { for (int i = sqStack.data.length - 1; i >= 0; i--) { System.out.println("data:" + sqStack.data[i]); } System.out.println("栈顶 top:" + sqStack.top); } private static int MAXSIZE = 5;//栈的最大可存储空间 /** * 构建一个为顺序存储结构的栈对象的实例 * * @param dataCount * @return */ private static SqStack buildSqlStack(int dataCount) { if (dataCount == 0) { return null; } String[] data = new String[MAXSIZE]; for (int i = 0; i < dataCount; i++) { data[i] = "a" + i; } int top = dataCount - 1; return new SqStack(data, top); } /** * 进栈 */ private static ResultEnum push(SqStack stack, String e) { if (stack.top == MAXSIZE - 1) {//栈满 return ResultEnum.ERROR; } stack.top++; stack.data[stack.top] = e; return ResultEnum.OK; } /** * 出栈 将栈顶那个有值的数据元素删除。 */ private static ResultEnum pop(SqStack stack) { if (stack.top == -1) {//空栈，无元素可删 return ResultEnum.ERROR; } stack.data[stack.top] = null;//被删除的元素置空 stack.top--; return ResultEnum.OK; } /** * 栈的结构定义，可以理解为栈这个对象 */ static class SqStack { String[] data; int top; public SqStack(String[] data, int top) { this.data = data; this.top = top; } } public enum ResultEnum { OK, ERROR; } }案例主要包含三步内容：
第一步：创建栈对象的实例； 第二步：把e这个数据元素压入栈中（进栈）； 第三步：把栈顶的有值数据从栈中移除（出栈）。
输出结果
data:null data:null data:null data:a1 data:a0 栈顶 top:1 ---------插入数据e（进栈）----------- data:null data:null data:e data:a1 data:a0 栈顶 top:2 ---------删除栈顶有值元素（出栈）----------- data:null data:null data:null data:a1 data:a0 栈顶 top:1这种代码，只有动手去写一写，才能更好的理解和消化。
来一张图认识一下链式存储结构栈：
输出结果：
--------------栈顶到栈底依次输出-------------- e a1 a0 栈顶 top:e --------------栈顶到栈底依次输出-------------- a1 a0 栈顶 top:a1迭代函数
private static void useIteration(int count) { int[] arr = new int[count]; arr[0] = 0; System.out.println("第0个月：" + arr[0] + " 对兔子"); arr[1] = 1; System.out.println("第1个月：" + arr[1] + " 对兔子"); for (int j = 2; j < count; j++) { arr[j] = arr[j - 1] + arr[j - 2]; System.out.println("第" + j + "个月：" + arr[j] + " 对兔子"); } }调用：
public static void main(String[] args) { useIteration(7); }输出：
第0个月：0 对兔子 第1个月：1 对兔子 第2个月：1 对兔子 第3个月：2 对兔子 第4个月：3 对兔子 第5个月：5 对兔子 第6个月：8 对兔子递归函数：
private static int useFbi(int i) { if (i < 2) { return i == 1 ? 1 : 0; } return useFbi(i - 1) + useFbi(i - 2); } private static void printFbi(int count) { for (int i = 0; i < count; i++) { System.out.println("第" + i + "个月：" + useFbi(i) + " 对兔子"); } }调用：
public static void main(String[] args) { printFbi(7); }输出：
第0个月：0 对兔子 第1个月：1 对兔子 第2个月：1 对兔子 第3个月：2 对兔子 第4个月：3 对兔子 第5个月：5 对兔子 第6个月：8 对兔子递归法相较于迭代法的代码，要简洁的多。 递归法的推导过程其实也是栈的操作过程，我们都需要找到最顶上的之后开始依次往回计算。
队列（queue）：是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In Frist Out）的线性表，简称FIFO。
允许插入的一端称为队尾，允许删除的一端称为队头。
例如队列（a1,a2,a3,…,an）,那么a1就是队头元素，an是队尾元素。这时我们删除时，总是从a1开始，而插入时，在列在an之后。
来一张图认识一下，队列：
包含一种叫作循环队列，队列的头尾相接的顺序存储结构。 引入两个指针：front指针指向队头元素，rear指针指向队尾元素的下一个位置，rear指针也可以指向剩余的队头位置。
两个计算公式： 如果队列的最大尺寸为QueueSize，那么队列已满的条件是：（rear+1）% QueueSize == front； 通用队列计算长度公式=：（rear-front +QueueSize）%QueueSize；不过笔者简单的推导了一下，|rear-front|%QueueSize 也能得出这个队列的长度。
来一张图看看循环队列的模样：
输出结果：
-----------入队列后的结果如下----------- data:null data:null data:e data:a1 data:a0 队列 front:0 ， rear:3 队列有值数据元素个数（队列长度）：3 -----------出队列后的结果如下----------- data:null data:null data:e data:a1 data: 队列 front:1 ， rear:3 队列有值数据元素个数（队列长度）：2从输出结果中我们可以看到队列的操作，删除从队头开始，新增从队尾插入。
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。
为了操作上更方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点，如下图所示：
空队列时，front和rear都指向头结点，如下图所示：
这段代码调试了一定时间，尤其是入队的时候要当心null。
public class TestLinkQueue { public static void main(String[] args) { LinkQueue linkQueue = new LinkQueue(); linkQueue.enQueue("a0"); linkQueue.enQueue("a1"); linkQueue.enQueue("e"); printStackInformation(linkQueue); linkQueue.deQueue(linkQueue); printStackInformation(linkQueue); } private static void printStackInformation(LinkQueue linkQueue) { System.out.println("--------------队列依次输出--------------"); for (QNode stackNode = linkQueue.front; stackNode != null; stackNode = stackNode.next) { System.out.println(stackNode.data); } } static class LinkQueue { QNode front = new QNode(); // 头指针 QNode rear = new QNode(); // 尾指针 ResultEnum enQueue(String e) { QNode qNode = new QNode(); qNode.data = e; qNode.next = null; if (rear.next == null) { // 队列为空 rear.next = qNode; // 更新队尾和队首指针 front.next = qNode; return ResultEnum.OK; } rear.next.next = qNode;//把拥有元素e的新结点qNode赋值给原队尾结点的后继。 rear.next = qNode;//把当前的qNode设置为队尾结点，rear指向qNode return ResultEnum.OK; } ResultEnum deQueue(LinkQueue linkQueue) { QNode qNode; if (linkQueue.front == linkQueue.rear) { return ResultEnum.ERROR; } qNode = linkQueue.front.next;//将要删除的队头结点暂存给qNode qNode.data = null; linkQueue.front.next = qNode.next;//将原队头结点的后继qNode->next赋值给头结点后继 if (linkQueue.rear == qNode) {//若队头是队尾，则删除后将rear指向头结点 linkQueue.rear = linkQueue.front; } return ResultEnum.OK; } } static class QNode { String data; QNode next; } enum ResultEnum { OK, ERROR; } }输出结果：
--------------队列依次输出-------------- null a0 a1 e --------------队列依次输出-------------- null a1 e栈和队列它们都是特殊的线性表，只不过对插入和删除操作做了限制。
栈（stack）是限定仅在表尾进行插入和删除操作的线性表。
队列（queue）是只允许在一端进行插入操作，在另一端进行删除操作的线性表。
它们均可以用线性表的顺序存储结构和链式存储结构来实现，但都在着顺序存储的一些弊端，因此它们各自有各自的技巧来解决这个问题。
对于栈来说，如果两个相同的数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化的利用数组空间。
对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，时间复杂度从O(n)变成了O(1).
原创不易，求个关注。
微信公众号： 一粒尘埃的漫旅
里面有很多想对大家说的话，就像和朋友聊聊天。 写代码，做设计，聊生活，聊工作，聊职场。 我见到的世界是什么样子的？ 搜索关注我吧。
