链表LinkedList实现队列(Java)

矫情吗；* 2023-07-01 08:42 109阅读 0赞

# 链表LinkedList实现队列 #

**Queue.java（队列接口）**

public interface Queue<E> {
        
    	
    	void enqueue(E e);//入队
    	E dequeue();//出队
    	E getFront();//获取队首元素
    	int getSize();//获取队列中元素个数
    	boolean isEmpty();//判断队列是否为空
    }

**LinkedListQueue.java（链表队列）**  
带尾节点的链表实现队列，没有设置虚拟头节点

//链表头是队列头，出队O(1);链表尾是队列尾,入队O(1)    
    public class LinkedListQueue<E> implements Queue<E> {
        
    	private class Node {
        // 内部类将节点设为私有 隐藏实现细节
    		public E e;// 元素
    		public Node next;// next指针
    
    		public Node(E e, Node next) {
        
    			this.e = e;
    			this.next = next;
    		}
    
    		public Node(E e) {
        
    			this(e, null);
    		}
    
    		public Node() {
        
    			this(null, null);
    		}
    
    		@Override
    		public String toString() {
        
    			return e.toString();
    		}
    	}
    
    	private Node head, tail;// 定义头节点，尾节点
    	private int size;
    
    	public LinkedListQueue() {
        
    		// TODO Auto-generated constructor stub
    		head = null;
    		tail = null;
    		size = 0;
    	}
    
    	@Override
    	public void enqueue(E e) {
        
    		// TODO Auto-generated method stub
    		if (tail == null) {
         // tail == null是尾节点为空，也就是队列为空的时候，否则tail应该指向尾节点
    			tail = new Node(e);// 传入要插入的节点
    			head = tail;
    		} else {
        
    			tail.next = new Node(e);// 如果tail不为空，在tail.next处插入节点
    			tail = tail.next;// tail后移
    		}
    		size++;
    	}
    
    	@Override
    	public E dequeue() {
        
    		// TODO Auto-generated method stub
    		if (isEmpty())
    			try {
        
    				throw new Exception("队列为空");
    			} catch (Exception e) {
        
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		Node retNode = head;// 出队的节点就是head所指向的节点
    		head = head.next;// head后移
    		retNode.next = null;
    		if (head == null)// 如果队列中只有一个元素
    			tail = null;
    		size--;
    		return retNode.e;
    	}
    
    	@Override
    	public E getFront() {
        
    		// TODO Auto-generated method stub
    		if (isEmpty())
    			try {
        
    				throw new Exception("队列为空");
    			} catch (Exception e) {
        
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		return head.e;
    	}
    
    	@Override
    	public int getSize() {
        
    		// TODO Auto-generated method stub
    		return size;
    	}
    
    	@Override
    	public boolean isEmpty() {
        
    		// TODO Auto-generated method stub
    		return size == 0;
    	}
    
    	public String toString() {
        
    		StringBuilder res = new StringBuilder();
    		res.append("Queue：front ");
    		for (Node cur = head; cur != null; cur = cur.next)
    			res.append(cur + "->");
    		res.append("NULL tail");
    		return res.toString();
    	}
    }

**测试（main）**

public class LinkedListQueueTest {
        
    	public static void main(String[] args) {
        
    		LinkedListQueue<Integer> loopqueue = new LinkedListQueue<>();
    		for (int i = 0; i < 5; i++) {
        
    			loopqueue.enqueue(i);
    			System.out.println(loopqueue);
    		}
    		loopqueue.dequeue();
    		System.out.println(loopqueue);
    	}
    }

**测试结果**![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]

## 链表实现的队列的时间复杂度 ##

**入队：O(1)  
出队：O(1)  
查询队首元素：O(1)**  
  
**实现队列的链表创建了尾节点tail，使得在链表尾部添加元素变得容易，复杂度为O(1)；但是在尾部删除元素需要遍历链表找到尾部元素的前一个节点，还是需要O(n)的复杂度，是不推荐的；所以使用链表头做队首，使用链表尾做队尾。**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200120121648996.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70