[자료구조] 스택(Stack), 큐(QUEUE) 개념

스택 (Stack)이란?

 

스택(Stack)은 데이터 구조의 하나로, 데이터를 쌓아 올린 형태를 가진 구조이다. 

기본적으로 후입선출 (LIFO, Last-In-First-Out) 원칙을 따르는데, 가장 나중에 추가된 데이터가 가장 먼저 제거된다는 뜻이다. 

 

 

 

📌  스택의 주요 연산

1. push: 데이터를 스택의 맨 위에 추가하는 연산

2. pop: 스택의 맨 위에 있는 데이터를 제거하고 반환하는 연산

3. peek (또는 top): 스택의 맨위에 있는 데이터를 제거하지 않고 확인하는 연산

4. isEmpty: 스택이 비어있는지 확인하는 연산

 

 

📌 스택 활용 예시

1. 웹 브라우저의 뒤로가기: 브라우저에서 페이지를 탐색할 때 방문한 페이지를 스택에 저장한다. 뒤로 가기를 누르면 가장 최근에 방문한 페이지부터 순서대로 돌아갈 수 있다. 

2. 실행 취소 (Undo) 기능: 텍스트 에디터나 그래픽 소프트웨어에서 작업을 되돌리는 기능은 스택을 활용한다. 사용자가 수행한 작업이 스택에 저장되며, 되돌리기(Undo) 명령을 수행하면 가장 최근 작업을 되돌려 준다.

3. 수식의 괄호 검증: 스택은 프로그래밍 언어에서 괄호의 짝을 맞추거나 수식의 유효성을 검증하는데 활용될 수 있다. 여는 괄호가 나오면 스택에 push하고, 닫는 괄호가 나오면 스택에서 pop하여 짝을 맞추는 식으로 동작한다. 

 

---

큐(QUEUE)란?

 

큐(QUEUE)는 선입선출(FIFO, First-In-First-Out) 원칙을 따르는 데이터 구조이다. 

즉, 먼저 들어간 데이터가 먼저 나오는 구조로, 예를 들어 일상에서 줄을 서서 기다릴 때 앞사람이 먼저 나가는 것과 같다. 

정해진 한 곳(top)에서만 삽입, 삭제가 이루어지는 스택과 다르게 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서는 삭제 작업이 양쪽으로 이루어진다. 

 

 

 

📌  큐의 양 끝을 나타내는 개념

1. front

- 큐의 가장 앞쪽을 가리키는 위치

- 데이터 제거 연산이 수행되는 위치 

- 즉, 큐에서 데이터를 꺼낼 때 front에서 데이터를 가지고 오고, 그 다음 요소가 새로 front가 된다. 

 

2. rear

- 큐의 가장 뒤쪽을 가리키는 위치

- 데이터 추가 연산이 수행되는 위치

- 새로운 데이터는 항상 rear에 추가되고, rear은 다음 빈 자리로 이동하게 된다. 

 

 

 

📌  큐의 주요 연산

1. 인큐(enqueue): 데이터를 큐의 뒤(끝)에 추가하는 연산

2. 디큐(dequeue): 큐의 앞(처음)에 있는 제이터를 제거하고 반환하는 연산

3. front (또는 peek): 큐의 가장 앞에 있는 데이터를 제거하지 않고 확인하는 연산

4. isEmpty: 큐가 비어있는지 확인하는 연산 

 

 

📌  큐의 동장 과정 예시 

예를 들어 큐에 숫자 10, 20, 30을 차례대로 추가한다고 해 보자. 

 

1. 초기 상태: 빈큐

• front: null
• rear: null

 

 

2. enqueue(10): 10을 추가 

front와 rear모두 10을 가리킴 

• front: 10 
• rear: 10

 

3. enqueue(20): 20을 추가

• front: 10 
• rear: 20

 

4. enqueue(30): 30을 추가

• front: 10 
• rear: 30

 

5. 첫 번째 dequeue()

• front가 가리키는 10이 제거됨 → front: 20
•  rear: 30

 

 

6. 두 번째 dequeue()

• front가 가리키는 20이 제거됨 → front: 30
•  rear: 30

 

 

 

📌  큐의 활용 예시

1. 프린터 작업 관리: 프린터에 여러 작업이 들어올 때, 먼저 요청한 작업부터 처리한다. 즉, 큐에 작업을 추가(enqueue)하고, 프린터가 한 작업을 끝내면 다음 작업을 꺼내(dequeue) 실행한다.

2. 콜센터 시스템: 먼저 전화한 사람이 먼저 응답받는 방식이다. 즉, 고객의 전화가 들어오면 큐에 추가하고 상담원이 빈 상태가 되면 큐에서 차례로 고객을 연결한다. 

3. 멀티스레드 작업 대기열: 멀티스레드 환경에서 작업 요청을 대기열에 넣고, 스레드가 준비되면 큐에서 작업을 꺼내 실행할 수 있다.