队列和栈的结构非常经典，在面试中会经常出现他们的变种题。
比如，实现图的宽度优先遍历，但是要求用栈实现；实现图的深度优先遍历，但是要求用队列实现。
这个题比较阴的地方就是图的宽度优先遍历通常是用队列来实现的，而深度遍历使用栈实现，所以，这里需要我们做一个转换：
先用队列来实现栈，然后用这个队列实现的栈实现宽度优先遍历，从而达到用栈实现图的宽度优先遍历的目的；
对于深度优先遍历，先用栈来实现队列，然后用这个栈实现的队列实现深度优先遍历。
这篇文章不是讨论图这种结构的，主要实现以下两种算法：
用栈结构实现队列结构用队列结构实现栈结构用栈实现队列要想实现队列，我们要考虑的是怎样达到数据的先进先出。
而栈是先进后出的结构，于是我们可以用两个栈来实现：push栈和pop栈。
push栈弹出依次压入到pop栈对于我们要实现的特殊队列，入队的时候压入数据到push栈，同时观察判断pop栈是否为空。
插入一个3，add(3)，此时pop栈为空，需要将push栈中的数弹出压入到pop栈，直到push栈为空：
add(3)插入一个2，add(2)，此时pop栈不为空，无需弹出push栈和压入pop栈：
add(2)同理，依次add(5)和add(7)：
依次add(5)和add(7))此时，我要从队列中取出数据，poll，弹出pop栈，此时判断一下pop栈是否为空，若为空，则需要将push栈数据全部倒出压入到pop栈：
队列poll继续从队列取数：
队列poll从上述add和poll的过程我们可以得出一个结论：
无论队列add还是poll都要看一下pop栈是否为空，如果pop栈为空了，则需要弹出push栈的数据压入到pop栈，直到push栈为空。
即：
push栈数倒入到pop栈时要一次性倒完当pop栈不为空时，不需要压入push栈的数据这样就能保证先进先出了。
因此我可以抽象出一个弹出push栈数据压入pop栈的方法：
publicvoidpushToPop(){if(popStack.isEmpty()){while(!pushStack.isEmpty()){popStack.push(pushStack.pop());}}}
用栈实现队列的完整代码：
publicclassMyQueueWithStack{privateStackIntegerpushStack;privateStackIntegerpopStack;publicMyQueueWithStack(){this.pushStack=newStack();this.popStack=newStack();}publicvoidpushToPop(){if(popStack.isEmpty()){while(!pushStack.isEmpty()){popStack.push(pushStack.pop());}}}publicvoidadd(intvalue){pushStack.push(value);pushToPop();}publicintpoll(){if(popStack.isEmpty()pushStack.isEmpty()){thrownewRuntimeException("队列空了！");}pushToPop();returnpopStack.pop();}}用队列实现栈
有了用两个栈实现队列的经验，我们可以再来试一下如何用两个队列实现栈。
终极目的是实现数据的先进先出，也就是先添加的数据，在取数的时候先取出。
下面先用图来演示一遍过程：
用两个队列实现栈的后进先出结构上图演示的数据入栈出栈过程：
入栈：1，2，出栈：2
入栈：3，4，5，出栈：5
入栈：无，出栈：4
...
所以，这一过程实现了栈的后进先出，达到了用队列实现栈的目的(用两个队列来回倒数据)。
要点：定义两个队列，实现的这种栈在push时往非空的那个队列（如果都为空，则选择其中一个）插入数据，pop时将非空的队列数据取出并依次插入到原来空的那个队列，只留下最后一个元素，将这个元素取出返回，这样原来非空的就变成了空队列了。---每次操作无论push还是pop均有一个队列是空的。
把上面我分析的思路翻译成代码就是这样的：
publicclassMyStackWithQueueT{privateQueueTqueue;privateQueueThelp;publicMyStackWithQueue(){this.queue=newLinkedList();this.help=newLinkedList();}publicvoidpush(Tvalue){if(queue.isEmpty()help.isEmpty()){queue.add(value);}if(!queue.isEmpty()){queue.add(value);}if(!help.isEmpty()){help.add(value);}}publicTpop(){QueueTtemp=newLinkedList();if(!queue.isEmpty()){temp=queue;while(queue.size()1){help.add(queue.poll());}}elseif(!help.isEmpty()){temp=help;while(help.size()1){queue.add(help.poll());}}returntemp.poll();}}延伸：Java中的List和QueueJava集合框架图（无Map）List集合
List集合元素有明确的上一个和下一个元素，也存在明确的第一个和最后一个元素。
List集合最常用的是ArrayList和LinkedList两个集合类。
ArrayListArrayList的容量可以改变，非线程安全集合。其内部实现用数组进行存储，集合扩容时会创建一个更大的数组控件，把原有数据复制到新数组中。
publicclassArrayListEextendsAbstractListEimplementsListE,RandomAccess,Cloneable,java.io.Serializable{privatestaticfinallongserialVersionUID=L;/***Defaultinitialcapacity.*/privatestaticfinalintDEFAULT_CAPACITY=10;/***Sharedemptyarrayinstanceusedforemptyinstances.*/privatestaticfinalObject[]EMPTY_ELEMENTDATA={};/***Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances.We*distinguishthisfromEMPTY_ELEMENTDATAtoknowhowmuchtoinflatewhen*firstelementisadded.*/privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};/***ThearraybufferintowhichtheelementsoftheArrayListarestored.*ThecapacityoftheArrayLististhelengthofthisarraybuffer.Any*emptyArrayListwithelementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA*willbeexpandedtoDEFAULT_CAPACITYwhenthefirstelementisadded.*/transientObject[]elementData;//non-privatetosimplifynestedclassaccess//......}
ArrayList支持对元素的快速随机访问，但是插入和删除的速度较慢，因为插入和删除的过程需要移动元素。
LinkedListLinkedList本质上是一个双向链表。
publicclassLinkedListEextendsAbstractSequentialListEimplementsListE,DequeE,Cloneable,java.io.Serializable{transientintsize=0;/***Pointertofirstnode.*Invariant:(first==nulllast==null)
*(first.prev==nullfirst.item!=null)*/transientNodeEfirst;/***Pointertolastnode.*Invariant:(first==nulllast==null)
*(last.next==nulllast.item!=null)*/transientNodeElast;//...}
它和ArrayList很明显的区别就是，LinkedList的插入和删除速度快，而随机访问速度则很慢。
另外，LinkedList还实现了Deque接口（double-endedqueue，双端队列），Deque同时具有队列和栈的性质，因为它可以先进先出，也可以先进后出。
LinkedList将零散的内存单元通过附加引用（其内部定义了指向前一个和后一个元素的first和last指针）的方式关联起来，形成按链路顺序查找的线性结构，内存利用率较高。
Queue集合前面几篇文章一直在探讨队列、栈这些数据结构，队列的**先进先出（FIFO）**应该深入我们的脑海中---队列只允许从一端进行取数，在另一端进行插入数据。
从棣属于juc包下的BlockingQueue出现以来，队列就应用于各种高并发场景中，鉴于其先进先出的特性记忆阻塞操作的特点，它经常被用作数据缓冲区。
BlockingQueue小结本文介绍了栈和队列的互转，这两个算法技巧可以帮助解决一些奇怪的算法题~
Java中常用的List和Queue集合多和队列和栈数据结构有关系，建议手绘一张集合框架图，时不时的想一下他们的实现，这将对我们很有帮助。
预览时标签不可点收录于话题#个上一篇下一篇