LeetCode 스택과 큐 225. Implement Stack using Queues, 232. Implement Queue using Stacks

문제에 대한 설명은 링크로 대체

 

225. Implement Stack using Queues

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

 

232. Implement Queue using Stacks

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

 

---

 

스택(Stack)과 큐(Queue)는 프로그래밍의 시작 부터 사용된 고전적인 자료구조 중 하나다.

스택은 LIFO(Last-in-first-out, 후입선출), 큐는 FIFO(First-in-first-out, 선입선출)로 처리된다.

 

 스택은 접시를 쌓고 꺼내는 것과 유사하다.

3개의 접시를 선반에 저장할 때 가장 먼저 저장한 접시는 바닥면에 닿아 있고 그 위로 이후에 저장될 접시가 차곡차곡 쌓인다.

 

 큐는 카페에서 주문을 하기위해 줄을 서있는 고객의 모습과 유사하다.

5명의 손님이 차례로 줄을 서게 될 때, 주문대에 먼저 도착한 고객이 먼저 주문을 한다.

 

간단한 그림으로 예시를 들겠다.

{1, 2, 3} 과 같은 3개의 데이터가 있을 때,

1번이 가장 먼저 저장되고 이후 2번이 저장된다.
3번은 1번과 2번 다음에 저장된다.

이 Stack 자료구조에서 데이터를 조회하게 될 시 가장 먼저 조회되는 데이터는 3번이다.(method: 'peek' or 'pop')

---

 

 큐는 가장 먼저 삽입된 엘리먼트가 가장 먼저 처리되는 자료형이다.

1번, 2번, 3번 순서대로 삽입되고 이중 가장 먼저 사용되는 데이터는 '1번'이다.

---

 스택과 큐는 굉장히 직관적이며 이해하는데 큰 어려움이 없을 것이다.

LeetCode에 재밌는 문제가 있다.

'큐를 이용한 스택 구현'과 '스택을 이용한 큐 구현' 이다.

개념을 이해하고 사용하는데에는 큰 어려움이 없겠지만, 막상 두 자료형을 각각 사용하여 반대의 개념을 구현하려 하니 예상외로 흥미롭다.

 

아래 그림을 살펴보자.

 

 

1번 데이터가 삽입된 후 2번 데이터가 삽입될 때 원래의 Stack 자료구조라면 1번 위에 2번 데이터가 위치해야 한다.

하지만 문제는 1, 2, 3 번의 데이터가 삽입된 이후에 마치 Queue 처럼 FIFO가 되길 요구한다.

데이터를 삽입할 때, 지금까지 적재된 데이터를 임시로 보관할 용도의 큐가 필요하다.

예를들어 2번 데이터를 적재한다면, 1번 데이터를 임시로 보관할 용도의 큐를 사용한다.

 

풀이: 작성자 Github에서 코드 살펴보기

study: 스택을 이용한 큐 구현 · taemin-kwon93/CodingTest@d2b4ce2

 

import java.util.Stack;

public class MyQueue {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> tmpStack = new Stack<>();

    public MyQueue() {}

    public void push(int x) {
        tmpStack.addAll(stack);
        stack.removeAllElements();
        stack.push(x);
        stack.addAll(tmpStack);
        tmpStack.removeAllElements();
    }

    public int pop() {
        return stack.pop();
    }

    public int peek() {
        return stack.peek();
    }

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

 

풀이 설명:

 위 풀이는 push를 제외한 나머지는 기존 stack 메서드를 그대로 사용한다.

데이터를 적재하는 용도의 Stack<Integer> stack 을 선언한다.

임시로 데이터를 보관할 용도의 Stack<Integer> tmpStack 을 선언한다.

 push 메서드는 임시보관 스택에 지금까지 적재된 데이터를 모두 담는다.

기존의 스택은 전부 삭제하고 현재 삽입될 데이터를 추가한다.

임시 보관한 데이터를 전부 추가한다.

임시 데이터를 전부 삭제한다.

 

---

 

 

 

 

 

 

 

 

풀이: 작성자 github에서 코드 살펴보기

study: 큐를 이용한 스택 구현 · taemin-kwon93/CodingTest@5e75986

import java.util.LinkedList;
import java.util.Queue;

public class MyStack {
    Queue<Integer> queue = new LinkedList<>();

    public void push(int x) {
        queue.add(x);

        for (int i = 1; i < queue.size(); i++) {
            System.out.println("test: " + x);
            queue.add(queue.remove());
        }
    }

    public int pop() {
        return queue.remove();
    }

    public int top() {
        if (queue.isEmpty()) {
            return Integer.MIN_VALUE;
        }
        return queue.peek();
    }

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

 

풀이 설명:

push 메서드를 제외한 나머지는 원래 queue의 메서드를 사용.

top 메서드의 경우 큐가 빈값인 경우의 예외를 처리하는 조건문 추가.

 

push 메서드는 queue에 있는 데이터를 뽑아 다시 삽입한다.

queue에 [3, 2, 1] 과 같은 데이터가 있을 때 '4를' 삽입한다면 [4, 3, 2, 1] 이 된다. 이후 반복작업을 통해 아래와 같이 된다.

[1, 4, 3, 2] => [2, 1, 4, 3] => [3, 2, 1, 4]

 

아래 그림을 보자.

1. 4 삽입
2. 데이터 '4'가 삽입된 이후의 모습
3. 3을 remove() 함
4. queue.add(queue.remove()) 의 모습
5. 큐에 있는 데이터 개수 n보다 한번 적게 작업을 반복 (새로 삽입된 데이터는 그대로 둠)