双端链表的基本操作（2）：双端链表实现队列

快来打我* 2022-05-18 03:40 227阅读 0赞

我们知道，队列是一种“先进先出”的数据结构，队列的插入操作是在队尾进行的，而删除操作是在队头进行的，这与在双端链表的表尾插入和在表头删除操作是类似的，因此可以用双端链表实现队列。

双端链表实现队列的Java代码：

package parking;
    
    import java.util.Collection;
    import java.util.Iterator;
    import java.util.Queue;
    
    class Node {
    
    	Object data;
    	Node next;
    
    	public Node(Object data) {
    		this.data = data;
    	}
    
    }
    
    class LinkNode {
    
    	private Node head;// 头结点
    	private Node tail;// 尾结点
    	private int size;
    
    	public LinkNode() {
    		this.head = null;
    		this.tail = null;
    		this.size = 0;
    	}
    
    	// 判断是否为空
    	public boolean isEmpty() {
    		return size == 0 ? true : false;
    	}
    
    	// 头插入法
    	public void addHNode(Node node) {
    		if (head == null) {
    			head = node;
    			tail = node;
    		} else {
    			node.next = head;
    			head = node;
    		}
    		size++;
    	}
    
    	// 尾结点插入
    	public void addTnode(Node node) {
    		if (head == null) {
    			head = node;
    			tail = node;
    		} else {
    			tail.next = node;
    			tail = node;
    		}
    		size++;
    	}
    
    	// 输出头结点，不删除
    	public Object sysHNode() {
    		if (head == null) {
    			return null;
    		}
    		Object obj = head.data;
    		return obj;
    	}
    
    	// 输出头结点,并删除
    	public Object deleteHnode() {
    		if (head == null) {
    			return null;
    		}
    		Object obj = head.data;
    		if (head.next == null) {
    			head = null;
    		} else {
    			head = head.next;
    		}
    		size--;
    		return obj;
    	}
    
    	// 输出尾结点，并删除
    	public Object deleteTnode() {
    		if (head == null) {
    			return null;
    		}
    		Object obj = tail.data;
    		if (head == tail) {
    			head = null;
    			tail = null;
    		} else {
    			Node temp = head;
    			Node pre = null;// 前一个结点
    			while (temp != tail) {
    				pre = temp;
    				temp = temp.next;
    			}
    			pre.next = null;
    			tail = pre;
    		}
    		size--;
    		return obj;
    	}
    
    	// 输出链表
    	public void sysNode() {
    		if (head == null) {
    			System.out.println("链表为空");
    			return;
    		}
    		Node temp = head;
    		while (temp != null) {
    			System.out.print(temp.data + "-->");
    			temp = temp.next;
    		}
    		System.out.println();
    	}
    
    	// 获取链表大小
    	public int getSize() {
    		// TODO Auto-generated method stub
    		return size;
    	}
    
    }
    
    public class LinkQueue {
    
    	private LinkNode link;
    
    	public LinkQueue() {
    		this.link = new LinkNode();
    	}
    
    	// 获取队列大小
    	private int getSize() {
    		return link.getSize();
    	}
    
    	// 判断队列是否为空
    	private boolean isEmpty() {
    		return link.isEmpty();
    	}
    
    	// 入队，尾结点插入
    	private void add(Object obj) {
    		link.addHNode(new Node(obj));
    	}
    
    	// 出队，在链表头结点删除元素
    	private Object poll() {
    		if (this.isEmpty()) {
    			return null;
    		}
    		return link.deleteHnode();
    	}
    
    	// 输出队列元素
    	private void sysQueue() {
    		link.sysNode();
    	}
    
    	public static void main(String[] args) {
    
    		LinkQueue queue = new LinkQueue();
    		int i;
    		for (i = 0; i < 5; i++) {
    			queue.add(i);
    		}
    		System.out.println("队列元素大小--》" + queue.getSize());
    		queue.sysQueue();
    		System.out.println("出队元素--》" + queue.poll());
    		queue.sysQueue();
    		System.out.println("队列元素大小--》" + queue.getSize());
    
    	}
    
    }

效果：

队列元素大小--》5
    4-->3-->2-->1-->0-->
    出队元素--》4
    3-->2-->1-->0-->
    队列元素大小--》4

###  我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。   ###