Rubyr代码随想录算法训练营第十天| 232. 用栈实现队列、225. 用队列实现栈

发布时间:2024年01月09日

Leetcode?232. 用栈实现队列?Implement Queue using Stacks

按照题目要求:

/**
?* Your MyQueue object will be instantiated and called as such:
?* MyQueue obj = new MyQueue();
?* obj.push(x);
?* int param_2 = obj.pop();
?* int param_3 = obj.peek();
?* boolean param_4 = obj.empty();
?*/

所以我们要实现队列的基本方法:

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。

因为栈遵循先进后出原则,使用两个栈,一个栈作为输入栈,一个栈作为输出栈。

例如:实现队列的pop()

输入栈依次放入: 1, 2, 使用pop(),一次从栈中移除;

输出栈:使用push(x)依次加入2,1到输出栈中,最后再移除首部元素1。

在实现队列时在以上需要实现的方法中使用栈的基本方法:

push(item): 将元素压入栈顶。

pop(): 从栈顶弹出元素,并返回弹出的元素。

peek(): 查看栈顶元素,但不弹出它。

isEmpty(): 检查栈是否为空。

size(): 返回栈中元素的个数...

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
       
    }
    
    public int pop() {
        addToStackOut();
        return stackOut.pop();
    }
    
    public int peek() {
        addToStackOut();
        return stackOut.peek();
    }
    
    public boolean empty() {
        if (stackIn.isEmpty() && stackOut.isEmpty()) {
            return true;
        }
        return false;
    }

    public void addToStackOut () {
        if (!stackOut.isEmpty()) {
            return;
        }

        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }

    } 
}

Leetcode?225. 用队列实现栈?

按照题目要求:

/**
?* Your MyStack object will be instantiated and called as such:
?* MyStack obj = new MyStack();
?* obj.push(x);
?* int param_2 = obj.pop();
?* int param_3 = obj.top();
?* boolean param_4 = obj.empty();
?*/

所以我们要实现栈的四个基本方法:

  • push(x) -- 元素 x 入栈
  • pop() -- 移除栈顶元素
  • top() -- 获取栈顶元素
  • empty() -- 返回栈是否为空

在实现之前,了解队列的接口的方法:

在 Java 中,队列(Queue)接口是一个基本的数据结构接口,它继承自 java.util.Collection 接口,提供了一系列用于管理元素的方法。以下是 Queue 接口中常用的方法:

  1. add(e): 将指定元素添加到队列尾部。如果队列已满并且不能再容纳元素,则抛出异常。
  2. offer(e): 将指定元素添加到队列尾部。如果队列已满,返回 false
  3. remove(): 移除并返回队列头部的元素。如果队列为空,则抛出异常。
  4. poll(): 移除并返回队列头部的元素。如果队列为空,则返回 null
  5. element(): 获取但不移除队列头部的元素。如果队列为空,则抛出异常。
  6. peek(): 获取但不移除队列头部的元素。如果队列为空,则返回 null
  7. size(): 返回队列中的元素数量。
  8. isEmpty(): 检查队列是否为空。
  9. clear(): 移除队列中的所有元素。
  10. contains(o): 检查队列是否包含指定元素。
  11. toArray(): 将队列转换为数组。

使用两个队列来实现栈,queue2作为备份,queue1作为操作队列。

要满足栈的后进先出的原则,push一个元素加到栈顶后,最先移除的也是这个元素,所以这个元素要先放在队列queue2中首位备份。

queue1原有的元素也陆续添加到queue2中,后进后出(实现栈的先进后出) , 最后queue2 与queue1交换。

class MyStack {
     Queue<Integer> queue1;
     Queue<Integer> queue2;

    public MyStack() {
       queue1 = new LinkedList<>();
       queue2 = new LinkedList<>();
    }
    
    public void push(int x) {
        //queue满足先进先出
        //queue2作为备份

        queue2.offer(x);
        //如果之前有元素存在,就加到queue2中,后进后出.
        //注意这里要用while,不是if
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        //交换queue1 and queue2
        Queue<Integer> temp ;
        temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
       return  queue1.peek();
    }
    
    public boolean empty() {
       return queue1.isEmpty();
    }
}

文章来源:https://blog.csdn.net/SHILIUHoster/article/details/135421293
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。