栈（stack）是限定仅在表尾进行插入和删除操作的线性表。
队列（queue）是一种先进先出（First In First Out）的线性表。
一、栈
1.栈的定义
栈顶：允许插入和删除的一端为栈顶
栈底：另一端
栈是一种后进先出（Last In First Out）的线性表，简称 LIFO 结构。既然栈是一种只允许在尾端进行删除操作的线性表，那么线性表的特性它全部都有。根据存储结构的不同，栈可以分成：顺序栈和链栈。
2.顺序栈
顺序栈其实就是一个数组，只不过需要在声明的时候就确定长度。当头指针 top 指向 -1 的时候，表示空栈。一般将头指针 top 指向尾端的元素。
进栈：需要注意栈是否已经满了（
top == MAX_SIZE - 1）,如果不满，则压入栈，同时 top 指针加一。出栈：需要注意栈是否为空栈（
top == - 1）,如果不空，则出栈，同时 top 指针减一。
时间复杂度均为 O(1)。
3.链栈
栈的链式存储结构，其实就是单链表，只不过它的头指针不再指向头结点，而是指向最尾的节点（栈顶元素）。
进栈：将新节点的 next 指针指向 top，然后将 top 指针指向当前的新节点，链表数量加一。
出栈：保存尾节点，将 top 指针指向 top.next，释放刚刚的尾节点，链表数量减一。
时间复杂度均为 O(1)。
4.用途
Java 对栈（Stack）进行了封装，可以直接使用，栈一般用作函数调用栈或者 Activity 栈。
对于函数调用栈，在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。
5.栈的面试题
-
剑指 Offer 面试题 21：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min() 函数。在该栈中，调用min()，push() 及 pop() 的时间复杂度都是 O(1)。
思路：建立一个数据栈和辅助栈，辅助栈的栈顶每次压入数据栈栈顶和辅助栈栈顶两个元素中的最小值，这样当弹出一个数据栈的时候，对应弹出一个辅助栈，因为两者已经关联过大小了，所以当下一次获取最小值的时候必然跟上次已经弹出的元素无关。如果想要获取最小的元素，直接弹出辅助栈的栈顶即可。
show my code
public class MinStack {
//数据栈
private Stack<Integer> data = new Stack<>();
//辅助栈
private Stack<Integer> min = new Stack<>();
/**
* 压栈
* @param i
*/
public void add(Integer item) {
//数据栈直接入栈
data.push(item);
//辅助栈需要判断，确保入栈的是最小的元素
if(min.isEmpty() || item <= min.peek()) {
min.push(item);
}else {
min.push(min.peek());
}
}
/**
* 出栈
* @return
*/
public Integer pop() {
if(data.isEmpty() || min.isEmpty()) {
return -1;
}
//弹出辅助栈的栈顶
min.pop();
//弹出数据栈栈顶
return data.pop();
}
/**
* 获取栈最小的元素
* @return
*/
public Integer min() {
if(data.isEmpty() || min.isEmpty()) {
return 0;
}
//直接弹出辅助栈的栈顶
return min.peek();
}
/**
* 打印栈
*/
public void printStack() {
System.out.print("栈元素: ");
for(Integer i:data) {
System.out.print(i+" ");
}
System.out.println("");
System.out.println("*************************");
}
}
测试过程及结果
public static void main(String[] args) {
MinStack stack = new MinStack();
stack.add(10);
stack.add(999);
stack.add(23);
stack.add(654);
stack.printStack();
System.out.println("出栈元素："+stack.pop());
stack.printStack();
System.out.println("Min 元素："+stack.min());
stack.printStack();
}
- 剑指 Offer 面试题 22：题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
思路：解决这个问题很直观的想法就是建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。
判断一个序列是不是栈的弹出序列的规律：如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。
show my code
/**
* 检测一个栈的出栈顺序是否存在
* @param push 数字的入栈顺序
* @param pop 数字的出栈顺序
* @return
*/
public static boolean verifyStackPopOrder(int push[],int pop[]){
//验证输入数据是否合法，压栈和出栈的数组的长度必须一致
if(push == null || pop == null || push.length == 0 || pop.length == 0
|| push.length != pop.length){
System.out.println("输入数据不合法");
return false;
}
//构造辅助栈，作为数据栈
Stack<Integer> data = new Stack<>();
//压栈数组的压入位置
int pushIndex = 0;
//出栈数组的出栈位置
int popIndex = 0;
//遍历出栈的数组，假如发现出栈的数据和压栈的栈顶元素相同，就将压栈数据的栈顶元素弹出，否则一直压入，
//直到压栈元素和出栈的栈顶元素相等，弹出压栈的栈顶元素，然后处理下一个出栈的栈顶元素
//未处理完出栈的数组
while(popIndex < pop.length){
//根据一个出栈的栈顶元素，遍历入栈的数组，直到找到相等的元素 或者全部已经入栈
while(pushIndex < push.length && (data.isEmpty() || data.peek() != pop[popIndex])){
//压数据进去数据栈
data.push(push[pushIndex]);
pushIndex ++;
}
//出栈栈顶元素找到和入栈的栈顶元素相同的，数据栈栈顶元素出栈，继续处理下一个出栈元素
if(data.peek() == pop[popIndex]){
data.pop();
popIndex ++;
//如果出栈顺序正确，那么所有数据栈元素都会被出栈，数据栈最后会变为空的栈
}else {
//全部已经压入栈，但是找不到和出栈栈顶元素相等的
return false;
}
}
//假如能运行到这里说明，已经全部压入栈，而且出栈的元素也已经全部弹出，说明顺序是正确的,这个肯定是true
return data.isEmpty();
}
测试过程及结果
public static void main(String[] args){
int[] push = {1, 2, 3, 4, 5};
int[] pop1 = {4, 5, 3, 2, 1};
int[] pop2 = {3, 5, 4, 2, 1};
int[] pop3 = {4, 3, 5, 1, 2};
int[] pop4 = {3, 5, 4, 1, 2};
System.out.println("人工计算为true，程序得出的出栈顺序为: " + verifyStackPopOrder(push, pop1));
System.out.println("人工计算为true，程序得出的出栈顺序为: " + verifyStackPopOrder(push, pop2));
System.out.println("人工计算为false，程序得出的出栈顺序为: " + verifyStackPopOrder(push, pop3));
System.out.println("人工计算为false，程序得出的出栈顺序为: " + verifyStackPopOrder(push, pop4));
int[] push5 = {1};
int[] pop5 = {2};
System.out.println("人工计算为false，程序得出的出栈顺序为: " + verifyStackPopOrder(push5, pop5));
int[] push6 = {1};
int[] pop6 = {1};
System.out.println("人工计算为true，程序得出的出栈顺序为: " + verifyStackPopOrder(push6, pop6));
System.out.println("人工计算为false，程序得出的出栈顺序为: " + verifyStackPopOrder(null, null));
}
二、队列
1.队列的定义
队头：允许删除的一端
队尾：允许插入的一端
队列是一种特殊的线性表，所以队列也是具有顺序存储结构和链式存储结构的。
2.队列的顺序存储结构（循环队列）
为了解决用数组来实现队列的“假溢出”问题，我们一般将顺序存储结构的队列头尾相接，这种把队列的头尾相接的顺序存储结构称为循环队列。
int front; // 头指针
int rear； // 尾指针
队列满的条件：
(rear+1) % QueueSize == front计算队列长度公式：
length = （rear - front + QueueSize）% QueueSize
3.队列的链式存储结构（链队列）
队列的链式结构其实就是链表，只是有头指针和尾指针。当队列为空的时候，头指针和尾指针都指向头结点。
Node front; // 头指针
Node rear； // 尾指针
入队：在链表尾端插入一个节点
出队：删除头结点的后继节点
4.队列的面试题
- 剑指 Offer 面试题 7：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数
appendTail()和deleteHead()，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
private Stack<T> stack1;
private Stack<T> stack2;
思路：我们从一个具体的例子来分析队列的插入和删除元素过程，操作两三次，你就会发现删除一个元素的步骤：当 stack2 中不为空的时候，在
stack2 中的栈顶元素就是最先进入队列的元素，可以弹出。如果 stack2 为空时，我们把 stack1 的元素逐个弹出然后压入 stack2 ，这样就能保证
stack2 的栈元素顺序就是进入队列的顺序。如果要使 stack1 的元素出栈，必须要弹完 stack2 的元素，然后将 stack1 的元素弹出压入 stack2 ，再弹出 stack2 的元素。入队的步骤就是将其压入 stack1 中。
show my code
public class CQueue {
public static void main(String[] args){
CQueue cQueue = new CQueue();
cQueue.appendTail(111);
cQueue.appendTail(222);
cQueue.appendTail(333);
System.out.println("出队: " + cQueue.deleteHead());
System.out.println("出队: " + cQueue.deleteHead());
cQueue.appendTail(444);
cQueue.appendTail(555);
System.out.println("出队: " + cQueue.deleteHead());
System.out.println("出队: " + cQueue.deleteHead());
System.out.println("出队: " + cQueue.deleteHead());
}
//入队的栈
private Stack<Integer> stack1 = new Stack<>();
// 出队的栈
private Stack<Integer> stack2 = new Stack<>();
/**
* 入队
* @param item
*/
public void appendTail(Integer item){
stack1.push(item);
}
/**
* 出队
* @return
*/
public Integer deleteHead(){
//假如 stack2 为空栈，那么当前的队列的头结点肯定在 stack1 中，将 stack1 的元素全部弹出，然后入栈 stack2
if(stack2.isEmpty()){
while(stack1.size() > 0){
Integer i = stack1.peek();
stack1.pop();
stack2.push(i);
}
}
if(stack2.isEmpty()){
System.out.println("队列为空，删除失败");
return -1;
}
Integer head = stack2.peek();
stack2.pop();
return head;
}
}
- 有个类似的题目：用两个队列实现栈。
思路：假设有两个队列Q1和Q2，当二者都为空时，入栈操作可以用入队操作来模拟，可以随便选一个空队列，假设选Q1进行入栈操作，现在假设a,b,c依次入栈了（即依次进入队列Q1）， 这时如果想模拟出栈操作，则需要将c出栈，因为在栈顶，这时候可以考虑用空队列Q2，将a，b依次从Q1中出队， 而后进入队列Q2，将Q1的最后一个元素c出队即可，此时Q1变为了空队列，Q2中有两个元素，队头元素为a，队尾元素为b，接下来如果再执行入栈操作，则需要将元素进入到Q1和Q2中的非空队列，即进入Q2队列，出栈的话，就跟前面的一样，将Q2除最后一个元素外全部出队，并依次进入队列Q1，再将Q2的最后一个元素出队即可。
show my code
public class QueueToStack<T> {
//链队
Queue<T> queueA = new LinkedList<>();
//链队
Queue<T> queueB = new LinkedList<>();
/**
* 入栈
* @param value
*/
public void push(T value) {
if (queueA.size() == 0 && queueB.size() == 0) {//如果两个队列都是空的话,则随便选择一个队列执行入栈操作
queueA.add(value);
}else if (queueA.size() == 0 && queueB.size() != 0){///如果不是两个队列都是为空的话,则选择非空的队列入栈
queueB.add(value);
}else if (queueA.size() != 0 && queueB.size() == 0){
queueA.add(value);
}
}
/**
* 出栈
* @return
*/
public T pop() {
if (queueA.size() == 0 && queueB.size() == 0){
return null;
}
T result = null;
//将非空的队列的元素按顺序出队，转移到空的队列，直到只有一个元素在非空队列
if (queueA.size() == 0 && queueB.size() != 0){
while (queueB.size() > 0){
result = queueB.poll();
if (queueB.size()!=0){
queueA.add(result);
}
}
}else if (queueA.size() != 0 && queueB.size() == 0){
while (queueA.size() > 0){
result = queueA.poll();
if (queueA.size()!=0){
queueB.add(result);
}
}
}
return result;
}
public static void main(String[] args) {
QueueToStack<Integer> stack=new QueueToStack<>();
int tmp=0;
stack.push(1);
stack.push(2);
stack.push(3);
tmp=stack.pop();
System.out.println(tmp);//3
stack.push(4);
tmp=stack.pop();
System.out.println(tmp);//4
tmp=stack.pop();
System.out.println(tmp);//2
stack.push(5);
stack.push(6);
tmp=stack.pop();
System.out.println(tmp);//6
tmp=stack.pop();
System.out.println(tmp);//5
tmp=stack.pop();
System.out.println(tmp);//1
}
}
三、诗和远方
好了,最后两分钟,念几句我在初学栈和队列时写的人生感悟的小诗,希望也能引起你们的共鸣。
人生,就像是一个很大的栈演变。 出生时你赤条条地来到人世,慢慢地长大,渐渐地变老,最终还得赤条条地离开世间。
人生,又仿佛是一天一天小小的栈重现。 童年父母每天抱你不断地进出家门,壮年你每天奔波于家与事业之间,老年你每天独自路跚于养老院的门里屋前。
人生,更需要有进栈出栈精神的体现。在哪里跌倒,就应该在哪里爬起来。无论陷入何等困境,只要抬头就能仰望蓝天,就有希望,不断进取,你就可以让出头之日重现。困难不会永远存在,强者才能勇往直前。
人生,其实就是一个大大的队列演变。无知童年,快乐少年,稚傲青年,成熟中年,安逸晚年。
人生,又是一个又一个小小的队列重现。 春夏秋冬轮回年年,早中晚夜循环天天。变化的是时间，不变的是你对未来执著的信念。
