LeetCode 솔루션 분류

[5/5] 225. Implement Stack using Queues

컨텐츠 정보

본문

[LeetCode 시즌 3] 2022년 5월 5일 문제입니다.

https://leetcode.com/problems/implement-stack-using-queues/


[Easy] 225. Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (pushtoppop, and empty).

Implement the MyStack class:

  • void push(int x) Pushes element x to the top of the stack.
  • int pop() Removes the element on the top of the stack and returns it.
  • int top() Returns the element on the top of the stack.
  • boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

  • You must use only standard operations of a queue, which means that only push to backpeek/pop from frontsize and is empty operations are valid.
  • Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

 

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

 

Constraints:

  • 1 <= x <= 9
  • At most 100 calls will be made to pushpoptop, and empty.
  • All the calls to pop and top are valid.

 

Follow-up: Can you implement the stack using only one queue?

관련자료

댓글 3

mingki님의 댓글

  • 익명
  • 작성일
C++
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Implement Stack using Queues.
Memory Usage: 6.7 MB, less than 88.02% of C++ online submissions for Implement Stack using Queues.
class MyStack {
private:
    queue<int> q;
    
public:
    MyStack() {
        
    }
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int n = q.size();
        
        for (int i = 0; i < n - 1; ++i) {
            q.push(q.front()); q.pop();
        }
        int res = q.front(); q.pop();
        return res;
    }
    
    int top() {
        int n = q.size();
        int res = 0;
        
        for (int i = 0; i < n; ++i) {
            res = q.front(); q.pop();
            q.push(res);
        }
        return res;
    }
    
    bool empty() {
        return q.empty();
    }
};

austin님의 댓글

  • 익명
  • 작성일
class MyStack {
public:
    MyStack() {
        
    }
    
    void push(int x) {
        q1.emplace(x);
    }
    
    int pop() {
        while(q1.size() > 1) {
            q2.emplace(q1.front());
            q1.pop();
        }
        int ret = q1.front();
        q1.pop();
        swap(q1, q2);
        return ret;        
    }
    
    int top() {
        while(q1.size() > 1) {
            q2.emplace(q1.front());
            q1.pop();
        }
        int ret = q1.front();
        q1.pop();
        q2.emplace(ret);
        swap(q1, q2);
        return ret;        
    }
    
    bool empty() {
        return q1.empty();
    }
    queue<int> q1;
    queue<int> q2;
};

나무토끼님의 댓글

  • 익명
  • 작성일
Runtime: 65 ms, faster than 5.63% of Python3 online submissions for Implement Stack using Queues.
Memory Usage: 14.1 MB, less than 27.76% of Python3 online submissions for Implement Stack using Queues.

class MyStack:

    def __init__(self):
        self.queue = collections.deque()
        self.temp = collections.deque()

    def push(self, x: int) -> None:
        if self.empty():
            self.queue.append(x)
        else:
            while self.queue:
                self.temp.append(self.queue.popleft())
            self.queue.append(x)
            while self.temp:
                self.queue.append(self.temp.popleft())

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

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

    def empty(self) -> bool:
        if len(self.queue) == 0:
            return True
        else:
            return False
LeetCode 솔루션 357 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 789 명
  • 오늘 방문자 5,095 명
  • 어제 방문자 6,932 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,481 명
알림 0