[자료 구조] Stack과 Queue

목차

1. Stack
2. Queue
3. Stack vs Queue
4. 확장 구조

 

 

 

---

 

 

 

Stack

후입선출 (LIFO: Last In, First Out) 방식의 자료구조입니다. 즉, 가장 나중에 들어온 데이터가 가장 먼저 나가는 구조입니다.

 

1. Stack 구조

Stack 구조

• 0번부터 넣은 후, 4번을 가장 마지막에 넣은 상태입니다.
• Top : 가장 위에 있는 데이터 위
• Bottom : 가장 아래에 있는 데이터 위치
• PUSH : 데이터를 넣는 행위
• POP : 데이터를 빼는 행위

 

2. Stack 특징

• 한 쪽 끝에서만 데이터 삽입과 삭제가 일어납니다.
• 재귀 호출, 되돌리기(Undo) 기능 등에 적합합니다.

3. 사용 예시

• 웹 브라우저의 뒤로 가기(Back) 기능
• 재귀 함수의 호출 스택
• 수식 계산 (후위 표기법 등)
• 자바 JVM Stack 메모리
• DFS (깊이 우선 탐색) 알고리즘 구현

 

 

---

 

 

Queue

선입선출 (FIFO : First In, First Out) 방식의 자료구조입니다. 즉, 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조입니다.

 

1. Queue 구조

Queue 구조

• 0번부터 4번 데이터까지 순서대로 넣은 상태입니다.
• Front : 데이터를 삭제하는 위치
• Rear : 데이터를 삽입하는 위치
• ENQUEUE : 데이터를 넣는 행위
• DEQUEUE : 데이터를 빼는 행위

 

2. Queue 특징

• 데이터는 한 쪽에서 입력되고 다른 쪽에서 출력됩니다.
• 순서대로 처리해야 하는 작업에 적합합니다.

 

3. 사용 예시

• 프린터 작업 예약
• CPU 작업 스케줄링
• 네트워크 데이터 전송 처리
• BFS (너비 우선 탐색) 알고리즘 구현

 

---

 

 

Stack vs Queue

항목	Stack (스택)	Queue (큐)
처리 순서	LIFO (후입선출)	FIFO (선입선출)
삽입 위치	맨 위 (Top)	뒤쪽 (Rear / Tail)
삭제 위치	맨 위 (Top)	앞쪽 (Front / Head)
주요 메서드	push(), pop(), peek()	enqueue(), dequeue(), peek()

 

 

---

 

 

확장 구조

• Deque (Double-ended Queue) : 양쪽에서 삽입/삭제가 가능한 큐
• Priority Queue (우선순위 큐) : 우선순위에 따라 요소를 꺼냄 (Heap으로 구현)