双栈实现一个队列

两个栈可实现将列表倒序:设有含三个元素的栈 A = [1,2,3] 和空栈 B = [] 。若循环执行 A 元素出栈并添加入栈 B ,直到栈 A 为空,则 A = [] , B = [3,2,1] ,即栈 B 元素为栈 A 元素倒序。

利用栈 B 删除队首元素:倒序后,B 执行出栈则相当于删除了 A 的栈底元素,即对应队首元素。

因此,可以设计栈 A 用于加入队尾操作,栈 B 用于将元素倒序,从而实现删除队首元素。

函数设计:

  1. 加入队尾 push() : 将数字 val 加入栈 A 即可。
  2. 获取队首元素 peek() :
    1. 当栈 B 不为空: B中仍有已完成倒序的元素,因此直接返回 B 的栈顶元素。
    2. 否则,当 A 为空: 即两个栈都为空,无元素,因此返回 -1 。
    3. 否则: 将栈 A 元素全部转移至栈 B 中,实现元素倒序,并返回栈 B 的栈顶元素。
  3. 弹出队首元素 pop() :
    1. 执行 peek() ,获取队首元素。
    2. 弹出 B 的栈顶元素。
  4. 队列判空 empty() : 当栈 A 和 B 都为空时,队列为空。

代码:

class MyQueue {
    private Stack<Integer> A;
    private Stack<Integer> B;

    public MyQueue() {
        A = new Stack<>();
        B = new Stack<>();
    }

    public void push(int x) {
        A.push(x);
    }

    public int pop() {
        int peek = peek();
        B.pop();
        return peek;
    }

    public int peek() {
        if (!B.isEmpty()) return B.peek();
        if (A.isEmpty()) return -1;
        while (!A.isEmpty()){
            B.push(A.pop());
        }
        return B.peek();
    }

    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

相关推荐

  1. 【✅面试编程题:如何用队列实现一个

    2024-07-10 23:58:01       43 阅读
  2. 225.队列实现

    2024-07-10 23:58:01       16 阅读
  3. 实现队列

    2024-07-10 23:58:01       17 阅读

最近更新

  1. 什么是 MLPerf?

    2024-07-10 23:58:01       0 阅读
  2. Docker

    2024-07-10 23:58:01       0 阅读
  3. 代码改进,模型优化,强化深度学习

    2024-07-10 23:58:01       0 阅读
  4. python 基础知识点(一)

    2024-07-10 23:58:01       0 阅读
  5. Python利用psutil库进行监控进程和资源

    2024-07-10 23:58:01       0 阅读
  6. SpringBoot RestHighLevelClient 按版本更新

    2024-07-10 23:58:01       0 阅读
  7. 跨域问题几种解决方法

    2024-07-10 23:58:01       0 阅读
  8. Python面试整理-文件处理

    2024-07-10 23:58:01       0 阅读

热门阅读

  1. std::deque和std::list的区别是什么

    2024-07-10 23:58:01       4 阅读
  2. 华为OD机试(C卷,200分)- 字符串拼接、田忌赛马

    2024-07-10 23:58:01       5 阅读
  3. 如何设置PHP wkhtmltopdf

    2024-07-10 23:58:01       6 阅读
  4. yolov5中训练长条型目标召回率低问题

    2024-07-10 23:58:01       8 阅读
  5. openssl error:0A000126:SSL routines:ssl3_read_n:unexpected eof

    2024-07-10 23:58:01       9 阅读
  6. 各种软件启动方式

    2024-07-10 23:58:01       6 阅读
  7. 【创作纪念日】我的三周年创作纪念日

    2024-07-10 23:58:01       7 阅读