스택과 큐
스택과 큐 (Stack & Queue)
스택(Stack)과 큐(Queue)는 데이터를 일시적으로 저장하고 관리하기 위한 가장 기본적인 선형 자료구조입니다. 두 자료구조는 데이터를 삽입하고 삭제하는 방식, 즉 데이터의 접근 순서에서 뚜렷한 차이를 보입니다.
📚 스택 (Stack): LIFO
- 개념 (Concept) : 후입선출(LIFO, Last-In, First-Out). 가장 마지막에 들어온 데이터가 가장 먼저 나가는 구조입니다.
- 비유 (Analogy) : 접시를 바닥부터 차곡차곡 쌓아 올리고, 맨 위의 접시부터 사용하는 모습에 비유할 수 있습니다.
- 주요 연산 (Operations)
> * `push(item)`: 스택의 가장 윗부분(top)에 데이터를 추가합니다. > * `pop()`: 스택의 가장 윗부분(top)에서 데이터를 제거하고 반환합니다. > * `peek()`: 스택의 가장 윗부분(top)에 있는 데이터를 제거하지 않고 확인합니다.
- 활용 사례 (Use Cases)
> * 함수 호출 스택 : 프로그램에서 함수가 호출될 때의 정보를 저장하는 메모리 영역 (재귀 함수 호출 시 중요). > * 괄호 유효성 검사 : 코드에서 괄호(`()`, `{}`, `[]`)가 올바르게 짝지어졌는지 검사할 때 사용됩니다. > * 웹 브라우저 뒤로가기 : 방문한 페이지의 URL을 스택에 저장하여 뒤로가기 기능을 구현합니다.
🎟️ 큐 (Queue): FIFO
- 개념 (Concept) : 선입선출(FIFO, First-In, First-Out). 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조입니다.
- 비유 (Analogy) : 은행 창구나 놀이공원에서 줄을 서서 기다리는 모습에 비유할 수 있습니다.
- 주요 연산 (Operations)
> * `enqueue(item)`: 큐의 가장 뒷부분(rear)에 데이터를 추가합니다. > * `dequeue()`: 큐의 가장 앞부분(front)에서 데이터를 제거하고 반환합니다. > * `peek()`: 큐의 가장 앞부분(front)에 있는 데이터를 제거하지 않고 확인합니다.
- 활용 사례 (Use Cases)
> * 너비 우선 탐색 (BFS, Breadth-First Search) : 그래프 탐색 시, 방문할 노드를 순서대로 큐에 저장하여 사용합니다. > * 프린터 작업 큐 : 여러 인쇄 요청을 순서대로 처리하기 위해 큐에 작업을 저장합니다. > * 메시지 큐 (Message Queue) : 비동기적 데이터 처리를 위해 요청을 큐에 저장하고, 다른 프로세스가 이를 순차적으로 처리하는 데 사용됩니다. (e.g., RabbitMQ, Kafka) > * 운영체제 태스크 스케줄링 : CPU가 처리할 작업들을 큐에 저장하고 순서대로 처리합니다.
💡 개발자 핵심 Point
- 스택과 큐는 자료구조 그 자체로도 중요하지만, 다른 복잡한 알고리즘(그래프 탐색, 트리 순회 등)을 구현하는 데 핵심적인 도구로 사용됩니다.
- 스택으로 큐 구현 : 두 개의 스택을 사용하여 큐를 구현할 수 있습니다. (enqueue는 스택1에 push, dequeue는 스택2가 비었을 때만 스택1의 모든 원소를 pop하여 스택2에 push한 후, 스택2에서 pop)
- 큐로 스택 구현 : 두 개의 큐를 사용하여 스택을 구현할 수 있습니다. (push할 때마다 데이터를 큐1에 넣고, 큐2에 있던 모든 데이터를 큐1으로 옮긴 후, 두 큐의 역할을 바꿈)
- 덱(Deque, Double-ended Queue)은 스택과 큐의 특징을 모두 가진 자료구조로, 양쪽 끝(front, rear)에서 모두 삽입과 삭제가 가능합니다.
