225. 用队列实现栈 --力扣 --JAVA

简介: 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。实现 MyStack 类:void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

 题目

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

    • void push(int x) 将元素 x 压入栈顶。
    • int pop() 移除并返回栈顶元素。
    • int top() 返回栈顶元素。
    • boolean empty() 如果栈是空的,返回 true ;否则,返回 false

    注意:

      • 你只能使用队列的基本操作 —— 也就是 push to backpeek/pop from frontsizeis empty 这些操作。
      • 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

      解题思路一

        1. 队列是先进先出而栈是先进后出,所以需要在队列添加数据时对队列进行倒置;

        代码展示

        class MyStack {
            Queue<Integer> queue1 = null;
            Queue<Integer> queue2 = null;
            public MyStack() {
                queue1 = new LinkedList<>();
                queue2 = new LinkedList<>();
            }
            public void push(int x) {
                queue2.offer(x);
                while (!queue1.isEmpty()){
                    queue2.offer(queue1.poll());
                }
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }
            public int pop() {
                return queue1.poll();
            }
            public int top() {
                return queue1.peek();
            }
            public boolean empty() {
                return queue1.isEmpty();
            }
        }

        image.gif

        解题思路二

          1. 利用ArrayDeque双向队列,可以利用自带的读取和删除末尾的值的方法实现队列的先进后出。

          代码展示

          class MyStack {
              ArrayDeque<Integer> queue = null;
              public MyStack() {
                  queue = new ArrayDeque<>();
              }
              public void push(int x) {
                  queue.addLast(x);
              }
              public int pop() {
                  return queue.pollLast();
              }
              public int top() {
                  return queue.peekLast();
              }
              public boolean empty() {
                  return queue.isEmpty();
              }
          }

          image.gif


          目录
          相关文章
          |
          4天前
          |
          算法 安全 Java
          【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
          【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
          13 0
          |
          7天前
          |
          存储 安全 Java
          |
          13天前
          |
          Java
          LeetCode题解-逆波兰表达式求值-Java
          逆波兰表达式求值-Java
          7 0
          |
          13天前
          |
          Java
          |
          13天前
          |
          Java
          |
          13天前
          |
          Java
          LeetCode题解-二叉搜索树中第K小的元素-Java
          LeetCode题解-二叉搜索树中第K小的元素-Java
          6 0
          |
          13天前
          |
          Java
          |
          13天前
          |
          Java
          LeetCode题解- 两两交换链表中的节点-Java
          两两交换链表中的节点-Java
          7 0
          |
          13天前
          |
          Java
          LeetCode题解-合并K个有序数组-Java
          合并K个有序数组-Java
          5 0
          |
          13天前
          |
          Java

          相关产品

        1. 云迁移中心