1. 队列和栈

2. 数组实现队列

public class MyQueue {
    private int[] arr;
    private int pushi;
    private int polli;
    private int size;
    private final int limit;
    public MyQueue(int limit) {
        this.limit = limit;
        pushi = 0;// 头指针
        polli = 0;// 尾指针
        size = 0;
        arr = new int[limit];
    }
    public void push(int value) {
        if (size == limit) {
            throw new RuntimeException("队列已满 无法继续添加");
        }
        size++;
        arr[pushi] = value;
        pushi = nextIndex(pushi);
    }
    public int pop(int value) {
        if (size == 0) {
            throw new RuntimeException("队列为空");
        }
        size--;
        int ans = arr[polli];
        polli = nextIndex(polli);
        return ans;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    private int nextIndex(int index) {
        // index = (index+1) % limit;
        return index < limit - 1 ? index + 1 : 0;
    }
}

3. 栈实现队列

// 使用两个栈实现
    public static class Myqueue {
        private Stack<Integer> StackPull;
        private Stack<Integer> StackPop;
    public Myqueue() {
        StackPull = new Stack<Integer>();
        StackPop = new Stack<Integer>();
    }
    public void push(int value) {
        StackPull.push(value);
        pushToPop();
    }
    private void pushToPop() {
        if (StackPop.isEmpty()) {
            while (!StackPull.isEmpty()) {
                StackPop.push(StackPull.pop()); // 将栈顶 压到 pop栈中
            }
        }
    }
    public int pop() {
        if (StackPull.isEmpty() && StackPop.isEmpty()) {
            throw new RuntimeException("队列中无元素");
        }
        pushToPop();
        return StackPop.pop();
    }
    public int peek() {
        if (StackPull.isEmpty() && StackPop.isEmpty()) {
            throw new RuntimeException("队列中无元素");
        }
        pushToPop();
        return StackPop.peek();
    }
}
public static void main(String[] args) {
    Myqueue test = new Myqueue();
    test.push(1);
    test.push(2);
    test.push(5);
    System.out.println(test.peek());
    System.out.println(test.pop());
    System.out.println(test.peek());
    System.out.println(test.pop());
    System.out.println(test.peek());
    System.out.println(test.pop());
}

4. 队列实现栈

// 两个队列实现
    public static class TwoQueueStack<T> {
        public Queue<T> queue;
        public Queue<T> help;
        public TwoQueueStack() {
            queue = new LinkedList<>();
            help = new LinkedList<>();
        }
        public void push(T value) {
            queue.offer(value); // 加入到队尾
        }
        public T pop() {
            while (queue.size() > 1) {
                help.offer(queue.poll()); // 除了队尾的元素 全部转移到另外一个队列中
            }
            T ans = queue.poll(); // 当前队尾元素为栈顶
            Queue<T> tep = queue; // 缓存当前空队列
            queue = help; // 重新转移到queue中
            help = tep;
            return ans;
        }
        public T peek() {
            while (queue.size() > 1) {
                help.offer(queue.poll());
            }
            T ans = queue.poll();
            help.offer(ans); // 由于是查看栈顶 所以获取到值后 重新添加到另外队列中
            Queue<T> tep = queue;
            queue = help;
            help = tep;
            return ans;
        }
        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }