题解 | 【模板】队列

我的方案是用一个链表来模拟队列，链表含队首指针和队尾指针（仅有队首指针会超时！），push是在队尾添加节点的操作，pop是在队首删除节点的操作，front是输出队首节点的操作。

import java.util.*;
/*
6
push 1
pop
front
push 2
push 3
pop

1
error
3
*/
public class Main {
    static Scanner sc = new Scanner(System.in);

    // 链表实现
    static void solve02() {
        int n = sc.nextInt();
        sc.nextLine();
        LinkedQueue queue = new LinkedQueue();
        while (n-- > 0) {
            String arr[] = sc.nextLine().split(" ");
            if (arr[0].equals("push")) {
                queue.push(Integer.parseInt(arr[1]));
            } else if (arr[0].equals("pop")) {
                Integer pop = (Integer) queue.pop();
                if (pop == null) {
                    System.out.println("error");
                } else {
                    System.out.println(pop);
                }
            } else if (arr[0].equals("front")) {
                Integer top = (Integer) queue.front();
                if (top == null) {
                    System.out.println("error");
                } else {
                    System.out.println(top);
                }
            }
        }
    }

    // 链表实现
    static void solve03() {
        int n = sc.nextInt();
        sc.nextLine();
        DoubleStackQueue queue = new DoubleStackQueue();
        while (n-- > 0) {
            String arr[] = sc.nextLine().split(" ");
            if (arr[0].equals("push")) {
                queue.push(Integer.parseInt(arr[1]));
            } else if (arr[0].equals("pop")) {
                Integer pop = (Integer) queue.pop();
                if (pop == null) {
                    System.out.println("error");
                } else {
                    System.out.println(pop);
                }
            } else if (arr[0].equals("front")) {
                Integer top = (Integer) queue.front();
                if (top == null) {
                    System.out.println("error");
                } else {
                    System.out.println(top);
                }
            }
        }
    }

    // 数组实现
    static void solve() {
        int n = sc.nextInt();
        sc.nextLine();
        Queue queue = new Queue(n);
        while (n-- > 0) {
            String arr[] = sc.nextLine().split(" ");
            if (arr[0].equals("push")) {
                queue.push(Integer.parseInt(arr[1]));
            } else if (arr[0].equals("pop")) {
                Integer pop = queue.pop();
                if (pop == -1) {
                    System.out.println("error");
                } else {
                    System.out.println(pop);
                }
            } else if (arr[0].equals("front")) {
                Integer top = queue.front();
                if (top == -1) {
                    System.out.println("error");
                } else {
                    System.out.println(top);
                }
            }
        }
    }


    public static void main(String[] args) {
//         solve();
//         solve02();
        solve03();
    }


}

///////////////////////////////////////
/*
10
front
pop
push 7
front
pop
pop
front
front
push 1
pop

error
error
7
7
error
error
error
1

*/
/**
 * 两个栈实现一个队列
 */
class DoubleStackQueue {
    Stack stackA;
    Stack stackB;

    public DoubleStackQueue() {
        stackA = new Stack();
        stackB = new Stack();
    }

    /**
     * 入队
     * @param data 数据
     */
    public void push(Object data) {
        stackA.push(data);
    }

    /**
     * 出队, 我们把 A里面的元素遍历拿出放入到B 中, 再拿出B中的第一个元素
     * @return 返回 队头的值
     */
    public Object pop() {
        // 判断 b 栈有没有元素, 有 返回 false, 无 返回 true
        if (stackB.isEmpty()) {
            while (!stackA.isEmpty()) {
                stackB.push(stackA.pop());
            }
        }
        return stackB.pop();
    }

    public Object front() {
        if (stackB.isEmpty()) {
            while (!stackA.isEmpty()) {
                stackB.push(stackA.pop());
            }
        }
        return stackB.isEmpty() ? null : stackB.top();
    }
}

class Stack {
    /**
     * 头节点, 无数据
     */
    private LNode head;

    public Stack() {
        head = new LNode();
        head.next = null;
        head.data = null;
    }

    public boolean isEmpty() {
        return head.next == null;
    }

    /**
     * 入栈
     * @param data
     */
    public void push(Object data) {
        // 创建新节点存储数据
        LNode tlNode = new LNode(data);
        // 头插法
        tlNode.next = head.next;
        head.next = tlNode;
    }

    /**
     * 出栈, 返回值
     * @return
     */
    public Object pop() {
        if (isEmpty()) return null;
        LNode del = head.next;
        // 让 head的 next 指向它的 下下个的值
        head.next = del.next;
        return del.data;
    }

    /**
     * 获取栈顶的值
     * @return
     */
    public Object top() {
        return isEmpty() ? null : head.next.data;
    }
}

class LNode {
    Object data;
    LNode next;

    public LNode() {
    }

    public LNode(Object data) {
        this.data = data;
    }

    public LNode(Object data, LNode next) {
        this.data = data;
        this.next = next;
    }
}
///////////////////////////////////////


///////////////////////////////////////

/**
 * 链表实现队列
 */
class LinkedQueue {
    // 设置两个结点node，front指向队首元素，rear指向队尾；
    /**
     * 队头指针, 指向队头节点
     */
    Node front;

    /**
     * 队尾指针, 指向队尾节点
     */
    Node rear;

    /**
     * 记录队列长度
     */
    int size = 0;

    public LinkedQueue() {
        front = rear = null;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 入队
     * @param ele
     * @return
     */
    public boolean push(Object ele) {
        if (size == 0) {
            front = new Node(null, ele);
            rear = front;
            size++;
            return true;
        }
        Node s = new Node(null, ele);
        //这块有个注意的地方，一旦rear设置了next属性，因为front节点与rear节点指向了同一个node节点，持有同一个结点的一个引用，因此front节点next属性也被填充
        rear.next = s;
        rear = s;
        size++;
        return true;
    }

    /**
     * 删除元素, 出队
     *
     * @return
     */
    public Object pop() {
        if (isEmpty()) return null;
        Object ele = front.element;
        front = front.next;
        if (size == 1) rear = front;
        size--;
        return ele;
    }

    /**
     * 队头
     * @return
     */
    public Object front() {
        return isEmpty() ? null : front.element;
    }


}

/**
 * 首先链表底层是一个个节点
 */
class Node {
    Node next;
    Object element;

    public Node(Node next, Object element) {
        this.next = next;
        this.element = element;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Object getElement() {
        return element;
    }

    public void setElement(Object element) {
        this.element = element;
    }
}

///////////////////////////////////////

///////////////////////////////////////
/**
 * 队列的实现类 -- 数组
 */
class Queue {
    /**
     * 队列需要维护的数组
     */
    private int arr[];

    /**
     * 出队列的游标, 队头
     */
    private int front = 0;

    /**
     * 入队列的游标, 队尾
     */
    private int rear = 0;

    public Queue(int size) {
        arr = new int[size];
    }

    /**
     * 插入数据
     * @param value
     */
    public void push(int value) {
        if (rear - front == arr.length) {
            // 队列满了，即将新建一个数组...
            int brr[] = new int[arr.length * 2];
            for (int i = front; i < rear; i++) {
                brr[i] = arr[i % arr.length];
                arr = brr;
            }
        }
        // 循环完回到初始位置
        arr[rear % arr.length] = value;
        rear++;
    }

    /**
     * 输出数据
     * @return
     */
    public int pop() {
        // 队列空了
        if (rear == front) {
            return -1;
        }
        int value = arr[front % arr.length];
        front++;
        return value;
    }

    public int front() {
        // 队列空了
        if (rear == front) {
            return -1;
        }
        return arr[front];
    }

}
///////////////////////////////////////