用链表实现队列

1、代码

public class ImplementationOfQueue<Item> implements Iterable {
​
    // 定义结点的嵌套类
    private class Node{
        Item item;
        Node next;
    }
​
    // 队头，代表队列中第一个元素
    private Node front;
    // 队尾，代表队列中最后一个元素
    private Node rear;
    // 栈长，也就是栈中元素的数量
    private int N;
​
    // 判空
    public boolean isEmpty(){
        return front == null;
    }
​
    // 栈长
    public int length(){
        return N;
    }
​
    // 进队，在队尾添加元素
    public void push(Item item){
​
        Node temp = rear;
​
        rear = new Node();
        rear.item = item;
        rear.next = null;
​
        if (isEmpty()){
            front = rear;
        }else {
            temp.next = rear;
        }
​
        N ++;
​
    }
​
    // 出队：在队头删除元素
    public Item pop() throws Exception {
​
        if (isEmpty()){
            throw new Exception("队列空，无法进行出队操作！");
        }
        Item item = front.item;
        Node temp = front;
        front = front.next;
        temp.next = null;
        if (isEmpty()){
            rear = null;
        }
​
        N --;
​
        return item;
​
    }
​
    // 迭代
    @Override
    public Iterator<Item> iterator() {
        return new ListIterator();
    }
​
    private class ListIterator implements Iterator<Item>{
​
        private Node current = front;
​
        @Override
        public boolean hasNext() {
            return current != null;
        }
​
        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
​
        @Override
        public void remove() {
        }
    }
    
}

View Code

2、入队示意图

 

 

3、出队示意图