프로그래밍에서 자주 사용되는 두 가지 중요한 자료구조가 바로 Stack(스택)과 Queue(큐)입니다. 이 둘은 데이터를 저장하고 관리하는 방식에서 큰 차이가 있습니다.
1. Stack(스택)란?
스택은 데이터를 후입선출(LIFO, Last In First Out) 방식으로 저장하고 처리하는 자료구조입니다. 즉, 나중에 들어온 데이터가 먼저 나가게 되는 구조입니다.
스택을 쉽게 이해하기 위해서는 책을 쌓는 모습을 떠올리면 됩니다. 책을 쌓을 때 가장 위에 놓은 책을 먼저 꺼내게 되죠. 즉, 가장 나중에 쌓은 책이 가장 먼저 사용됩니다. 이처럼 스택은 데이터를 위쪽에서만 삽입하고 삭제할 수 있습니다.
스택의 주요 연산:
- push: 스택의 맨 위에 데이터를 삽입.
- pop: 스택의 맨 위에서 데이터를 제거하고 반환.
- peek: 스택의 맨 위에 있는 데이터를 제거하지 않고 조회.
스택의 활용 사례:
- 재귀 함수 호출: 함수가 재귀적으로 호출될 때, 함수의 상태를 저장하고 복귀할 때 스택을 사용합니다.
- 문자열 역순 변환: 문자열을 거꾸로 출력할 때, 스택을 이용하여 문자들을 저장한 후 출력할 수 있습니다.
- 괄호 검사: 프로그래밍 언어에서 괄호의 짝을 검사할 때 스택이 자주 사용됩니다.
- DFS(깊이 우선 탐색): 그래프나 트리 탐색에서 한 경로를 끝까지 탐색한 후, 더 이상 갈 곳이 없을 때 스택을 이용해 이전 단계로 되돌아가며 탐색을 이어가는 방식입니다.
구현(Java)
public class Stack {
private int[] stack;
private int top;
private int maxSize;
// 스택 초기화
public Stack(int size) {
this.maxSize = size;
this.stack = new int[size];
this.top = -1;
}
// 스택에 데이터를 삽입 (push)
public void push(int value) {
if (isFull()) {
System.out.println("스택이 가득 찼습니다.");
return;
}
stack[++top] = value;
}
// 스택에서 데이터를 제거하고 반환 (pop)
public int pop() {
if (isEmpty()) {
System.out.println("스택이 비어있습니다.");
return -1;
}
return stack[top--];
}
// 스택의 맨 위 데이터를 반환 (peek, 삭제하지 않음)
public int peek() {
if (isEmpty()) {
System.out.println("스택이 비어있습니다.");
return -1;
}
return stack[top];
}
// 스택이 비었는지 확인
public boolean isEmpty() {
return top == -1;
}
// 스택이 가득 찼는지 확인
public boolean isFull() {
return top == maxSize - 1;
}
}2. Queue(큐)란?
큐는 데이터를 선입선출(FIFO, First In First Out) 방식으로 저장하고 처리하는 자료구조입니다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조입니다.
큐는 일상생활에서 줄을 서는 모습을 떠올리면 쉽게 이해할 수 있습니다. 먼저 줄을 선 사람이 먼저 서비스를 받듯이, 큐에 들어간 데이터도 먼저 들어온 것이 먼저 처리됩니다. 큐는 데이터의 삽입과 삭제가 각각 다른 쪽에서 이루어집니다.
큐의 주요 연산:
- enqueue: 큐의 뒤쪽(끝부분)에 데이터를 삽입.
- dequeue: 큐의 앞쪽(첫부분)에서 데이터를 제거하고 반환.
- peek: 큐의 앞쪽에 있는 데이터를 제거하지 않고 조회.
큐의 활용 사례:
- 프린터 작업 대기열: 프린터가 여러 작업을 처리할 때, 먼저 요청된 작업부터 차례대로 처리됩니다.
- 프로세스 스케줄링: 운영체제에서 여러 프로세스를 관리할 때, 큐를 사용하여 프로세스가 순서대로 실행됩니다.
- BFS(너비 우선 탐색): 그래프 탐색에서 BFS는 큐를 이용해 탐색 순서를 관리합니다.
구현
public class Queue {
private int[] queue;
private int front;
private int rear;
private int maxSize;
private int nItems;
// 큐 초기화
public Queue(int size) {
this.maxSize = size;
this.queue = new int[size];
this.front = 0;
this.rear = -1;
this.nItems = 0;
}
// 큐에 데이터를 삽입 (enqueue)
public void enqueue(int value) {
if (isFull()) {
System.out.println("큐가 가득 찼습니다.");
return;
}
if (rear == maxSize - 1) {
rear = -1; // 원형 큐처럼 동작하기 위해 rear를 초기화
}
queue[++rear] = value;
nItems++;
}
// 큐에서 데이터를 제거하고 반환 (dequeue)
public int dequeue() {
if (isEmpty()) {
System.out.println("큐가 비어있습니다.");
return -1;
}
int temp = queue[front++];
if (front == maxSize) {
front = 0; // 원형 큐처럼 동작하기 위해 front를 초기화
}
nItems--;
return temp;
}
// 큐의 앞쪽 데이터를 반환 (peek, 삭제하지 않음)
public int peek() {
if (isEmpty()) {
System.out.println("큐가 비어있습니다.");
return -1;
}
return queue[front];
}
// 큐가 비었는지 확인
public boolean isEmpty() {
return nItems == 0;
}
// 큐가 가득 찼는지 확인
public boolean isFull() {
return nItems == maxSize;
}
}3. Stack과 Queue의 차이
4. Stack과 Queue 선택 시 고려할 점
- 처리 순서가 중요한가?: 처리해야 할 데이터의 순서가 중요하다면 큐를 사용하는 것이 적합합니다. 반면, 마지막에 추가된 데이터부터 처리해야 한다면 스택이 적합합니다.
- 메모리 효율성: 스택은 재귀 함수 호출 등에서 메모리를 효율적으로 사용할 수 있지만, 과도한 재귀는 스택 오버플로를 유발할 수 있습니다. 반면, 큐는 일정한 크기로 순차적으로 처리하는 작업에 적합합니다.
Spring, Django 개발 블로그