题目链接

示例

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

  1. 输入：
  2. ["CQueue","appendTail","deleteHead","deleteHead"]
  3. [[],[3],[],[]]
  5. 输出：
  6. [null,null,3,-1]

解题思路

题意：
两个栈实现一个队列
实现队列的两个函数
一个是 在队列尾部插入整数
一个是 在队列头部删除整数
若队列无元素，删除操作返回-1

思路：
栈 先进后出
队列 先进先出
所以使用两个栈，一个栈维护插入，一个栈维护删除
在入列时，插入到第一个栈
在出列时，即删除时，将第一个栈内的元素全部弹出到第一个栈内，再把依次第二个栈的元素弹出

成员变量**

  • 维护两个栈 stack1 和 stack2 ，其中 stack1 支持插入操作， stack2 支持删除操作

构造方法

  • 初始化 stack1 和 stack2 为空

插入元素
插入元素对应方法 appendTail

  • stack1 直接插入元素

删除元素
删除元素对应方法 deleteHead

  • 如果 stack2 为空，则将 stack1 里的所有元素弹出插入到 stack2 里

  • 如果 stack2 仍为空，则返回 -1，否则从 stack2 弹出一个元素并返回


    使用 stack() 或 LinkedList()
    但是 stack() 的线程安全的，所以比 LinkedList() 效率低
    LinkedList 实现了 Deque 和 Queue 接口，可以按照队列、栈和双端队列的方式进行操作

    LinkedList 类是双向列表（底层使用链表结构）
    列表中的每个节点都包含了对前一个和后一个元素的引用。
    LinkedList有很多方法，通过这些方法可以很容易将其用作队列、栈等数据结构。
    https://blog.csdn.net/weixin_43691723/article/details/105302287

代码

  1. class CQueue {
  3.     // 使用stack()
  4.     //两个栈，一个出栈，一个入栈
  5.     // private Stack<Integer> stack1;
  6.     // private Stack<Integer> stack2;
  8.     // public CQueue() {
  9.     //     stack1 = new Stack<>();
  10.     //     stack2 = new Stack<>();
  11.     // }
  13.     // public void appendTail(int value) {
  14.     //     stack1.push(value);
  15.     // }
  17.     // public int deleteHead() {
  18.     //     if(!stack2.isEmpty()){
  19.     //         return stack2.pop();
  20.     //     }else{
  21.     //         while(!stack1.isEmpty()){
  22.     //             stack2.push(stack1.pop());
  23.     //         }
  24.     //         return stack2.isEmpty() ? -1 : stack2.pop();
  25.     //     }
  26.     // }
  28.         private Deque<Integer> stack1;
  29.         private Deque<Integer> stack2;
  31.         public CQueue() {
  32.             stack1 = new LinkedList<Integer>();
  33.             stack2 = new LinkedList<Integer>();
  34.         }
  36.         public void appendTail(int value) {
  37.             stack1.push(value);
  38.         }
  40.         public int deleteHead() {
  41.             if(stack2.isEmpty()){
  42.                 while(!stack1.isEmpty()){
  43.                     stack2.push(stack1.pop());
  44.                 }
  45.             }
  46.             if(stack2.isEmpty()){
  47.                 return -1;
  48.             }else{
  49.                 return stack2.pop();
  50.             }
  52.         }
  53. }
  59. /**
  60.  * Your CQueue object will be instantiated and called as such:
  61.  * CQueue obj = new CQueue();
  62.  * obj.appendTail(value);
  63.  * int param_2 = obj.deleteHead();
  64.  */