스택(Stack) 자료구조 개요 및 동작 원리
1. 개요
- 스택(Stack)은 후입선출(LIFO: Last In, First Out) 원칙을 따르는 선형 자료구조이다. 이는 가장 나중에 삽입된 데이터가 가장 먼저 삭제되는 구조로, 접시 쌓기나 책 더미처럼 마지막에 넣은 것이 가장 먼저 꺼내지는 형태를 가진다. 스택은 데이터의 관리가 간단하며, 특히 재귀적인 문제 해결이나 후위 표기법 계산 등 다양한 알고리즘에서 중요한 역할을 한다.
스택의 사용 사례
- 함수 호출 스택: 프로그램에서 함수가 호출되면, 가장 최근에 호출된 함수가 먼저 반환되어야 하므로 함수 호출을 스택 구조로 관리한다.
- 역순 문자열 출력: 문자열을 뒤집을 때 스택을 이용하여 간단히 구현할 수 있다.
- 수식의 괄호 검사: 수식에서 괄호가 올바르게 짝지어졌는지 검사하는 데 스택이 사용된다.
스택은 주로 push(삽입)와 pop(삭제) 연산을 통해 데이터를 처리하며, top이라는 포인터로 스택의 마지막 요소를 가리킨다.
2. 스택의 동작 원리
스택은 한쪽 끝에서만 데이터의 삽입과 삭제가 이루어지는 구조로, top이라는 포인터가 스택의 가장 상단 요소를 가리킨다. 데이터를 삽입할 때는 push 연산을 통해 top이 가리키는 위치에 데이터를 추가하고, 데이터를 삭제할 때는 pop 연산을 통해 top에 위치한 데이터를 제거한다.
1. 삽입 연산 (Push)
- 삽입 연산(Push)은 스택의 top 위치에 데이터를 추가하는 연산이다. 새로운 데이터는 스택의 마지막에 추가되며, top 포인터는 새로 추가된 데이터를 가리키게 된다.
예시:
스택: [5, 10, 15] (현재 상태)
Push(20)
스택: [5, 10, 15, 20] (새로운 상태, top = 20)
이 예시에서, 20이 스택의 top에 추가되었으며, 기존 데이터는 그대로 유지된다.
2. 삭제 연산 (Pop)
- 삭제 연산(Pop)은 스택의 top 위치에 있는 데이터를 제거하는 연산이다. 가장 마지막에 삽입된 데이터가 삭제되며, top 포인터는 그 아래에 있는 데이터를 가리키게 된다.
예시:
스택: [5, 10, 15, 20] (현재 상태)
Pop()
스택: [5, 10, 15] (새로운 상태, top = 15)
이 경우, 20이 가장 나중에 삽입된 데이터이므로 top에서 삭제되었고, 그 아래에 있던 15가 새로운 top이 된다.
3. 스택이 가득 찬 상태 (Stack Overflow)
스택이 가득 찬 상태에서 추가적인 push 연산을 수행하면 스택 오버플로우(Stack Overflow)가 발생한다. 이는 스택이 허용된 메모리 범위를 초과했을 때 발생하며, 특히 배열 기반 스택에서 자주 일어난다.
4. 스택이 비어 있는 상태 (Stack Underflow)
스택이 비어 있는 상태에서 pop 연산을 수행하면 스택 언더플로우(Stack Underflow)가 발생한다. 이는 삭제할 데이터가 없을 때 발생하며, 오류가 발생한다.
3. 스택의 종류
스택은 구현 방식에 따라 여러 가지로 나뉘며, 각각의 방식은 사용 목적에 맞게 선택된다.
1. 배열 기반 스택 (Array-based Stack)
배열 기반 스택은 고정된 크기의 배열을 사용하여 데이터를 저장한다. 이 방식은 구현이 간단하지만, 배열 크기를 미리 정해두기 때문에 메모리 낭비가 발생하거나, 스택 오버플로우가 발생할 수 있다.
예시:
class Stack:
def __init__(self, size):
self.stack = [None] * size
self.top = -1
self.size = size
def is_empty(self):
return self.top == -1
def is_full(self):
return self.top == self.size - 1
def push(self, data):
if self.is_full():
print("스택이 가득 찼습니다.")
return
self.top += 1
self.stack[self.top] = data
def pop(self):
if self.is_empty():
print("스택이 비어 있습니다.")
return
data = self.stack[self.top]
self.top -= 1
return data
위 코드에서는 고정 크기의 배열을 사용하여 스택을 구현하며, push와 pop 연산을 통해 데이터를 삽입하고 삭제할 수 있다.
2. 연결 리스트 기반 스택 (Linked List-based Stack)
연결 리스트 기반 스택은 동적 메모리를 사용하여 데이터의 크기에 제한 없이 스택을 구현할 수 있다. 각 데이터는 노드(Node) 형태로 연결되며, 새로운 데이터가 추가되면 top 포인터가 새로 추가된 노드를 가리킨다. 배열 기반 스택과 달리, 메모리 낭비가 적고 유연성이 높다.
3. 순환 스택 (Circular Stack)
- 순환 스택(Circular Stack)은 스택이 원형으로 연결된 구조로, 배열의 끝에 도달하면 다시 배열의 처음으로 돌아가 데이터를 삽입할 수 있다. 이를 통해 스택의 효율적인 메모리 활용이 가능해진다. 하지만 배열 기반 순환 스택에서 크기 제한이 있다는 점은 여전히 문제로 남는다.
4. 스택의 응용
스택은 다양한 분야에서 사용되며, 주로 재귀적인 문제 해결이나 후위 표기법 계산, 수식의 괄호 짝 맞추기 등에 활용된다.
1. 함수 호출 스택
프로그램에서 함수가 호출될 때마다 함수 호출 정보를 스택에 저장하며, 함수 실행이 끝나면 스택에서 해당 정보를 꺼내어 처리한다. 이를 통해 함수가 재귀적으로 호출되더라도, 함수가 끝나는 순서대로 처리될 수 있다. 함수 호출 스택은 컴퓨터가 함수 간의 연관성을 관리하는 데 매우 중요하다.
예시:
main() 함수 호출 → f1() 함수 호출 → f2() 함수 호출
f2() 함수 종료 → f1() 함수 종료 → main() 함수 종료
이와 같이, 마지막에 호출된 함수가 먼저 종료되면서 스택의 LIFO 구조가 유지된다.
2. 수식의 괄호 검사
수식에서 괄호가 올바르게 짝지어졌는지 확인하는 데 스택이 사용된다. 여는 괄호가 나오면 스택에 push하고, 닫는 괄호가 나오면 스택에서 pop을 하여 짝이 맞는지 확인한다. 모든 괄호가 짝을 이루면 올바른 수식임을 확인할 수 있다.
예시:
수식: (a + b) * (c - d)
스택 상태: [(] → pop [(] → push [(] → pop
3. 후위 표기법 (Postfix Notation) 계산
후위 표기법에서는 연산자가 피연산자 뒤에 위치하며, 이를 계산할 때 스택을 사용한다. 피연산자를 스택에 push하고, 연산자가 나오면 스택에서 피연산자를 pop하여 연산을 수행한 후, 그 결과를 다시 스택에 push하는 방식으로 계산이 이루어진다.
예시:
수식: 3 4 + 2 * 7 /
스택 상태: [3, 4] → [7] → [7, 2] → [14] → [2]
결과: 2
5. 스택의 구현
1. 배열 기반 스택 구현 예시
class Stack:
def __init__(self, size):
self.stack = [None] * size
self.top = -1
self.size = size
def is_empty(self):
return self.top == -1
def is_full(self):
return self.top == self.size - 1
def push(self, data):
if self.is_full():
print("스택이 가득 찼습니다.")
return
self.top += 1
self.stack[self.top] = data
def pop(self):
if self.is_empty():
print("스택이 비어 있습니다.")
return
data = self.stack[self.top]
self.top -= 1
return data
def peek(self):
if self.is_empty():
print("스택이 비어 있습니다.")
return None
return self.stack[self.top]
이 코드는 배열 기반 스택을 구현한 예시로, 고정된 크기의 스택에서 데이터를 삽입(push)하고 삭제(pop)하는 연산을 지원한다. peek 연산은 스택의 top에 있는 데이터를 확인하는 연산이다.
6. 스택의 주요 연산 시간 복잡도
- 삽입(Push): O(1)
- 삭제(Pop): O(1)
- 탐색(Search): O(n) (단순 스택의 경우)
스택의 삽입과 삭제 연산은 O(1)의 시간 복잡도를 가지므로 매우 빠르게 수행된다. 하지만 스택에서 특정 데이터를 찾기 위해서는 모든 데이터를 탐색해야 하므로 탐색 시간 복잡도는 O(n)이다.
스택은 후입선출(LIFO) 방식으로 데이터를 처리하는 데 매우 유용한 자료구조이다. 함수 호출 관리, 수식 처리, 후위 표기법 계산 등에서 필수적으로 사용되며, 효율적인 메모리 관리와 간단한 구조로 다양한 응용 분야에서 중요한 역할을 한다.
'컴퓨터 과학과 > 자료 구조' 카테고리의 다른 글
| [자료 구조] 큐(Queue) (0) | 2024.09.29 |
|---|---|
| [자료구조] 배열의 정의 및 구조 (1) | 2024.09.17 |
| [자료구조] 자료구조란 무엇인가? (0) | 2024.09.17 |