Chapter 01. 스택
01-1 스택이란?
스택
마지막에 들어간 자료가 가장 먼저 나오는 자료구조
후입선출 LIFO(Last-In First-Out)
스택은 물건을 넣는 좁고 긴 통으로 생각할 수 있는데, 다른 통로는 막고 한쪽만을 열어둔 구조로
열린 곳을 보통 상단(stack top) 이라 부르고, 스택에 저장되는 것을 요소(element) 라 부름
스택은 요소의 삽입과 삭제가 상단에서만 가능
추상 자료형
추상화(abstraction)
: 새로운 자료형을 정의하기 위해 그 자료형의 자세하고 복잡한 내용 대신에 필수적이고 중요한 특징만 골라서 단순화시키는 작업
추상 자료형(ADT: Abstract Data Type)
: 추상화를 통해 정의한 자료형
스택의 연산
- push(e): 새로운 요소 e를 스택의 맨 위에 추가 (삽입)
- pop(): 스택의 맨 위에 있는 요소를 꺼내서 반환 (삭제)
- isEmpty(): 스택이 비어 있으면 True를, 아니면 False를 반환
- isFull(): 스택이 가득 차 있으면 True를, 아니면 False를 반환
- peek(): 스택의 맨 위에 있는 항목을 삭제하지 않고 반환
- size(): 스택에 들어 있는 전체 요소의 수를 반환
스택이 peek 연산을 지원하지 않는다면 pop으로 꺼내서 확인 후 push로 다시 넣으면 원래 상태가 유지됨
스택 오버플로(overflow)
: 포화 상태인 스택에 새로운 요소를 삽입하는 경우 → 오류 발생
언더플로(underflow)
: 공백 상태인 스택에서 pop()이나 peek() 호출하는 경우
01-2 배열 구조로 스택 구현하기
자료구조의 구현 방법들
자료 구조를 구현하는 방법은 각각의 자료들을 메모리에 어떤 방식으로 저장하는 가에 따라
크게 배열 구조와 연결된 구조로 나눌 수 있음
- 배열 구조: 자료들을 배열에 모아 저장하는 방법
모든 요소는 인접한 메모리 공간에 저장됨
각 요소들을 쉽게 찾아 편리하게 사용할 수 있으나, 크기가 고정되어있기에 가득 차면 더는 저장할 수 없음 - 연결된 구조: 인접한 메모리 공간이 아니라 흩어져 있는 요소들을 연결하여 하나로 관리하는 방법
위치를 바꾸거나 새로운 페이지를 쉽게 추가하고 삭제할 수 있어 배열 구조보다 유연하게 사용할 수 있으나, 관리하기 복잡함
배열 구조의 스택을 위한 데이터
- array[ ]: 스택 요소들을 저장할 배열
- capacity: 스택의 최대 용량. 저장할 수 있는 요소의 최대 개수(상수)
- top: 상단 요소의 위치(변수, 인덱스)
capacity = 10 # 스택 용량: 예) 용량을 10으로 지정
array = [None]*capacity # 요소 배열: [None, ..., None] (길이가 capacity)
top = -1 # 상단의 인덱스: 공백 상태(-1)로 초기화
스택의 연산
공백 상태와 포화 상태를 검사하는 isEmpty(), isFull() 연산
def isEmpty() :
if top == -1 : return True # 공백이면 True 반환
else : return False # 아니면 False 반환
def isFull() : return top == capacity # 비교 연산 결과를 바로 반환
새로운 요소 e를 삽입하는 push(e) 연산
def push(e):
# global top
if not isFull(): # 포화 상태가 아닌 경우
top += 1 # top 증가(global top 선언 필요)
array[top] = e # top 위치에 e 복사
else: # 포화 상태: overflow
print("stack overflow")
exit()
상단 요소를 삭제하는 pop() 연산
def pop():
# global top
if not isEmpty(): # 공백 상태가 아닌 경우
top -= 1 # top 감소(global top 선언 필요)
return array[top+1] # 이전 (top+1) 위치의 요소 반환
else: # 공백 상태: underflow
print("stack underflow")
exit()
상단 요소를 들여다보는 peek() 연산
def peek():
if not isEmpty(): # 공백 상태가 아닌 경우
return array[top]
else: pass # underflow 예외는 처리하지 않았음
현재 스택 요소의 수를 반환하는 size() 연산
def size(): return top+1 # 현재 요소의 수는 top+1
전역 변수와 함수 구현 방법의 문제
- top을 전역 변수로 인식하지 못할 경우 오류 발생 → top을 전역변수로 선언하는 global top 문장을 각 함수에 추가
- 위 코드들을 여러 개의 스택이 동시에 필요한 문제에 사용할 수 없음
전역 변수로 선언된 배열이 하나이므로 위 코드는 하나의 스택이 필요한 경우에만 사용 가능
스택을 클래스로 구현
자료구조는 함수를 기반으로 하는 절차적 프로그래밍보다 클래스를 기반으로 하는 객체 지향 프로그래밍 기법을 이용해 구현하는 것이 좋음
클래스의 선언과 멤버변수 초기화
클래스 이름이 정해지면 스택 클래스 선언, 전역 변수들을 모두 클래스의 멤버변수로 옮김
파이썬에서 클래스의 멤버변수들은 생성자라는 특별한 이름으로 불리는 __init__() 함수에서 선언
class ArrayStack:
def __init__(self, capacity):
self.capacity = capacity # 스택 용량
self.array = [None]*self.capacity # 요소 배열
self.top = -1 # 상단의 인덱스생성자: 클래스의 객체가 만들어질 때마다 자동으로 호출되는 함수
s1 = ArrayStack(20) # 용량이 20인 ArrayStack 객체 s1 생성
s2 = ArrayStack(100) # 용량이 100인 ArrayStack 객체 s2 생성파이썬에서는 생성자를 포함한 클래스의 모든 멤버함수의 첫 번째 매개변수로 스택 객체 자신을 나타내는 'self'를 넣음
클래스의 연산
def isEmpty(self): return self.top == -1
def isFull(self): return self.top == self.capacity-1
def push(self, item):
if not self.isFull():
self.top += 1
self.array[self.top] = item
else: pass
def pop(self):
if not self.isEmpty():
self.top -= 1
return self.array[self.top+1]
else: pass
def peek(self):
if not self.isEmpty():
return self.array[self.top]
else: pass
def size(self): return self.top+101-3 스택의 응용: 괄호 검사
괄호 검사 문제: 소스코드나 주어진 문자열에서 괄호들이 올바르게 사용되었는지를 검사하는 문제
괄호 사용 조건
- 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 함
- 같은 종류인 경우 왼쪽 괄호가 오른쪽보다 먼저 나와야 함
- 다른 종류의 괄호 쌍이 서로 교차하면 안 됨
괄호 검사 알고리즘
쌍을 이룬 괄호들은 더 이상 고려할 필요X
검사 과정
- 빈 스택 준비
- 입력된 문자를 하나씩 읽어 왼쪽 괄호를 만나면 스택에 삽입
- 오른쪽 괄호를 만나면 가장 최근에 삽입된 괄호를 스택에서 꺼냄
스택이 비었다면 오른쪽 괄호가 먼저 나온 상황이므로 조건 2 위배 - 꺼낸 괄호가 오른쪽 괄호와 짝이 맞지 않으면 조건 3 위배
- 입력 문자열을 끝까지 처리했는데 스택에 괄호가 남아 있으면 괄호의 개수가 같지 않아 조건 1 위배
모든 문자를 처리하고 스택이 공백 상태이면 검사 성공
괄호 검사 프로그램
def CheckBrackets(statement):
stack = ArrayStack(100)
for ch in statement:
if ch in ('{','[', '('):
stack.push(ch)
elif ch in ('}', ']',')'):
if stack.isEmpty():
return False
else:
left = stack.pop()
if (ch == '}' and left != "{") or \
(ch == ']' and left != "[") or \
(ch== ')' and left != "(") :
return False
return stack.isEmpty()01-4 파이썬에서 스택 사용하기
파이썬 리스트를 스택으로 사용하기
리스트의 앞쪽이나 뒤쪽을 스택의 상단으로 생각하고, 그쪽으로만 자료를 넣거나 뺌
(리스트의 뒤쪽을 스택의 상단으로 사용하는 것이 더 효율적)
| 연산 | ArrayStack | 파이썬 list | 사용 예 |
| 삽입 | push() | 메서드 append() 사용 | L.append(e) |
| 삭제 | pop() | 메서드 pop() 사용 | L.pop() |
| 요소의 수 | size() | 내장 함수 len()을 사용 | len(L) |
| 공백 상태 검사 | isEmpty() | 요소의 수가 0인지 검사 | len(L)==0 |
| 포화 상태 검사 | isFull() | list는 용량이 무한대라 포화상태는 의미가 없음. 항상 False | False |
| 상단 들여다보기 | peek() | 맨 마지막 요소 참조 | L[len(L)-1] 또는 L[-1] |
s = list()
msg = input("문자열 입력: ")
for c in msg:
s.append(c)
print("문자열 출력: ", end='')
while len(s) > 0:
print(s.pop(), end='')
print()
queue 모듈의 LifoQueue 사용하기
queue 모듈에서 큐(Queue)나 스택(LifoQueue), 우선순위 큐(PriorityQueue) 등을 클래스로 제공해줌
| 연산 | ArrayStack | queue.LifoQueue |
| 삽입/삭제 | push(), pop() | put(), get() |
| 공백/포화 상태 검사 | isEmpty(), isFull() | empty(), full() |
| 상단 들여다보기 | peek() | 제공하지 않음 |
maxsize가 0이면 스택의 용량이 무한대라는 의미
import queue
s = queue.LifoQueue(maxsize=100)
msg = input("문자열 입력: ")
for c in msg:
s.put(c)
print("문자열 출력: ", end='')
while not s.empty():
print(s.get(), end='')
print()01-5 시스템 스택과 순환 호출
운영체제가 관리하는 메모리에는 함수의 호출과 반환을 위해 사용되는 스택 영역이 존재
어떤 함수가 호출되면 그 함수가 끝나고 돌아갈 복귀 주소를 스택에 저장, 호출된 함수를 위한 매개변수와 지역변수들을 스택에서 할당
함수의 호출과 반환을 위해 시스템 스택 이 사용됨
순환 → 시스템 스택을 적극적으로 사용하는 프로그래밍 기법
순환이란?
순환(recursion): 함수가 자기 자신을 다시 호출하여 문제를 해결하는 프로그래밍 기법
문제 자체가 순환적이거나 순환적으로 정의되는 자료구조를 다루는 프로그램에 적합
팩토리얼의 두 가지 구현
반복 구조의 팩토리얼 함수
def factorial_iter(n) :
rsult = 1
for k in range(2, n+1) :
result = result * k
return resultfor문을 이용하여 1부터 n까지 반복해서 곱함
순환 구조의 팩토리얼 함수
def factorial(n) :
if n==1 :
return 1
else :
return n * factorial(n-1)순환적으로 호출하는 부분은 호출할수록 문제의 크기가 반드시 작아져야 함
순환 호출을 멈추는 부분이 반드시 있어야 함
순환함수는 대부분 반복 구조로도 구현 가능
n!을 구하기 위해 곱셈이 처리되는 횟수
- 반복 구조에서는 for 루프가 n-1번 반복되기때문에 곱셈이 n-1번 처리됨
- 순환 구조에서는 n이 1인 경우는 곱셈을 사용하지 않고 바로 결과를 반환 → 곱셈이 n-1번 처리됨
곱셈 연산의 횟수는 차이X
순환은 함수 호출에 의한 부담이 있고, 시스템 스택을 많이 사용하기 때문에 대부분은 반복보다 느림
그러나, 순환은 트리와 같은 특정한 문제에 대해 반복보다 훨씬 명확하고 간결한 코딩 가능
하노이의 탑
이동해야 하는 원판의 수가 많으면 더 많은 시간이 걸리므로, 원판의 수가 문제의 크기
n개의 원판을 A → C 옮기려 함
단계 1. 시작 막대(A)에 있는 n-1개의 원판을 목표 막대(C)를 임시 막대로 이용해서 임시 막대(B)로 이동
단계 2. 시작 막대(A)에 남은 하나의 원판을 목표 막대(C)로 이동
단계 3. 임시 막대(B)에 있는 n-1개의 원판을 시작 막대(A)를 임시 막대로 이용해서 목표 막대(C)로 이동
def hanoi_tower(n, fr, tmp, to) :
if (n==1):
print("원판 1: %s --> %s" % (fr, to))
else:
hanoi_tower(n-1, fr, to, tmp) # 단계 1
print("원판 %d: %s --> %s" % (n, fr, to)) # 단계 2
hanoi_tower(n-1, tmp, fr, to) # 단계 3