99클럽 코테 스터디 14일차 TIL + 스택/큐(C++)

문제

[리트코드] 225. Implement Stack using Queues

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

 

코드

#include <queue>
using namespace std;

class MyStack {
public:
    queue<int> queue1, queue2;

    MyStack() {
    }

    // push 연산
    void push(int x) {
        queue1.push(x);
    }

    // pop 연산
    int pop() {
        while (queue1.size() > 1) {
            queue2.push(queue1.front());
            queue1.pop();
        }
        int top = queue1.front();
        queue1.pop();
        swap(queue1, queue2);
        return top;
    }

    // top 연산
    int top() {
        while (queue1.size() > 1) {
            queue2.push(queue1.front());
            queue1.pop();
        }
        int top = queue1.front();
        queue2.push(top);  // top 값을 queue2에 유지
        queue1.pop();
        swap(queue1, queue2);
        return top;
    }

    // empty 연산
    bool empty() {
        return queue1.empty();
    }
};

 

주석 있는 코드

#include <queue>
using namespace std;

class MyStack {
public:
    // 두 개의 큐로 스택을 구현함
    queue<int> queue1, queue2;

    // 생성자 (특별히 초기화할 내용 없음)
    MyStack() {
    }

    // push 연산: 스택에 원소 x를 추가
    void push(int x) {
        queue1.push(x); // queue1에 x를 삽입
    }

    // pop 연산: 스택의 최상단 원소를 제거하고 반환
    int pop() {
        // queue1에 원소가 하나 남을 때까지 queue2로 이동
        while (queue1.size() > 1) {
            queue2.push(queue1.front()); // queue2에 queue1의 첫 원소 이동
            queue1.pop(); // queue1에서 해당 원소 제거
        }
        // queue1의 마지막 원소가 스택의 최상단 원소
        int top = queue1.front();
        queue1.pop(); // 최상단 원소 제거

        // queue1과 queue2를 교환하여 queue1이 항상 데이터가 있는 큐가 되도록 유지함
        swap(queue1, queue2);

        // 최상단 원소 반환
        return top;
    }

    // top 연산: 스택의 최상단 원소를 반환하지만 제거하지 않음
    int top() {
        // queue1에 원소가 하나 남을 때까지 queue2로 이동
        while (queue1.size() > 1) {
            queue2.push(queue1.front()); // queue2에 queue1의 첫 원소 이동
            queue1.pop(); // queue1에서 해당 원소 제거
        }
        // queue1의 마지막 원소가 스택의 최상단 원소
        int top = queue1.front();
        queue2.push(top); // queue2에 최상단 원소 다시 삽입하여 유지

        queue1.pop(); // queue1에서 해당 원소 제거

        // queue1과 queue2를 교환하여 queue1이 항상 데이터가 있는 큐가 되도록 유지함
        swap(queue1, queue2);

        // 최상단 원소 반환
        return top;
    }

    // empty 연산: 스택이 비어 있는지 확인
    bool empty() {
        return queue1.empty(); // queue1이 비어 있으면 스택도 비어 있음
    }
};

 

풀이

두 개의 큐(queue1, queue2)를 사용해 스택을 구현하는 문제.

 

두 개의 큐가 필요한 이유

• 스택은 LIFO 구조이지만 큐는 FIFO이기 때문에, 이를 큐로 구현하려면 두 개의 큐를 사용해 원소 순서를 조작해야한다.
• 예를 들어, pop과 top 연산에서 queue1의 마지막 원소에 접근하기 위해 다른 큐(queue2)로 원소를 옮겨야 한다. 이를 통해 스택처럼 마지막에 추가된 원소를 최상단으로 다룰 수 있다.

 

<연산 설명>

• push: queue1에 값만 추가
• pop: queue1의 모든 원소를 queue2로 이동해 마지막 원소만 남기고 제거함. 이후 queue1과 queue2를 교환해 queue1이 항상 데이터를 가지도록 유지함.
• top: queue1의 마지막 원소를 가져오되, queue2에 다시 삽입해 원래 상태를 유지함.
• empty: queue1이 비어 있는지 확인해 스택의 비어 있음 여부를 반환함.

 

회고

리트코드에서 알고리즘 풀이는 이번에 처음인데 영어의 장벽에 어쩔 수 없이 겁이 났다.. 앞으로 리트코드 문제도 조금씩 풀어봐야지!