99클럽 코테 스터디 5일차 TIL + 큐로 스택 구현하기

 

 

오늘의 학습 키워드

• 스택을 큐로 구현하기

 

문제 링크

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

 

문제 내용

• 큐를 이용하여 스택을 구현
• void push(int x) : 스택 맨 위에 원소 x를 삽입
• int pop() : 맨 위의 원소를 제거하고 반환
• int top() : 맨 위의 원소 반환
• boolean empty(): 스택이 비어있는지 여부 확인

 

문제 해결 방법

일단 스택과 큐의 개념을 다시 짚어보면서 두 자료구조의 차이점을 파악했다. 스택은 LIFO(Last In First Out), 큐는 FIFO(First In First Out)이다. 문제를 푸는 방법은 총 2가지가 있다.

 

1. 큐 2개를 이용했다. q1이 기존 큐, q2를 새로운 큐(보조 큐)라고 가정한다.

 

[push]

1. 새 값을 q2에 넣는다.

2. q1의 모든 값을 뒤로 옮긴다.

3. q1과 q2를 swap 한다.

 

[pop, top, empty]

Queue의 메소드를 사용한다. pop은 poll, top은 peek, empty는 isEmpty를 사용한다.

 

 

2. 큐 1개를 이용했다.

 

[push]

1. 큐에 값을 추가한다.

2. 기존 원소들을 순서대로 회전시켜 마지막에 들어온 값이 앞으로 오게 한다.

 

[pop, top, empty]

Queue의 메소드를 사용한다. pop은 poll, top은 peek, empty는 isEmpty를 사용한다.

 

 

구현 코드

1. 큐 2개 이용하기

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

class MyStack {

    private Queue<Integer> q1;
    private Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    public void push(int x) {
        q2.offer(x);

        while(!q1.isEmpty()) {
            q2.offer(q1.poll());
        }

        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
    
    public int pop() {
        return q1.poll();
    }
    
    public int top() {
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

 

 

2. 큐 1개 이용하기

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

class MyStack {

    private Queue<Integer> q;

    public MyStack() {
        q = new LinkedList<>();
    }

    public void push(int x) {
        q.offer(x);
        int size = q.size();
        for (int i = 0; i < size - 1; i++) {
            q.offer(q.poll());
        }
    }

    public int pop() {
        return q.poll();
    }

    public int top() {
        return q.peek();
    }

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

 

 

새롭게 배운 것

1. Queue는 다음과 같이 생성한다.

Queue<Integer> queue = new LinkedList<>();

 

2. 기능이 같더라도 Stack에서 사용하는 메소드명과 Queue에서 사용하는 메소드명이 다르다.

// 데이터 넣기
stack.push(1);
queue.offer(1);

// 데이터 꺼내기
stack.pop();
queue.poll();