锲而舍之，朽木不折；锲而不舍，金石可镂。---荀子《劝学》
概念队列，是一种先进先出的结构，类似于我们日常生活中的各种排队
先进先出-队列栈，是先进后出的结构，就像弹匣一下
先进后出-栈如上图，入栈过程1-3-5，出栈顺序就是5-3-1。
用双向链表实现队列和栈数据结构（一）
链表一节中，我们已经知道，双向链表由数据域和节点指针组成，有指向前一个节点的指针（last）和指向后一个节点的指针（next），头结点的last指向空，尾结点的next指向空。
双向链表我们可以用双向链表来实现队列和栈。
双向链表实现队列队列-从尾部插入，从头部取出先定义双向链表：
publicclassNodeT{publicTvalue;publicNodelast;publicNodenext;publicNode(Tvalue){this.value=value;}}
根据队列的特性，先进先出，入队时元素加入到队尾（tail），出队时从队列头部（head）出，因此，入队push和出队poll方法的实现需要定义两个辅助Nodehead和tail即可。
向对列插入元素
一开始head和tail都指向空，
向队列push第一个元素（设为Nodecur）的时候，将元素封装好，让它的next指向空，last指向空。只进来一个节点时，头和尾都指向这个节点：插入第一个元素apush第二个元素b，那么它肯定排在a的后面，出的时候a先出。我们也是将元素b封装成一个链表节点，有前后两个指针，现在要考虑的是将b挂在哪里？
应该是让b挂在a的next上，并且b的next指向null，同时让head节点不动，尾结点tail来到b的位置，如图所示：
插入第二个元素bpush第三个元素c，同样它是一个双向链表节点，让b的next指向它，并且设置它的next为null，同时head位置不动，tail移动到c的位置，如图所示：
插入第三个元素c以此类推，通过上述演示，我们可以得出，每当插入一个元素时，tail向后移动，即需要移动tail指针。
从队列取出元素
再来分析一下弹出元素如何做。由于先进先出，所以从头部弹出元素。
第一次弹出，让头部指向原来头部的next，并将原来头部的value返回
从头部弹出元素并返回继续弹出的话，需要继续移动head到上一次head的next节点，假设是c，并让c的last指向null
继续从头部弹出元素从上述分析可以看出，从队列中取元素时，需要移动的是head节点。
代码实现：
publicclassMyQueue{//借助链表实现队列privateNodehead;privateNodetail;//入队操作publicvoidpush(Tvalue){//封装一个节点，保存其值，然后考虑将该节点挂在哪个位置NodeTcur=newNode(value);if(head==null){//一开始队列为空的时候，插入一个元素后，让head和tail都移动到当前节点head=cur;tail=cur;}else{//头结点不是空的情况，插入后，尾指针移动cur.last=tail;tail.next=cur;tail=cur;}}//出队-获取队列头部元素publicTpoll(){if(head==null){System.out.println("队列空了");returnnull;}Nodecur=head;//让head的下一个节点成为新的头结点if(head==tail){//只有一个元素了head=null;tail=null;}else{//移动headhead=head.next;head.last=null;cur.next=null;}returncur.value;}}
TIP：上述用双向链表实现的是从尾部插入元素，从头部取出元素。双向链表的节点有两个指针，可以灵活的控制从队列的哪个方向插入和取出数据：也就是说可以用双向链表实现双端队列。
实现双端队列
双端队列，既可以从尾部插入头部取出（前面已实现），也可以从头部插尾部取出。
用链表实现队列（还有后面要实现的栈结构），玩的就是head和tail指针，控制好这两个指针的指向就很容易写出来，建议用图画一下加深一下理解。
头部插入尾部取出（先插入的在尾部，所以从尾部取出，符合先进先出）的过程：
队列-从头部插入元素一图胜千言，图上每一个插入动作都体现出了head、tail指针的变化，我们来根据这个图实现双端队列的另一半：
publicclassDoubleEndsQueueT{//上来先定义head和tailprivateNodeThead;privateNodeTtail;//从尾部插入头部取出的实现见MyQueue的push和poll方法，此处略//从头部插入publicvoidaddFromHead(Tvalue){//宗旨：移动headNodeTcur=newNode(value);if(head==null){head=cur;tail=cur;}else{cur.next=head;head.last=cur;head=cur;}}//从尾部取出publicTpopFromBottom(){if(head==null){system.out.println("队列为空");returnnull;}NodeTcur=tail;if(head==tail){head=null;tail=null;}else{tail=tail.last;tail.next=null;cur.last=null;}returncur.value;}}双向链表实现栈
栈的结构和队列在结构上是相似的，就是出入栈和队列的出入在方向上有差别。
我们可以基于上面实现的双端队列（内部是用双向链表实现）来实现栈：只要符合先进后出的规则就行：addFromHead和popFromHead、addFromBottom和popFromBottom。
publicclassMyStackT{privateDoubleEndsQueueTqueue;publicMyStack(){queue=newDoubleEndsQueueT();}publicvoidpush(Tvalue){queue.addFromHead(value);}publicTpop(){returnqueue.popFromHead();}}小结
队列的先进先出和栈的先进后出结构，基于双向链表指针的灵活性，很容易实现。
实现的要诀就是控制头head、尾tail指针的指向，建议画图加深印象。
预览时标签不可点收录于话题#个上一篇下一篇