[LeetCode] 232. Implement Queue using Stacks

 

https://leetcode.com/problems/implement-queue-using-stacks/description/?envType=daily-question&envId=2024-01-29

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Implement Queue using Stacks

문제 유형 : 스택/큐

문제 난이도 : Easy

 

문제

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

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

 

두 개의 스택으로 큐의 기본적인 기능들을 구현하시오.

• void push(int x): 요소 x를 큐의 맨 뒤에 삽입합니다.
• int pop(): 맨 앞에 있는 요소를 삭제하고 반환합니다.
• int peek(): 큐의 맨 앞에 있는 요소를 반환합니다.
• boolean empty(): 큐가 비어있다면 true를, 아니면 false를 반환합니다.

 

 

풀이

두 스택에서 하나를 메인스택, 하나를 서브스택으로 한다.

• void push(int x): 메인스택에 요소를 삽입한다.
• int pop(): 메인스택의 크기가 n개라면, n-1개를 빼서 서브스택에 저장시킨다. 마지막 요소도 pop하여 변수에 따로 저장한다.
  서브스택의 요소들을 메인스택에 다시 넣는다. 스택에 LIFO로 넣었다가 다시 빼는 것이여서 순서는 다시 유지된다.
• int peek(): pop()에서 마지막 요소를 빼는 대신, 변수에 값을 저장하기만 하고, 반환한다.
• boolean empty(): 메인스택이 비어있는지에 대해 반환하면 된다. 서브스택은 연산 전 항상 비어있다.

 

향상된 버전: 

입력용 스택과 출력용 스택을 만든다.

• void push(int x): 입력스택에 요소를 삽입한다.
• int pop(): 출력스택이 비어있으면, 입력스택들의 모든 요소들을 pop하여 출력스택에 push한다. 이 때, 순서가 역전되어 먼저 온 요소들이 먼저 나갈 수 있게된다.
  출력스택에서 원소를 하나 pop하여 원소를 제거한다.
• int peek(): 출력스택의 맨 위의 원소를 반환한다.
• boolean empty(): 입력스택과 출력스택이 모두 비어있다면 true, 아니면 false이다.

 

코드

C++

class MyQueue {
    stack<int> mainStack;
    stack<int> subStack;
public:
    MyQueue() {
        
    }
    
    void push(int x) {
        mainStack.push(x);
    }
    
    int pop() {
        int n = mainStack.size();
        for(int i = 0; i < n-1; i++) {
            subStack.push(mainStack.top());
            mainStack.pop();
        }

        int popped = mainStack.top();
        mainStack.pop();

        while(!subStack.empty()) {
            mainStack.push(subStack.top());
            subStack.pop();
        }

        return popped;
    }
    
    int peek() {
        int n = mainStack.size();
        for(int i = 0; i < n-1; i++) {
            subStack.push(mainStack.top());
            mainStack.pop();
        }

        int top = mainStack.top();

        while(!subStack.empty()) {
            mainStack.push(subStack.top());
            subStack.pop();
        }

        return top;
    }
    
    bool empty() {
        return mainStack.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();
 */

 

 

 

C++ - 향상된 버전

class MyQueue {
    stack<int> i,o;
public:
    MyQueue() {
        
    }
    
    void push(int x) {
        i.push(x);
    }
    
    int pop() {
        int x;
        if(o.empty()) {
            while(!i.empty()) {
                o.push(i.top());
                i.pop();
            }
        }
        x = o.top();
        o.pop();

        return x;
    }
    
    int peek() {
        int x;
        if(o.empty()) {
            while(!i.empty()) {
                o.push(i.top());
                i.pop();
            }
        }
        x = o.top();
        return x;
    }
    
    bool empty() {
        return i.empty() && o.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();
 */