本文共 1015 字，大约阅读时间需要 3 分钟。

用两个栈实现一个队列

问题描述

实现一个队列数据结构，仅能通过两端操作，分别在队列尾部插入整数和在队列头部删除整数。若队列为空时，删除操作返回-1。

方法思路

传统的队列可以通过数组或链表实现，但当需要通过两端操作时，使用两个栈是更有效的方法。具体来说，将一个栈用于队列的存储，另一个栈用于辅助操作。

核心思路

这种方法利用了栈的先进后出特性，使得队列的操作变得可行。

代码实现

public class CQueue {    private Stack
   
     stack1;    private Stack
    
      stack2;    public CQueue() {        stack1 = new Stack<>();        stack2 = new Stack<>();    }    public void appendTail(int value) {        while (!stack2.isEmpty()) {            stack1.push(stack2.pop());        }        stack1.push(value);    }    public int deleteHead() {        while (!stack1.isEmpty()) {            stack2.push(stack1.pop());        }        if (stack2.isEmpty()) {            return -1;        }        return stack2.pop();    }}
    
   

优化解释

这种方法确保了队列的操作符合预期，同时保持了较低的时间复杂度。

总结

通过两个栈的巧妙结合，可以高效实现队列的基本操作。这种设计既简洁又高效，适用于需要频繁队列操作的场景。