本文共 1728 字，大约阅读时间需要 5 分钟。

队列和栈的概念

队列：先进先出，从头进，从尾出。

栈：先进后出，从头进，从头出。

所以现在要做的就是用链表来实现：从头进，从头出，从尾进，从尾出这4种方法，即可组合出队列和栈的数据结构。

假设以此插入1、2、3、4、5。

1、从头进

2、从尾进

3、从头出，假设出2个元素

4、从尾出，再出两个元素

代码实现

public class Code_02 {
       //双向链表    static class Node
   
     {
           public T data;        public Node
    
      last;        public Node
     
       next;        public Node(T data) {
               this.data = data;        }    }    //用双向链表分别实现，从头进，从头出，从尾进，从尾出这4种方法    static class DoubleNodeUtil
      
        {
           public Node
       
         head;        public Node
        
          tail; //从头进 public void addHead(T data) { Node
         
           newNode = new Node
          
           (data); if (head == null) { head = newNode; tail = newNode; } else { newNode.next = head; head.last = newNode; head = newNode; } } //从尾进 public void addTail(T data) { Node
           
             newNode = new Node
            
             (data); if (head == null) { head = newNode; } else { tail.next = newNode; newNode.last = tail; } tail = newNode; } //从头出 public T popHead() { if (head == null) { return null; } Node
             
               h = head; if (head == tail) { head = null; tail = null; } else { head = head.next; head.last = null; } return h.data; } //从尾出 public T popTail() { if (tail == null) { return null; } Node
              
                t = tail; if (head == tail) { head = null; tail = null; } else { tail = tail.last; tail.next = null; } return t.data; } } //栈 public static class MyStack
               
                 { private DoubleNodeUtil
                
                  queue; public MyStack() { queue = new DoubleNodeUtil
                 
                  (); } public void push(T value) { queue.addHead(value); } public T pop() { return queue.popHead(); } } //队列 public static class MyQueue
                  
                    { private DoubleNodeUtil
                   
                     queue; public MyQueue() { queue = new DoubleNodeUtil
                    
                     (); } public void push(T value) { queue.addHead(value); } public T poll() { return queue.popTail(); } }}
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://nllrb.baihongyu.com/