99클럽 코테 스터디 4일차 TIL ✒️Stack을 이용해서 Queue 구현

 

 

✅ 오늘의 학습 키워드

• Queue와 Stack 구조 알기
• Stack만으로 Queue 구현하기

---

🔍 오늘의 문제 분석

↘️ 오늘의 문제 바로가기 ↘️

 

• 스택으로 큐의 push, pop, peek, empty 기능을 구현
• 스택의 순서를 반전시키기 위해 두 개의 스택을 선언

 

오늘의 문제는 스택이 큐처럼 기능하도록 구현하는 문제이다. 큐는 FIFO 선입선출의 구조를 가지고 있고 스택은 LIFO 후입선출의 구조를 가지고 있다. 그래서 push 또는 pop을 수행할 때 미리 스택에 있는 요소들의 순서를 반전시켜야 한다. 이렇게 반전시키기 위해서 요소를 잠시 저장하기 위해 또 다른 스택을 이용한다.

 

---

✨ 오늘의 회고

📌내가 적은 답안📌

import java.util.Stack;

class MyQueue {

    private Stack<Integer> s1;
    private Stack<Integer> s2;

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    public void push(int x) {
        while (!s1.empty()) {
            s2.push(s1.pop());
        }

        s1.push(x);

        while (!s2.empty()) {
            s1.push(s2.pop());
        }
    }
    
    public int pop() {
        // if (s1.empty()) return -1;
        return s1.pop();
    }
    
    public int peek() {
        // if (s1.empty()) return -1;
        return s1.peek();
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

 

 

스택과 큐는 선형 자료구조이지만 동작 방식이 다르기 때문에 메서드도 비슷하지만 이름이 다르다.

 

📒 스택

• push
• pop
• peek/top

📒 큐

• add/offer
• remove/poll
• peek

 

✏️여기서 선형 자료구조란?

 

선형 자료구조는 데이터가 순차적/일렬로 저장되는 구조를 의미한다. 각 요소는 논리적으로 연속적으로 배치되어서 순차적인 탐색이 가능하다. 연속된 메모리 공간을 사용한다. 요소는 한 방향으로만 연결되어 있어서 특정 방식으로만 삽입하거나 삭제할 수 있다. 배열, 연결 리스트, 스택, 큐, 덱 등이 대표적인 선형 자료구조이다.

 

스택과 큐를 응용해서 DFS와 BFS를 구현할 수 있다고 해서 좀 더 알아봤다.

 

스택은 DFS(깊이 우선 탐색) 알고리즘에 적합한 자료구조인데, 왜냐하면 DFS는 최대한 깊이 들어간 후, 더 이상 갈 곳이 없으면 되돌아오는 방식으로 그래프를 탐색한다.

 

BFS는 시작 노드에서 가까운 노드를 먼저 탐색하고 점점 멀리 있는 노드를 탐색하는 방식인데 큐를 활용해서 구현할 수 있다. BFS는 최단 경로 문제에서 유용하다.