azl397985856 commented 2 years ago

232. 用栈实现队列

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/implement-queue-using-stacks/

前置知识

栈

队列

题目描述


使用栈实现队列的下列操作：

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

MyQueue queue = new MyQueue();

queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false 说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。假设所有操作都是有效的、（例如，一个空的队列不会调用 pop 或者 peek 操作）。

physicshi commented 2 years ago

思路

rust 双栈实现队列

代码

struct MyQueue {
    input: Vec<i32>,
    output: Vec<i32>,
}

impl MyQueue {

    fn new() -> Self {
        Self {
            input: vec![],
            output: vec![],
        }
    }

    fn push(&mut self, x: i32) {
        self.input.push(x);
    }

    fn pop(&mut self) -> i32 {
        self.peek();
        self.output.pop().unwrap()
    }

    fn peek(&mut self) -> i32 {
        if self.output.is_empty() {
            while self.input.len() > 0 {
                self.output.push(self.input.pop().unwrap());
            }

        }
        self.output.last().cloned().unwrap()
    }

    fn empty(&mut self) -> bool {
        self.input.is_empty() && self.output.is_empty()
    }
}

复杂度

push ：

时间复杂度：O(1)
空间复杂度：O(n)

pop ：

时间复杂度：O(1)
空间复杂度：O(1)

peek：

时间复杂度：最好的情况O(1) 最坏的情况O(n)
空间复杂度：O(1)

empty：

时间复杂度：O(1)
空间复杂度：O(1)

KelvinG-LGTM commented 2 years ago

思路

Tip: stack其实是一个操作受限的数据结构. 既只能对最后一个数(i.e.: 栈顶)进行pop, append操作. 如果我们解题用到list时, 操作stack[0]就有点不讲武德了.

使用两个栈. 一个用来push stack_push, 一个用来pop stack_pop.

1️⃣ push策略: 直接往stack_push里面append. 理论上, 你想怎么push都可以, 只要后面的pop, peek方法都正确就行.

2️⃣ pop 策略: stack_pop里面的最后一个数 (也就是栈顶)一定是queue的第一个数. 所以我们需要确保stack_pop里面时刻"有数可弹".

如果stack_pop不为空, 我们就把最后一个(i.e.: 栈顶元素)取出来.
如果stack_pop为空, 我们就需要把stack_push里面的数一边弹出, 一边弹入. 操作结束后, 把stack_pop里面最后一个(i.e.: 栈顶元素)pop出来并且返回.

3️⃣ peek策略: 核心理念跟pop相同. 我们需要确保stack_pop里面时刻"有数可弹". 思路与pop()相同

代码

class MyQueue:
    def __init__(self):
        self.stack_push = []
        self.stack_pop = []

    def push(self, x: int) -> None:
        self.stack_push.append(x)

    def pop(self) -> int:
        if self.empty(): 
            return -1
        if not self.stack_pop: 
            while self.stack_push: 
                tmp = self.stack_push.pop()
                self.stack_pop.append(tmp)
        res = self.stack_pop.pop()
        return res

    def peek(self) -> int:
        if self.empty(): 
            return -1
        if self.stack_pop: 
            return self.stack_pop[-1]

        else: 
            while self.stack_push: 
                tmp = self.stack_push.pop()
                self.stack_pop.append(tmp)
            return self.stack_pop[-1]

    def empty(self) -> bool:
        return not self.stack_push and not self.stack_pop

复杂度分析

时间复杂度

push - O(1) pop - max(O(1) or O(当前stack_push的大小)) = O(N) peek - 跟pop一样 O(N)

空间复杂度

用到了两个stack. O(最终队列的大小)

反思

🫡 不过不知道这道题的实际意义是什么? 没有办法把题目跟生产环境联系在一起.

题解中有提到:

其实使用两个栈来替代一个队列的实现是为了在多进程中分开对同一个队列对读写操作。一个栈是用来读的，另一个是用来写的。当且仅当读栈满时或者写栈为空时，读写操作才会发生冲突。

当只有一个线程对栈进行读写操作的时候，总有一个栈是空的。在多线程应用中，如果我们只有一个队列，为了线程安全，我们在读或者写队列的时候都需要锁住整个队列。而在两个栈的实现中，只要写入栈不为空，那么push操作的锁就不会影响到pop。

TODO: 可能需要改一下自己的code. 我的代码只有在pop, peek时, 才会进行"倒腾"

rzhao010 commented 2 years ago

Thoughts Using two stacks to stimulate the FIFO sequence, one var to record the front element of the queue

Code

class MyQueue {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    int front;
    public MyQueue() {

    }

    public void push(int x) {
        if (stack1.isEmpty()) {
            front = x;
        }
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        stack2.push(x);
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
    }

    public int pop() {
        int top = stack1.pop();
        if (!stack1.isEmpty()){
            front = stack1.peek();
        }
        return top;
    }

    public int peek() {
        return front;
    }

    public boolean empty() {
        return stack1.isEmpty();
    }
}

Complexity

Time: O(1), Push and Pop are constant time
Space: O(1) no extra space used

forestie9 commented 2 years ago

Ideas

Use two stacks. Push to one stack, in peek and pop, reversely push element in first stack to second to get O(1).

Code

class MyQueue:

    def __init__(self):
        self.stack = []
        self.top = []

    def push(self, x: int) -> None:
        self.stack.append(x)        

    def pop(self) -> int:
        self.peek()
        return self.top.pop()

    def peek(self) -> int:
        if not self.top:
            while self.stack:
                self.top.append(self.stack.pop())
        return self.top[-1]

    def empty(self) -> bool:
        return not self.stack and not self.top

Complexity

O(1) time and space

zhiyuanpeng commented 2 years ago

class MyQueue:

    def __init__(self):
        self.push_stack = []
        self.pop_stack = []

    def push(self, x: int) -> None:
        self.push_stack.append(x)

    def pop(self) -> int:
        self.peek()
        return self.pop_stack.pop()

    def peek(self) -> int:
        if not self.pop_stack:
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())
        return self.pop_stack[-1]

    def empty(self) -> bool:
        if self.pop_stack or self.push_stack:
            return False
        else:
            return True

time O(1) space O(N)

maybetoffee commented 2 years ago

class MyStack { private Queue q; private int top_elem;

public MyStack() {
    q = new LinkedList<>();
    top_elem = 0; 
}

public void push(int x) {
    q.offer(x);
    top_elem = x;
}

public int pop() {
    int size = q.size();
    while(size > 2){
        q.offer(q.poll());
        size--;
    }
    top_elem = q.peek();
    q.offer(q.poll());
    return q.poll();
}

public int top() {
    return top_elem;
}

public boolean empty() {
    return q.isEmpty();
}

}

Ellie-Wu05 commented 2 years ago

思路：第一次只用了一个stack，不符合题目要求两个stack

还是先把想法留下

代码

class MyQueue:

    def __init__(self):
        self.queue = []

    def push(self, x: int) -> None:
        self.queue.append(x)

    def pop(self) -> int:
        return self.queue.pop(0)

    def peek(self) -> int:
        return self.queue[0]

    def empty(self) -> bool:
        return self.queue ==[]

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

思路二：两个stack

outqueue stack 直接 append inqueue pop 出来的值

class MyQueue:

    def __init__(self):
        self.inqueue = []
        self.outqueue =[]

    def push(self, x: int) -> None:
        self.inqueue.append(x)
        self.outqueue.append(self.inqueue.pop())

    def pop(self) -> int:
        return self.outqueue.pop(0)

    def peek(self) -> int:
        return self.outqueue[0]

    def empty(self) -> bool:
        return (not self.inqueue) and (not self.outqueue)

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

复杂度分析

时间：\ Push - On \ Pop - On \ Peek - O1 \ empty -O1 \ 空间： \ Push - On \ Pop - O1 \ Peek - O1 \ empty -O1

yz3516 commented 2 years ago

思路

用两个stack，一个inStack无脑存push进queue的element，另一个outStack负责pop和peek method；

代码

class MyQueue {
    Stack<Integer> inStack;
    Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

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

    public int pop() {
        peek();
        return outStack.pop();
    }

    public int peek() {
        if(outStack.isEmpty()){
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

复杂度

空间复杂度都是O(1)；\ 时间：\ push: O(1), 只需要push到inStack里\ pop: O(1), worst case O(n)，需要call一次peek然后return outStack栈顶的元素\ peek: O(1), worst case O(n)\ emptu：O(1), 查看两个stack是否都为空都是O(1)

zqwwei commented 2 years ago

Code

class MyQueue {
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();
    private int front;

    public MyQueue() {

    }

    // 每次S1空都更新front
    public void push(int x) {
        if (s1.empty())
            front = x;
        s1.push(x);
    }

    public int pop() {
        if (s2.empty()) {
            // s1搬空 下次push更新front
            while(!s1.empty())
                s2.push(s1.pop());
        }
        return s2.pop();
    }

    // peek是两部分逻辑 S2相当于队列如不为空直接返回peek 否则S1最底就是peek值
    public int peek() {
        if (!s2.empty()) 
            return s2.peek();
        return front;
    }

    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}

Complexity

Time: amortized O(1) pop
Space: O(n)

q815101630 commented 2 years ago

用两个stack

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.inStack = []
        self.outStack = []
    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.inStack.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if self.outStack:
            return self.outStack.pop()
        else:
            while self.inStack:
                self.outStack.append(self.inStack.pop())
            if self.outStack:
                return self.outStack.pop()
            else:
                return -1
    def peek(self) -> int:
        """
        Get the front element.
        """
        if self.outStack:
            return self.outStack[-1]
        else:
            while self.inStack:
                self.outStack.append(self.inStack.pop())
            if self.outStack:
                return self.outStack[-1]
            else:
                return -1

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not self.inStack and not self.outStack

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

Time: O(1)

Space: O(n)

currybeefer commented 2 years ago

思路：这题的思路就是用两个栈模拟就好啦代码： ` stack stk1; stack stk2; MyQueue() {

}

void push(int x) 
{
    stk1.push(x);
}

int pop() 
{
    int res;
    while(!stk1.empty())
    {
        int x = stk1.top();
        stk1.pop();
        stk2.push(x);
    }
    res=stk2.top();
    stk2.pop();
    while(!stk2.empty())
    {
        int x = stk2.top();
        stk2.pop();
        stk1.push(x);
    }
    return res;
}

int peek() 
{
    int res;
    while(!stk1.empty())
    {
        int x = stk1.top();
        stk1.pop();
        stk2.push(x);
    }
    res=stk2.top();
    while(!stk2.empty())
    {
        int x = stk2.top();
        stk2.pop();
        stk1.push(x);
    }
    return res;
}

bool empty() 
{
    return stk1.empty();
}`

复杂度： peek()和pop()的时间复杂度是O(n)，其他都是O(1) 空间复杂度为O(n)

nancychien commented 2 years ago

思路

Use two stacks. One for pushing (stack_push), one for popping (stack_pop) ` class MyQueue: def init(self): self.stack_push = [] self.stack_pop = []

def push(self, x: int) -> None:
    self.stack_push.append(x)

def pop(self) -> int:
    if self.empty(): 
        return -1
    # stack_pop is empty
    if not self.stack_pop: 
        while self.stack_push: 
            tmp = self.stack_push.pop()
            self.stack_pop.append(tmp)
    result = self.stack_pop.pop()
    return result

def peek(self) -> int:
    if self.empty(): 
        return -1
    if self.stack_pop: 
        return self.stack_pop[-1]
    else: 
        while self.stack_push: 
            tmp = self.stack_push.pop()
            self.stack_pop.append(tmp)
        return self.stack_pop[-1]

def empty(self) -> bool:
    return not self.stack_push and not self.stack_pop

`

Time complixiety: push - O(1) pop - O(n) peek - O(n) empty - O(1) Space complixiety: push - O(n) pop - O(1) peek - O(1) empty - O(1)

fhuang5 commented 2 years ago

(Java). Used helper function to avoid repeated code. O(1) amortized time and O(1) auxiliary space.

class MyQueue {

    private Stack<Integer> pushStack = new Stack<Integer>();
    private Stack<Integer> popStack = new Stack<Integer>();

    private void updatePopStack() {
        if(popStack.isEmpty()) {
            while(!pushStack.isEmpty()){
                popStack.push(pushStack.pop());
            }
        }
    }

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

    public int pop() {
        updatePopStack();
        return popStack.pop();
    }

    public int peek() {
        updatePopStack();
        return popStack.peek();
    }

    public boolean empty() {
        return ( popStack.isEmpty() && pushStack.isEmpty() );

    }

}

YuyingLiu2021 commented 2 years ago

时间复杂度:  O(N)
空间复杂度:  O(N)

class MyQueue:
    def __init__(self):
        self.instack = []
        self.outstack = []

    def push(self, x: int) -> None:
        self.instack.append(x)

    def pop(self) -> int:
        if len(self.outstack) == 0:
            while len(self.instack) !=0:
                self.outstack.append(self.instack.pop())
        return self.outstack.pop()

    def peek(self) -> int:
        if len(self.outstack) == 0:
            while len(self.instack) !=0:
                self.outstack.append(self.instack.pop())
        return self.outstack[-1]

    def empty(self) -> bool:
        if len(self.instack) == 0 and len(self.outstack) == 0:
            return True
        else:
            return False

Geek-LX commented 2 years ago

思路：

Use two stacks

代码：

class MyQueue:

    def __init__(self):
        self.stack = []
        self.help_stack = []

    def push(self, x: int) -> None:
            while self.stack:
                self.help_stack.append(self.stack.pop())
            self.help_stack.append(x)
            while self.help_stack:
                self.stack.append(self.help_stack.pop())

    def pop(self) -> int:
        return self.stack.pop()

    def peek(self) -> int:
        return self.stack[-1]

    def empty(self) -> bool:
        return not bool(self.stack)

复杂度：

Time complixiety: push - O(n) pop - O(1) peek - O(1) empty - O(1) Space complixiety: push - O(n) pop - O(1) peek - O(1) empty - O(1)

疑问：

->int 在Python函数定义中是什么意思？

只是告诉返回一个整数（但它不会强制函数返回整数）。它被称为返回批注

来自 https://stackoverflow.com/questions/14379753/what-does-mean-in-python-function-definitions

峰顶的索引是-1，那栈的索引是怎样的呢？

def peek(self) -> int:

return self.stack[-1]

//我认为首先看stack是怎样实现的？

List可以实现stack，dict更适合链表

但是list可没有-1的索引？

5.1.1. 將 List 作為 Stack（堆疊）使用

来自 https://docs.python.org/zh-tw/3/tutorial/datastructures.html#using-lists-as-stacks

XiaoLiz commented 2 years ago

思路

看到这个题型首先想到数组增删改查

代码

var MyQueue = function() {
    this.tasck = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    return this.stack.push(x)
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    return this.stack.shift()
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    return this.stack.slice(0, 1)
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
   return !this.stack.length;
};

复杂度分析

时间复杂度: O(1)
空间复杂度: O(1)

ghost commented 2 years ago

思路

使用两个栈，如同两个杯子倒水一样进行操作

代码

class MyQueue:
    def __init__(self):
        self.stack_push = []
        self.stack_pop = []

    def push(self, x: int) -> None:
        self.stack_push.append(x)

    def pop(self) -> int:
        if self.empty(): 
            return -1
        if not self.stack_pop: 
            while self.stack_push: 
                tmp = self.stack_push.pop()
                self.stack_pop.append(tmp)
        res = self.stack_pop.pop()
        return res

    def peek(self) -> int:
        if self.empty(): 
            return -1
        if self.stack_pop: 
            return self.stack_pop[-1]

        else: 
            while self.stack_push: 
                tmp = self.stack_push.pop()
                self.stack_pop.append(tmp)
            return self.stack_pop[-1]

    def empty(self) -> bool:
        return not self.stack_push and not self.stack_pop

复杂度分析

时间复杂度：O(1) O(N)
空间复杂度：O(N)

Frederickfan commented 2 years ago

class MyQueue(object):

    """
    Queue is fifo stack is lifo

    [1, 2, 3]
    [3, 2, 1]

    [4] -> push
    [3,2,1] -> peak and pop
    if not queue:
        push elem from first stack to sec
    else:
        pop or peek from the other    
    """

    def __init__(self):
        self.pushStack = []
        self.popStack = []

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.pushStack.append(x)

    def pop(self):
        """
        :rtype: int
        """
        if self.popStack:
            return self.popStack.pop()
        while self.pushStack:
            self.popStack.append(self.pushStack.pop())
        return self.popStack.pop()

    def peek(self):
        """
        :rtype: int
        """
        print(self.pushStack)
        if self.popStack:
            return self.popStack[-1]
        while self.pushStack:
            self.popStack.append(self.pushStack.pop())
        print(self.popStack)
        return self.popStack[-1]

    def empty(self):
        """
        :rtype: bool
        """
        return len(self.pushStack) == 0 and len(self.popStack) == 0

houmk1212 commented 2 years ago

思路

使用两个栈，来实现队列的操作；入队时候，可以不管，直接入栈1。出队的时候，为了获得栈低的元素，需要把栈1中的元素出栈，并依次入栈2. 当栈2不空的时候，出队需要从栈2中弹栈。

代码

class MyQueue {
    private ArrayDeque<Integer> stack1;
    private ArrayDeque<Integer> stack2;
    public MyQueue() {
        stack1 = new ArrayDeque<Integer>();
        stack2 = new ArrayDeque<Integer>();
    }

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

    public int pop() {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        int ans = stack2.pop();
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        return ans;
    }

    public int peek() {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        int ans = stack2.peek();
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        return ans;
    }

    public boolean empty() {
        return stack1.isEmpty();
    }
}

复杂度

时间复杂度：入队O(1) peek和pop O(N)

空间复杂度：O（N）

wychmod commented 2 years ago

思路

两个栈来回倒

代码

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack1 = []
        self.stack2 = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stack1.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        self.stack2 = self.stack1[::-1]
        res = self.stack2.pop()
        self.stack1 = self.stack2[::-1]
        return res

    def peek(self) -> int:
        """
        Get the front element.
        """
        return self.stack1[0]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return True if len(self.stack1) == 0 else False

复杂度分析

时间复杂度pop On 其他O1 空间复杂度 On

Magua-hub commented 2 years ago

思路用两个stack模拟

代码


class MyQueue {
public:
    stack<int> stk, num;

    MyQueue() {

    }

    void push(int x) {
        stk.push(x);
    }

    int pop() {
        if(!stk.empty() && num.empty()) {
            while(!stk.empty()) {
                num.push(stk.top());
                stk.pop();
            }
        }
        int res = num.top();
            num.pop();
            return res;
    }

    int peek() {
        if(!stk.empty() && num.empty()) {
            while(!stk.empty()) {
                num.push(stk.top());
                stk.pop();
            } 
        }
        int res = num.top();

            return res;
    }

    bool empty() {
        if(stk.empty() && num.empty()) 
            return true;
        else return false;
    }
};
复杂度
空间复杂度都是O(n)；
时间：
push: O(1),
pop: O(n) 
peek: O(n)
emptu：O(1)

zzz607 commented 2 years ago

思路

见代码

代码

type MyQueue struct {
    input *MyStack
    output *MyStack
}

func Constructor() MyQueue {
    return MyQueue{
        input: new(MyStack),
        output: new(MyStack),
    }
}

func (this *MyQueue) Push(x int)  {
    this.input.Push(x)
}

func (this *MyQueue) Pop() int {
    // 题目保证不会在空的栈上面调用pop/peek
    if this.output.IsEmpty() {
        this.inputToOutput()
    }
    return this.output.Pop()
}

func (this *MyQueue) Peek() int {
    if this.output.IsEmpty() {
        this.inputToOutput()
    }
    return this.output.Peek()
}

func (this *MyQueue) Empty() bool {
    if this.input.Size() != 0 || this.output.Size() != 0 {
        return false
    }
    return true
}

func (this *MyQueue) inputToOutput() {
    for !this.input.IsEmpty() {
        this.output.Push(this.input.Pop())
    }
}

type MyStack struct {
    data []int
}

func (receiver *MyStack) Pop() int {
    if receiver.IsEmpty() {
        return -1
    }

    v := receiver.data[len(receiver.data) - 1]
    receiver.data = receiver.data[:len(receiver.data) - 1]
    return v
}

func (receiver *MyStack) Peek() int {
    if receiver.IsEmpty() {
        return -1
    }

    return receiver.data[len(receiver.data) - 1]
}

func (receiver *MyStack) Push(v int) {
    receiver.data = append(receiver.data, v)
}

func (receiver *MyStack) Size() int {
    return len(receiver.data)
}

func (receiver *MyStack) IsEmpty() bool {
    return len(receiver.data) == 0
}

复杂度分析

时间复杂度：push和empty是O(1)。pop和peek由于有一个遍历动作，看上去是N(N), 但是随后的pop/peek就是O(1)了，所以，平摊一下的话，应该就是O(1)。综上，平均时间复杂度为O(1)
空间复杂度：O(N)

FutureFields commented 2 years ago

Idea: Stack push and pop

class MyQueue { private: stack a; stack b; public: MyQueue() { } void push(int x) { a.push(x); } int pop() { int num = 0; if (b.empty()) { while(!a.empty()) { b.push(a.top()); a.pop(); } } if (!b.empty()) { num = b.top(); b.pop(); } return num; }
int peek() { int num = 0; if (b.empty()) { while(!a.empty()) { b.push(a.top()); a.pop(); } } if (!b.empty()) num = b.top(); return num; }
bool empty() { if (a.empty() && b.empty()) return true; return false; } };

space: O(1), time: O(1)

flaming-cl commented 2 years ago

232. 用栈实现队列

思路

基本思路
- 问题：删除数组开头元素，时间复杂度相对较高
- 解决办法：用两个栈实现队列
两个栈实现队列细节
- 栈 2、栈 1 的作用
- 栈 1 用于入栈，栈 2 用于出栈
- 栈 2 、栈 1 的关系
- 栈 2 即倒过来的栈 1：栈 1 最前面的元素，会被推到栈 2 末尾
- 栈 2 和栈 1 联合，对消减时间复杂度的贡献
- 删除栈 1 的开头元素，即变为删除栈 2 的末尾元素，O(N) => O(1)

复杂度

空间复杂度 O(N)
时间复杂度
- 摊还时间复杂度 O(1)
- 最坏情况 O(N)：栈 2 为空，需要 for loop 挤压栈 1 时
- 最好情况 O(1)

摊还分析

摊还分析的核心
- 高频次操作的时间复杂度小 + 低频次操作的时间复杂度高，二者均摊了每次操作的代价
- 即，每 n 次入队才能产生一次代价为 n 的出队操作
所有操作的总时间复杂度

O(2N) = n(所有的入队操作产生） + 2 * n(第一次出队操作产生） + n - 1(剩下的出队操作产生）
综上所述，每次操作的平均时间复杂度为 O(2N/2N)=O(1)

代码

var MyQueue = function() {
  this.queue1 = [];
  this.queue2 = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
  this.queue1.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
  this.cleanQ1();
  return this.queue2.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
  this.cleanQ1();
  return this.queue2[this.queue2.length - 1];
};

MyQueue.prototype.cleanQ1 = function() {
  if (this.queue2.length === 0) {
    const q1Len = this.queue1.length;
    for (let i = 0; i < q1Len; i++) {
      this.queue2.push(this.queue1.pop());
    }
  }
}

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
  return this.queue1.length === 0 && this.queue2.length === 0;
};

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

carterrr commented 2 years ago

class MyQueue {

Deque<Integer> pushStack;
Deque<Integer> popStack;

public MyQueue() {
    pushStack = new LinkedList<>();
    popStack = new LinkedList<>();
}

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

public int pop() {
    if(popStack.isEmpty()){
        transfer();
    }
    if(popStack.isEmpty()) 
    return -1;
    return popStack.pop();
}

public int peek() {
    if(popStack.isEmpty()){
        transfer();
    }
    if(popStack.isEmpty()) 
    return -1;
    return popStack.peek();
}

public boolean empty() {
    return pushStack.isEmpty() && popStack.isEmpty();
}

private void transfer() {
    while(!pushStack.isEmpty()) {
        popStack.push(pushStack.pop());
    }
}

}

BlueRui commented 2 years ago

Problem 232. Implement Queue using Stacks

Algorithm

Use two stacks to implement the queue: inStack and outStack.
Each element will be first pushed into inStack.
If outStack is not empty, we will pop from outStack. If outStack is empty, when pop/peek is called on the queue, we pop all elements in inStack and push them to outStack. After this, the head of the queue is at the top of outStack.

Complexity

push(): time complexity O(1).
pop(): amortized time complexity O(1). Each element will only be moved from inStack to outStack once with a total time of O(n). If we pop n times, the amortized time for each pop() is O(1).
peek(): same as pop().

Code

Language: Java

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    /** Initialize your data structure here. */
    public MyQueue() {
        inStack = new ArrayDeque<>();
        outStack = new ArrayDeque<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        inStack.addFirst(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (outStack.isEmpty()) {
            top();
        }
        return outStack.removeFirst();
    }

    /** Get the front element. */
    public int peek() {
        if (outStack.isEmpty()) {
            top();
        }
        return outStack.peekFirst();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void top() {
        // move all elements from inStack to outStack
        while (!inStack.isEmpty()) {
            outStack.addFirst(inStack.removeFirst());
        }
    }
}

youxucoding commented 2 years ago

4月5日【day05】

leetcode.232. 用栈实现队列

难度简单

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

思路：

题目中明确需要使用两个栈 实现队列，队列的特点是先进先出，队尾进队头出，队尾进入我们可以使用压栈实现（栈头即队尾），关键点在于队头出队怎么实现？

使用两个栈，一个称为stack_tail 即栈头是队尾，另一个成为stack_head 即栈头是队头，实现push() 直接向stack_tail压栈即可，当实现pop()时，将stack_tail栈中元素逐个弹出，并逐个压入stack_head，此时stack_head.pop()将弹出队头元素，再将此栈逐个弹出并压入stack_tail中，至此pop实现完成，stack_tai栈中的栈底元素（即队头）已经弹出。

代码实现：

class MyQueue {
    private Stack<Integer> stack_head;
    private Stack<Integer> stack_tail;
    public MyQueue() {
        stack_head = new Stack<Integer>();
        stack_tail = new Stack<Integer>();
    }

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

    public int pop() {
        int res = 0;
        if(!stack_tail.empty()){
            while(!stack_tail.empty()){
                stack_head.push(stack_tail.pop());
            }
            res = stack_head.pop();
            while(!stack_head.empty()){
                stack_tail.push(stack_head.pop());
            }
        }
        return res;
    }

    public int peek() {
        int res = 0;
        if(!stack_tail.empty()){
            while(!stack_tail.empty()){
                stack_head.push(stack_tail.pop());
            }
            res = stack_head.peek();
            while(!stack_head.empty()){
                stack_tail.push(stack_head.pop());
            }
        }
        return res;
    }

    public boolean empty() {
        return stack_tail.empty();
    }
}

复杂度分析：

时间复杂度：
- push：O(1)
- pop：O(N)
- peek：O(N)
- empty：O(1)
空间复杂度：
- push：O(1)
- pop：O(N)
- peek：O(N)
- empty：O(1)

linjunhe commented 2 years ago

思路

push: 新数据来了就 push 到栈1，
pop: 需要 pop 的时候（如果栈2 不为空），就把栈1 反转（等价于pop后再append）存到栈2，从栈2 pop

代码

class MyQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x: int) -> None:
        self.stack1.append(x)

    def pop(self) -> int:
        if self.stack2 == []:
            self.stack2 = list(reversed(self.stack1))
            self.stack1 = []
        return self.stack2.pop()

    def peek(self) -> int:
        if self.stack2 == []:
            return self.stack1[0]
        else:
            return self.stack2[-1]

    def empty(self) -> bool:
        return self.stack2 == [] and self.stack1 == []

复杂度分析

时间复杂度：O(1), python中reversed的时间复杂度好像是O(1)
空间复杂度：O(n), n为stack长度

JudyZhou95 commented 2 years ago

Analysis

Use two stacks to reverse output order. Only move elements from input stack to output stack when previous elements in output are all popped out.

Code

class MyQueue:

    def __init__(self):
        self.input = []
        self.output = []

    def push(self, x: int) -> None:
        self.input.append(x)

    def pop(self) -> int:
        self.move()
        return self.output.pop()

    def peek(self) -> int:
        self.move()
        return self.output[-1]

    def empty(self) -> bool:
        return not self.input and not self.output
    def move(self):
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

Complexity:

Time Complexity: O(1) Space Complexity: O(N)

ShawYuan97 commented 2 years ago

题目地址(232. 用栈实现队列)

https://leetcode-cn.com/problems/implement-queue-using-stacks/

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

 

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

 

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

 

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

思路

由于栈是先进后出的特性，一个栈无法实现队列操作，因此需要两个栈。
其中一个栈用于进入队列，栈依然保持了入队的顺序
出队时，如果出栈为空，将入栈的元素反向放入出栈；如果出栈不为空，输入出栈的栈顶元素
判空条件就是两个栈同时为空

代码

语言支持：Python3

Python3 Code:


class MyQueue:
    """
    使用两个栈来实现队列的操作，将两个栈分为输入栈和输出栈
    """
    def __init__(self):
        self.instack = []
        self.outstack = []

    def push(self, x: int) -> None:
        self.instack.append(x)

    def pop(self) -> int:
        if self.empty():
            return None 
        if self.outstack:
            return self.outstack.pop()
        else:
            self.outstack = self.instack[::-1]
            self.instack = []
        return self.outstack.pop()

    def peek(self) -> int:
        if not self.outstack:
            return self.instack[0]
        else:
            return self.outstack[-1]

    def empty(self) -> bool:
        if not self.instack and not self.outstack:
            return True
        return False 

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

复杂度分析

令 n 为数组长度。

时间复杂度：$O(1)$
空间复杂度：$O(n)$

caterpillar-0 commented 2 years ago

思路

两个栈，一个进，一个出

代码

class MyQueue {
private:
    stack<int> instack;
    stack<int> outstack;
    void inout(){
        //此处不可以用pop，pop是删除栈顶元素，无返回值，使用top返回
        while(!instack.empty()){//empty空返回true,不空返回false
            outstack.push(instack.top());
            instack.pop();//删除
        }
    }
public:
    //使用两个栈，一个instack,一个outstack
    MyQueue() {
        //stack栈后进先出，队列先进先出
    }
    //析构可以省略，因为数据都是容器，只有析构函数；
    void push(int x) {
        instack.push(x); 
    }

    int pop() {
        if(outstack.empty()){
            inout();
        }
        int temp=outstack.top();//读取栈顶元素
        outstack.pop();//删除栈顶
        return temp;//返回元素
    }

    int peek() {
        //返回队列开头元素
        if(outstack.empty()){
            inout();
        }
        return (outstack.top());//读取栈顶元素
    }

    bool empty() {
        return (instack.empty() && outstack.empty());
    }
};

复杂度分析

时间复杂度：push-o(1),pop-o(n)
空间复杂度：o(n)

miss1 commented 2 years ago

思路

定义两个栈，pop的时候，将stack1的数据全部pop到stack2，返回stack2栈顶的值，再将stack2全部pop回stack1

代码


var MyQueue = function() {
  this.stack1 = [];
  this.stack2 = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
  this.stack1.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
  while (this.stack1.length > 0) {
    this.stack2.push(this.stack1.pop());
  }
  let res = this.stack2.pop();
  while (this.stack2.length > 0) {
    this.stack1.push(this.stack2.pop());
  }
  return res;
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
  return this.stack1[0];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
  return this.stack1.length === 0;
};

复杂度分析

time: O(n)
space: O(n)

yanjyumoso commented 2 years ago

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stackpush = []
        self.stackpop = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stackpush.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        while not self.stackpop:
            while self.stackpush:
                self.stackpop.append(self.stackpush.pop())
        return self.stackpop.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        while self.stackpop:
            self.stackpush.append(self.stackpop.pop())
        return self.stackpush[0]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not(bool(self.stackpop) or bool(self.stackpush))

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

CarrieyqZhang commented 2 years ago

思路

用两个栈来实现，push的时候用input stack, pop的时候如果output栈有元素，直接pop,如果为空，把input栈所有元素push到output栈再pop peek()也先检查output栈是否为空，不为空直接peek,空的话把input栈所有元素push到output栈再peek 如果两个栈都为空的话那么empty（）返回空

代码

class MyQueue {
    Stack<Integer> input;
    Stack<Integer> output;

    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();

    }

    public void push(int x) {
        input.push(x);

    }

    public int pop() {
        if(output.isEmpty()){   //must check if it's empty   
            while(!input.isEmpty()){
                output.push(input.pop());
            }     
        }
          return output.pop();

    }

    public int peek() {
        if(output.isEmpty()){//must check empty
            while(!input.isEmpty()){
                output.push(input.pop());
            }
        }
        return output.peek();
    }

    public boolean empty() {
        return output.isEmpty() && input.isEmpty();
    }
}

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

revisegoal commented 2 years ago

idea

双辅助栈实现队列

code

class MyQueue {
    Deque<Integer> pushStack = new LinkedList<>();
    Deque<Integer> popStack = new LinkedList<>();
    public MyQueue() {

    }

    public void push(int x) {
        while (!popStack.isEmpty()) {
            pushStack.push(popStack.pop());
        }
        pushStack.push(x);
    }

    public int pop() {
        while (!pushStack.isEmpty()) {
            popStack.push(pushStack.pop());
        }
        return popStack.pop();
    }

    public int peek() {
        while (!pushStack.isEmpty()) {
            popStack.push(pushStack.pop());
        }
        return popStack.peek();
    }

    public boolean empty() {
        return pushStack.isEmpty() && popStack.isEmpty();
    }
}

/**
 * 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();
 */

complexity

time: O(n)
space: O(n)

duke-github commented 2 years ago

思路

向其中一个栈推数据会出现在栈顶，如果需要读取的时候，需要读取最后一个，这时候只需要将栈翻转即可。
在队列的先进先出规则上，只会操作栈的最后一个，所以将栈翻转之后保存即时队列的操作顺序。
当用于输出的栈数据为空的时候，将用于保存的栈的数据翻转给输出栈。

复杂度

时间复杂度O(1) 对于双栈中的每个数据 均进行两次入栈 两次出栈的操作  空间复杂度O(1)除双栈外不需要额外的空间

代码

class MyQueue {
        private Stack<Integer> headStack = new Stack<>();
        private Stack<Integer> tailStack = new Stack<>();

        public MyQueue() {
        }

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

        public int pop() {
            if (tailStack.empty()) {
                while (!headStack.empty()) {
                    tailStack.push(headStack.pop());
                }
            }
            return tailStack.pop();
        }

        public int peek() {
            if (tailStack.empty()) {
                while (!headStack.empty()) {
                    tailStack.push(headStack.pop());
                }
            }
            return tailStack.peek();
        }

        public boolean empty() {
            return headStack.empty() && tailStack.empty();
        }
}

bolunzhang2021 commented 2 years ago

class MyQueue {
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();

    public MyQueue() {

    }

    public void push(int x) {
        while (!s2.isEmpty()) {
            s1.push(s2.pop());
        }
        s1.push(x);           
    }

    public int pop() {   
        while (!s1.isEmpty()) {
       s2.push(s1.pop());
       }
        return s2.pop();
    }

    public int peek() {
        while(!s1.empty())
       { s2.push(s1.pop());} 

        return s2.peek();
    }

    public boolean empty() {
        return s2.empty()&&s1.empty();
    }
}

xil324 commented 2 years ago

思路：使用两个栈，栈A正常操作，在pop的时候，看栈B是否为空，如果为空，则将元素依次pop出，然后加入栈B，这样栈B的元素就是先进先出

···

class MyQueue(object):

def __init__(self):
    self.stack1 = [];
    self.stack2 = [];

def push(self, x):
    """
    :type x: int
    :rtype: None
    """
    self.stack1.append(x); 

def pop(self):
    """
    :rtype: int
    """
    self.peek(); #check if self.stack2 is empty 
    return self.stack2.pop(); 

def peek(self):
    """
    :rtype: int
    """
    if len(self.stack2) == 0:
        while self.stack1:
            self.stack2.append(self.stack1.pop()); 
    return self.stack2[-1]; 

def empty(self):
    """
    :rtype: bool
    """
    return len(self.stack1)==0 and len(self.stack2)==0;

···

xixiao51 commented 2 years ago

思路

用两个栈来实现队列。

代码

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }

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

    public int pop() {
        while(!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        int pop = stack2.pop();
        while(!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        return pop;
    }

    public int peek() {
        while(!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        int peek = stack2.peek();
        while(!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        return peek;
    }

    public boolean empty() {
        return stack1.isEmpty();
    }
}

复杂度分析

- 时间复杂度： ◦ push：O(1) ◦ pop：O(N) ◦ peek：O(N) ◦ empty：O(1)

空间复杂度： ◦ push：O(1) ◦ pop：O(N) ◦ peek：O(N) ◦ empty：O(1)

LyuliangLiu commented 2 years ago

Idea

Push to stack1: O(1); Pop: reversely move all from stack1 to stack2. For every n pops, only the first takes O(N), the rest take O(1) each.

Code

class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

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

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

Complexity

push: O(1)
pop: amortized O(1)
empty(): O(1)
peek(): If use another variable to keep track of the front: O(1); Otherwise amortized O(1)

m908 commented 2 years ago

思路

一个栈保存输入数据，一个栈作为输出，当需要输出时判断输出栈是否为空，不为空直接输出栈顶，为空则从输入栈中获取数据

代码

class MyQueue {
public:
    MyQueue() {    
    }

    void readFromInput() {
        int index = mStackInput.size();
        for(int i = 0; i < index; i++)
        {
            mStackOutput.push(mStackInput.top());
            mStackInput.pop();
        }
    }

    void push(int x) {
        mStackInput.push(x);
    }

    int pop() {
        int result = -1;
        if(!mStackOutput.empty())
        {
            result = mStackOutput.top();
            mStackOutput.pop();
        }
        else if(mStackOutput.empty() && !mStackInput.empty())
        {
            readFromInput();
            result = mStackOutput.top();
            mStackOutput.pop();
        }
        return result;
    }

    int peek() {
        if(!mStackOutput.empty())
        {
            return mStackOutput.top();
        }
        else if(mStackOutput.empty() && !mStackInput.empty())
        {
            readFromInput();
            return mStackOutput.top();
        }
        else
            return -1;
    }

    bool empty() {
        if(mStackOutput.empty() && mStackInput.empty())
            return true;
        else
            return false;
    }

private:
    stack<int> mStackInput;
    stack<int> mStackOutput;
};

复杂度

时间复杂度

push() :O(1)
pop():O(n)
peek():O(n)
empty():O(1)
空间复杂度

O(n)

MoonLee001 commented 2 years ago

思路

使用两个数组实现

代码

var MyQueue = function() {
  this.in = [];
  this.out = [];
}
MyQueue.prototype.push = function (x) {
  this.in.push(x);
}
MyQueue,prototypt.peek = function() {
  if (this.out.length == 0) {
    const n = this.in.length;
    for (let i = 0; i < n; i++) {
      this.out.push(this.in.pop());
    }
  }
  return this.out[this.out.length - 1];
}
MyQueue,prototypt.pop = function() {
  if (this.out.length == 0) {
    const n = this.in.length;
    for (let i = 0; i < n; i++) {
      this.out.push(this.in.pop());
    }
  }
  return this.out.pop();
}
MyQueue,prototypt.empty = function() {
  return this.in.length === 0 && this.out.length === 0;
}

复杂度分析

时间复杂度： push: O(1) peek: O(n) pop: O(n) empty: O(1)
空间复杂度： O(n)

kbfx1234 commented 2 years ago

// 4-5 cpp
class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> stIn;
    stack<int> stOut;

    MyQueue() {

    }

    /** Push element x to the back of queue. */
    void push(int x) {
        stIn.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if (stOut.empty()) {
            while(!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;

    }

    /** Get the front element. */
    int peek() {
        int res = this->pop();
        stOut.push(res);
        return res;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

/**
 * 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();
 * bool param_4 = obj->empty();
 */

wenliangchen commented 2 years ago

思路

维护两个栈，一个专门用来入，另一个在出时负责倒一下。

代码

class MyQueue {
    Stack<Integer> st;
    Stack<Integer> ans;
    int f;

    public MyQueue() {
        st = new Stack<>();
        ans = new Stack<>();
    }

    public void push(int x) {
        if(st.empty()){
            f =x;
        }

        st.push(x);
    }

    public int pop() {
        if(ans.empty()){
            while(!st.empty()){
                ans.push(st.pop());
            }
        }
        return ans.pop();
    }

    public int peek() {
        if(!ans.empty()) return ans.peek();

        return f;
    }

    public boolean empty() {

        return ans.empty() && st.empty();
    }

}

复杂度

时间 push: O(1) peek: O(n) pop: O(n) empty: O(1)
空间 O(n)

hyh331 commented 2 years ago

Day5 思路

使用两个栈来实现队列，一个是输入栈，一个是输出栈。

push操作直接压入输入栈即可。输入栈的元素顺序是和队列相反的。
pop操作需要先判断输出栈是否为空，然后将输入栈全部放入到输出栈，此时输出栈的栈顶到栈底的元素排列就和队列中队头到队尾的元素排列一致。
peek操作，使用2中已有的pop函数,注意最后要将出栈的元素放回去。

empty，只需判断两个栈是否为空即可

代码

class MyQueue {
public:
stack<int> StkIn, StkOut;
MyQueue() {

}
//入队，直接将数据x压入StkIn即可
void push(int x) {
    StkIn.push(x);
}
//出队，
int pop() {
    //当StkOut栈为空时，将StkIn的元素全部放入StkOut，
    //这样做StkOut中从栈顶到栈底元素的排列就和队列中从队头到队尾一致。
    if(StkOut.empty()){
        while(!StkIn.empty()){
            StkOut.push(StkIn.top());
            StkIn.pop();
        }
    }
    int result=StkOut.top();
    StkOut.pop();
    return result;
}
//返回队列首部的元素。
int peek() {
    int res=this->pop();//直接使用已经写好的pop函数
    StkOut.push(res);//pop函数中弹出了res，所以要添加回去
    return res;

}
//返回队列是否为空，只需判断两个栈是否都为空即可
bool empty() {
    return StkIn.empty()&&StkOut.empty();
}
};

复杂度分析

时间复杂度：push和empty是O(1)，pop和peek是O(N)
空间复杂度：O(N)

JasonHe-WQ commented 2 years ago

思路：创建入栈和出栈列表，向入栈队列添加元素，当都为空时返回空，当出栈为空时，依次将入栈元素压入，再返回代码：


class MyQueue:

    def __init__(self):
        self.inStack = []
        self.outStack = []

    def push(self, x: int) -> None:
        self.inStack.append(x)

    def pop(self) -> int:
        if not self.empty():
            if self.outStack:
                return self.outStack.pop()
            else:
                while self.inStack:
                    self.outStack.append(self.inStack.pop())
                return self.outStack.pop()
        else:
            return 0

    def peek(self) -> int:
        if self.empty():
            return 0
        if not self.outStack:            
            while self.inStack:
                self.outStack.append(self.inStack.pop())
        val = self.pop()
        self.outStack.append(val)
        return val

    def empty(self) -> bool:
        if not (self.inStack or self.outStack):
            return True
        return False

kite-fly6618 commented 2 years ago

思路：

两个栈实现队列，辅助栈翻转主栈中的元素，获取队列首部的元素，实现pop

代码：

var MyQueue = function() {
    this.stack1 = []
    this.stack2 = []
};

MyQueue.prototype.push = function(x) {
    this.stack1.push(x)
};

MyQueue.prototype.pop = function() {
    if (!this.stack2.length) {
        while(this.stack1.length) {
            this.stack2.push(this.stack1.pop())
        }
    }
    return this.stack2.pop()
};

MyQueue.prototype.peek = function() {
    return this.stack2[this.stack2.length-1] || this.stack1[0]
};

MyQueue.prototype.empty = function() {
    return this.stack2.length == 0 && this.stack1.length == 0
};

复杂度：

时间复杂度: O(n)
空间复杂度: O(n)

liuguang520-lab commented 2 years ago

思路

利用两个栈来实现队列的功能，一个栈用来接受输入，一个栈接受是输出，如果输出栈没有数字了就从输入栈中添加

code

class MyQueue {
public:
    MyQueue() {

    }

    void push(int x) {
        s1_input.push(x);
    }

    int pop() {
        if(s1_input.size() == 0 &&s2_output.size() == 0)
        {//判断队列中是否有元素
            exit(0);
        }
        if(!s2_output.empty())//输出栈有元素就直接从输出栈输出
        {
            int i = s2_output.top();
            s2_output.pop();
            return i;
        }
        else
        {
            while(!s1_input.empty())
            {
                s2_output.push(s1_input.top());
                s1_input.pop();
            }
            int i = s2_output.top();
            s2_output.pop();
            return i;
        }
    }

    int peek() {//和pop函数一样，少了删除
        if(s1_input.size() == 0 &&s2_output.size() == 0)
        {
            exit(0);
        }
        if(!s2_output.empty())
        {
            int i = s2_output.top();
            return i;
        }
        else
        {
            while(!s1_input.empty())
            {
                s2_output.push(s1_input.top());
                s1_input.pop();
            }
            int i = s2_output.top();
            return i;
        }
    }

    bool empty() {
        return (s1_input.empty() && s2_output.empty());
    }
private:
    stack<int> s1_input;
    stack<int> s2_output;
};

复杂度分析

时间复杂度 O（1）
空间复杂度O(n)

webcoder-hk commented 2 years ago

class MyQueue(object):
    def __init__(self):
        self.stack = MyStack()
        self.tmp = MyStack()

    def push(self, x):
        while self.stack.size()>0:
            self.tmp.push(self.stack.pop())
        self.stack.push(x)
        while self.tmp.size()>0:
            self.stack.push(self.tmp.pop())

    def pop(self):
        if self.stack.size()>0:
            return self.stack.pop()

    def peek(self):
        if self.stack.size()>0:
            return self.stack.peek()

    def empty(self):
        return self.stack.empty()

class MyStack(object):
    def __init__(self):
        self.data = []

    def push(self, x):
        self.data.append(x)

    def pop(self):
        if len(self.data)>0:
            return self.data.pop()

    def peek(self):
        if len(self.data)>0:
            return self.data[-1]

    def empty(self):
        return len(self.data)==0

    def size(self):
        return len(self.data)

AConcert commented 2 years ago

class MyQueue {
    stack: number[] = [];
    constructor() {

    }

    push(x: number): void {
        this.stack.push(x);
    }

    pop(): number {
        const top = this.stack[0];
        // this.stack.splice(0, 1);
        for (let index = 1; index < this.stack.length; index++) {
            this.stack[index - 1] = this.stack[index];
        }
        this.stack.pop();
        return top;
    }

    peek(): number {
        return this.stack[0]
    }

    empty(): boolean {
        if (this.stack.length <= 0) {
            return true;
        }
        return false;
    }
}

leetcode-pp / 91alg-7-daily-check

【Day 5 】2022-04-05 - 232. 用栈实现队列 #6

232. 用栈实现队列

入选理由

题目地址

前置知识

题目描述

思路

代码

复杂度

思路

代码

复杂度分析

时间复杂度

空间复杂度

反思

Ideas

Code

Complexity

思路：第一次只用了一个stack，不符合题目要求两个stack

代码

思路二：两个stack

复杂度分析

思路

代码

复杂度

Code

Complexity

思路

思路

代码

复杂度分析

思路

代码

复杂度分析

思路

代码

复杂度

思路

代码

复杂度分析

思路

代码

232. 用栈实现队列

思路

复杂度

摊还分析

代码

Problem 232. Implement Queue using Stacks

Algorithm

Complexity

Code

leetcode.232. 用栈实现队列

思路：

代码实现：

复杂度分析：

思路

代码

复杂度分析

Analysis

Code

Complexity:

题目地址(232. 用栈实现队列)

题目描述

思路

代码

思路

代码

复杂度分析

思路

代码

复杂度分析

思路

代码

idea

code

complexity

思路

复杂度

代码