[자료구조] 스택(Stack)과 큐(Queue)

스택(Stack)이란?

---

🔍 개념

스택이란 쌓아 올린다는 의미로 책을 쌓는 것처럼 차곡차곡 쌓아 올리는 자료 구조를 말한다.

🔍 스택의 특징

스택은 Last In First Out (후입선출) 방식으로 가장 마지막에 들어간 자료가 가장 먼저 삭제된다.

위의 이미지처럼 구조와 크기가 같은 자료를 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근이 가능하다.
삽입될 새 자료는 top이 가리키고 있는 자료의 위에만 쌓인다. 뿐만 아니라 삭제할 때도 top을 통해서만 삭제할 수 있다.

📍 스택에 자료 추가, 제거

삽입, 삭제 연산은 다음과 같다.

 

import java.util.Stack;

public class Main {
    public static void main(String[] args) {

        Stack<Integer> st = new Stack<>();
        st.push(1);
        st.push(2);
        st.push(3);

        System.out.println(st);        // [1, 2, 3]

        st.pop();

        System.out.println(st);        // [1, 2]

        st.pop();

        System.out.println(st);        // [1]

        st.clear();

        System.out.println(st);        // []

    }
}

자바에서 스택은 Stack을 객체 인스턴스로 생성하여 사용하며 push 메서드를 통해 값을 넣어줄 수 있다.
이 때, [1, 2, 3]의 순서로 값이 들어가게 된다.

pop을 하게 되면 [1, 2, 3]이라고 보았을 때 뒤에서부터 하나씩 빠지게 된다.

clear는 스택 내부에 있는 모든 내용을 삭제한다.

활용 예시

• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

여담

비어있는 스택 내부의 원소를 출력하려고 하면 stack underflow가 되며, 스택이 넘치는 경우 stack overflow라고 한다...

헐..

큐(Queue)란?

---

🔍 개념

큐는 사전적으로 대기열이나 대기열에서 기다리는 행위를 말한다.
대기열에서는 먼저 줄을 선 사람이 먼저 무엇인가를 할 수 있는 사회적 합의(?)가 있다. 따라서 큐는 스택과 다르게 First In First Out(선입선출) 방식을 취하는 자료구조를 말한다.

🔍 큐의 특징

스택은 top이라는 정해진 위치에서 push와 pop을 통해 자료를 추가, 삭제하는 반면 큐는 한쪽 끝에서는 추가연산을 수행하고 다른쪽 끝에서는 삭제 연산을 수행한다.
여기에서 삭제 연산만 수행하는 곳을 front라 정의하고, 추가 연산만 수행하는 곳을 rear라 정의한다. 가장 첫 원소와 끝 원소를 통해 큐에 접근할 수 있다.

이 때, 큐의 rear에서 이루어지는 삽입 연산을 enQueue(인큐), front에서 이루어지는 삭제 연산을 deQueue(디큐)라고 한다.

front에서 삭제 연산이 이루어지므로 front에 가까운 자료가 먼저 들어와 있는 자료라고 볼 수 있다(rear에 가까운 원소는 당연히 늦게 들어온 것).

📍 큐에 자료 추가, 제거

 

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

public class Main {
    public static void main(String[] args) {

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

        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);

        System.out.println(q);        // [1, 2, 3, 4]

        q.poll();

        System.out.println(q);        // [2, 3, 4]

        q.poll();

        System.out.println(q);        // [3, 4]

        q.clear();

        System.out.println(q);        //[]

    }
}

스택에서는 push와 pop 메서드를 사용했지만 큐에서는 추가 시 offer, 삭제 시 poll 메서드를 사용한다.
마찬가지로 clear는 큐 내부의 모든 원소를 삭제한다.

 

활용 예시

---

• 프린터 인쇄 대기열
• 너비 우선 탐색(BFS, Breadth-First Search)의 구현
• 캐시 구현