232. Implement Queue using Stacks - cocoder39/coco39_LC GitHub Wiki

232. Implement Queue using Stacks

  • when push, push to input stack
  • when pop, first check if output stack has element to pop. if not, move elements from input stack to output stack (last in element becomes last out)
  • note we need to first empty output stack then transfer items from input stack to output stack
  • O(1) for push and amortized O(1) for pop
class MyQueue:

    def __init__(self):
        self.input = []
        self.output = []
        
    def push(self, x: int) -> None:
        self.input.append(x)
        
    def pop(self) -> int:
        if not self.output:
            self.transfer()
        return self.output.pop()
        

    def peek(self) -> int:
        if not self.output:
            self.transfer()
        return self.output[-1]

    def empty(self) -> bool:
        return not self.input and not self.output

    def transfer(self):
        while self.input:
            item = self.input.pop()
            self.output.append(item)

=============================================

   stack:          10      1
                    9      2
                    8      3
                    7      4
                    6      5
                   ---    ---
                   new    old
queue:
10
9
8
7
6
5
4
3
2
1

time: push() O(1), pop() amortized O(1) (left time of an element is 2 push operations and 2 pop operations)

class Queue {
public:
    // Push element x to the back of queue.
    void push(int x) {
        input.push(x);
    }

    // Removes the element from in front of queue.
    void pop(void) {
        i2o();
        output.pop();
    }

    // Get the front element.
    int peek(void) {
        i2o();
        return output.top();
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return input.empty() && output.empty();
    }
private:
    stack<int> input, output;
    void i2o() {
        if (output.empty()) {
            while (! input.empty()) {
                int tmp = input.top();
                input.pop();
                output.push(tmp);
            }
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️