스택 알아보기
데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식
스택에 데이터를 넣는 작업을 푸시(push)
스택에서 데이터를 꺼내는 작업을 팝(pop)
푸시하고 팝하는 윗부분을 꼭대기(top)
아랫부분을 바닥(bottom)
스택 구현하기
스택 배열: stk
푸시한 데이터를 저장하는 스택 본체인 list형 배열, 인덱스가 0인 원소를 스택의 바닥이라고 한다.
따라서 가장 먼저 푸시하여 데이터를 저장하는 곳은 stk[0]이다.
스택 크기: capacity
스택의 최대 크기를 나타내는 int형 정수이며, 이 값은 배열 stk의 원소 수인 len(stk)와 일치한다.
스택 포인터: ptr
스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값을 스택 포인터라고 한다.
물론 스택이 비어 있으면 ptr의 값은 0이 되고 가득 차 있으면 capacity와 같은 값이 된다.
위 그림은 크기가 8인 스택에 4개의 데이터를 푸시한 상태이다.
가장 먼저 푸시한 데이터는 stk[0]인 19이고, 가장 마지막에 푸시한 데이터는 stk[ptr - 1]인 53이다.
ptr은 가장 마지막에 푸시한 원소의 인덱스에 1을 더한 값과 일치한다. 스택에 데이터를 푸시할 때 ptr을 1씩 증가시키고, 스택에서 데이터를 팝할 때 ptr을 1씩 감소시킨다.
스택 포인터의 범위를 지정할 때 주의할 점
FixedStack 클래스를 사용하여 스택 작업을 수행하는 경우 스택 포인터 ptr 값은 반드시 0 이상이거나 capacity값 이하가 된다. 따라서 is_empty(), is_full() 함수는 <, >= 연산자가 아니라 ==를 사용해서 다음과 같이 정의할 수도 있다.
def is_empty(self) -> bool:
"""스택이 비어 있는지 판단"""
return self.ptr == 0def is_full(self) -> bool:
"""스택이 가득 차 있는지 판단"""
return self.ptr == self.capacity
하지만 프로그램 오류 등으로 ptr의 값이 0보다 작아지거나 capacity보다 커질 가능성도 있으므로 이 방법은 추천하지 않는다. 부등호(<=, >=)로 판단하면 스택 배열의 최솟값과 최댓값에서 벗어나 접근하는 것을 막을 수 있다.
이렇게 코드를 간단히 설계하는 것만으로도 프로그램을 오류 없이 잘 작동할 수 있도록 한다.
예외 처리 클래스 Empty
pop( ) 함수 또는 peek( ) 함수를 호출할 때 스택이 비어 있으면 내보내는 예외 처리이다.
예외 처리 클래스 Full
push( ) 함수를 호출할 때 스택이 가득 차 있으면 내보내는 예외 처리이다.
초기화하는 __init__( ) 함수
__init__( ) 함수는 스택 배열을 생성하는 등의 준비 작업을 수행한다. 매개변수 capacity로 전달받은 값을 스택의 크기를 나타내는 필드인 capacity로 복사하여, 원소 수가 capacity이고 모든 원소가 None인 리스트형 stk를 생성한다. 이때 스택이 비어 있으므로 스택 포인터 ptr의 값을 0으로 한다.
쌓여 있는 데이터 개수를 알아내는 __len__( ) 함수
__len__( ) 함수는 스택에 쌓여 있는 데이터 개수를 반환한다. 여기서는 스택 포인터 ptr값을 그대로 반환한다.
스택 s의 원소 수는 s.__len__( ) 또는 len(s)를 통해 알아볼 수 있다.
스택이 비어 있는지를 판단하는 is_empty( ) 함수
is_empty( ) 함수는 데이터가 하나도 쌓여 있지 않은 상태, 즉 스택이 비어 있는지 판단한다.
스택이 비어 있으면 True를, 그렇지 않으면 False를 반환한다.
스택이 가득 차 있는지를 판단하는 is_full( ) 함수
is_full( ) 함수는 더 이상 데이터를 푸시할 수 없는 상태, 즉 스택이 가득 차 있는지 판단한다.
스택이 가득 차 있으면 True를, 그렇지 않으면 False를 반환한다.
# 고정 길이 스택 클래스 FixedStack 구현하기
from typing import Any
class FixedStack:
"""고정 길이 스택 클래스"""
class Empty(Exception):
"""비어 있는 FixedStack에 팝 또는 피크할 때 내보내는 예외 처리"""
pass
class Full(Exception):
"""가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리"""
pass
def __init__(self, capacity: int = 256) -> None:
"""스택 초기화"""
self.stk = [None] * capacity # 스택 본체
self.capacity = capacity # 스택의 크기
self.ptr = 0 # 스택 포인터
def __len__(self) -> int:
"""스택에 쌓여 있는 데이터 개수를 반환"""
return self.ptr
def is_empty(self) -> bool:
"""스택이 비어 있는지 판단"""
return self.ptr <= 0
def is_full(self) -> bool:
"""스택이 가득 차 있는지 판단"""
return self.ptr >= self.capacity
데이터를 푸시하는 push( ) 함수
push( ) 함수는 스택에 데이터를 추가한다. 그러나 스택이 가득 차서 더 이상 푸시할 수 없는 경우에는 FixedStack.Full을 통하여 예외 처리를 내보낸다. 푸시 작업을 수행하는 아래 그림처럼 스택이 가득 차 있지 않으면 전달받은 value를 배열 원소 stk[ptr]에 저장하고 스택 포인터 ptr을 1 증가시킨다.
24를 stk[4]에 저장한 후 ptr을 1 증가시켜 5가 되도록 한다.
데이터를 팝하는 pop( ) 함수
pop( ) 함수는 스택의 꼭대기에서 데이터를 꺼내서 그 값을 반환한다. 그러나 스택이 비어서 팝할 수 없는 경우에는 FixedStack.Empty를 통하여 예외 처리를 내보낸다. 팝 작업을 수행하는 아래 그림처럼 스택이 비어 있지 않으면 스택 포인터 ptr의 값을 1 감소시키고 stk[ptr]에 저장된 값을 반환한다.
데이터를 들여다보는 peek( ) 함수
peek( ) 함수는 스택의 꼭대기 데이터(다음에 팝하는 데이터)를 들여다 본다. 그러나 스택이 비어 있는 경우에는 FixedStack.Empty를 통하여 예외 처리를 내보낸다. 스택이 비어 있지 않으면 꼭대기 원소 stk[ptr - 1]의 값을 반환한다.
데이터의 입출력이 없으므로 스택 포인터는 변화하지 않는다.
def push(self, value: Any) -> None:
"""스택에 value를 푸시(데이터를 넣음)"""
if self.is_full(): # 스택이 가득 차 있는 경우
raise FixedStack.Full # 예외 처리 발생
self.stk[self.ptr] = value
self.ptr += 1
def pop(self) -> Any:
"""스택에서 데이터를 팝(꼭대기 데이터를 꺼냄)"""
if self.is_empty(): # 스택이 비어 있는 경우
raise FixedStack.Empty # 예외 처리 발생
self.ptr -= 1
return self.stk[self.ptr]
def peek(self) -> Any:
"""스택에서 데이터를 피크(꼭대기 데이터를 들여다봄)"""
if self.is_empty(): # 스택이 비어 있음
raise FixedStack.Empty # 예외 처리 발생
return self.stk[self.ptr - 1]
def clear(self) -> None:
"""스택을 비움(모든 데이터를 삭제)"""
self.ptr = 0
스택의 모든 데이터를 삭제하는 clear( ) 함수
clear( ) 함수는 스택에 쌓여 있는 데이터를 모두 삭제하여 빈 스택을 만든다. 스택 포인터 ptr의 값을 0으로 하면 끝난다.
스택에서 푸시나 팝 등 모든 작업은 스택 포인터 ptr을 바탕으로 이루어진다. 따라서 스택의 배열 원솟값을 변경할 필요가 없다.
데이터를 검색하는 find( ) 함수
find( ) 함수는 스택 본체의 배열 stk 안에 value와 값이 같은 데이터가 포함되어 있는지 확인하고, 포함되어 있다면 배열의 어디에 들어 있는지를 검색한다.
아래 그림은 find( ) 함수가 스택에서 검색하는 예를 보여준다.
이 그림을 보면 알 수 있듯이 검색은 꼭대기 쪽에서 바닥 쪽으로 선형 검색을 한다. 즉, 배열의 인덱스가 큰 쪽에서 작은 쪽으로 스캔한다. 검색에 성공하면 발견한 원소의 인덱스를 반환하고 실패하면 -1을 반환한다.
위 그림의 스택에는 인덱스 1과 4 두 곳에 25가 있다. 이 스택에서 25를 검색하는 경우 꼭대기 쪽에 있는 25의 인덱스 4를 반환한다. 꼭대기 쪽부터 스캔하는 것은 먼저 팝할 데이터를 찾아가기 위해서이다.
데이터 개수를 세는 count( ) 함수
count( ) 함수는 스택에 쌓여 있는 데이터(value)의 개수를 구하여 반환한다.
데이터가 포함되어 있는지 판단하는 __contains__( ) 함수
__contains__( ) 함수는 스택에 데이터(value)가 있는지 판단한다. 있으면 True를 반환하고 그렇지 않으면 False를 반환한다. 예를 들어 스택 s에 데이터 x가 포함되어 있는지 판단은 s.__contains__(x)뿐만 아니라 멤버십 판단 연산자인 in을 사용하여 x in s로 수행할 수 있다.
def find(self, value: Any) -> Any:
"""스택에서 value를 찾아 인덱스를 반환(없으면 -1을 반환)"""
for i in range(self.ptr - 1, -1, -1): # 꼭대기 쪽부터 선형 검색
if self.stk[i] == value:
return i # 검색 성공
return -1 # 검색 실패
def count(self, value: Any) -> int:
"""스택에 있는 value의 개수를 반환"""
c = 0
for i in range(self.ptr): # 바닥 쪽부터 선형 검색
if self.stk[i] == value # 검색 성공
c += 1
return c
def __contains__(self, value: Any) -> bool:
"""스택에 value가 있는지 판단"""
return self.count(value) > 0
def dump(self) -> None:
"""덤프(스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력)"""
if self.is_empty(): # 스택이 비어 있음
print('스택이 비어 있습니다.')
else:
print(self.stk[:self.ptr])
스택의 모든 데이터를 출력하는 dump( ) 함수
dump( ) 함수는 스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 꼭대기까지 순서대로 출력한다.
스택이 비어 있으면 '스택이 비어 있습니다.'를 출력한다.
| __len__( ) 함수와 __contains__( ) 함수 알아보기 파이썬에서 시작과 끝에 언더스코어(_)가 2개 붙은 함수는 특별한 의미가 있다. __len__( ) 함수 클래스에 __len__( ) 함수를 정의하면 클래스형의 인스턴스를 len( ) 함수에 전달할 수 있다. 예를 들어 클래스형의 인스턴스 obj에 대한 __len__( ) 함수를 호출하는 obj.__len__( )를 간단히 len(obj)로 작성할 수 있다. __contains__( ) 함수 클래스에 __contains__( ) 함수를 정의하면 클래스형의 인스턴스에 멤버십 판단 연산자인 in을 적용할 수 있다. 예를 들어 클래스형의 인스턴스 obj에 대한 __contains__( ) 함수를 호출하는 obj.__contains__(x)를 간단히 x in obj로 작성할 수 있다. |
고정 길이 스택 FixedStack 클래스를 사용하는 프로그램(fixed_stack_test.py)
# 고정 길이 스택 클래스(FixedStack)를 사용하기
from enum import Enum
from fixed_stack import FixedStack
Menu = Enum('Menu', ['푸시', '팝', '피크', '검색', '덤프', '종료'])
def select_menu() -> Menu:
"""메뉴 선택"""
s = [f'({m.value}){m.name}' for m in Menu]
while True:
print(*s, sep = ' ', end='')
n = int(input(': '))
if 1 <= n <= len(Menu):
return Menu(n)
s = FixedStack(64) # 최대 64개를 푸시할 수 있는 스택
while True:
print(f'현재 데이터 개수: {len(s)} / {s.capacity}')
menu = select_menu() # 메뉴 선택
if menu == Menu.푸시: # 푸시
x = int(input('데이터를 입력하세요.: '))
try:
s.push(x)
except FixedStack.Full:
print('스택이 가득 차 있습니다.')
elif menu == Menu.팝: # 팝
try:
x = s.pop()
print(f'팝한 데이터는 {x}입니다.')
except FixedStack.Empty:
print('스택이 비어 있습니다.')
elif menu == Menu.피크: # 피크
try:
x = s.peek()
print(f'피크한 데이터는 {X}입니다.')
except FixedStack.Empty:
print('스택이 비어 있습니다.')
elif menu == Menu.검색: # 검색
x = int(input('검색할 값을 입력하세요.: '))
if x in s:
print(f'{s.count(x)}개 포함되고, 맨 앞의 위치는 {s.find(x)}입니다.')
else:
print('검색값을 찾을 수 없습니다.')
elif menu == Menu.덤프: # 덤프
s.dump()
else:
break
실행 결과
현재 데이터 개수: 0 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 1
데이터를 입력하세요.: 1
현재 데이터 개수: 1 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 1
데이터를 입력하세요.: 2
현재 데이터 개수: 2 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 1
데이터를 입력하세요.: 3
현재 데이터 개수: 3 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 1
데이터를 입력하세요.: 1
현재 데이터 개수: 4 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 1
데이터를 입력하세요.: 5
현재 데이터 개수: 5 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 4
검색할 값을 입력하세요.: 1
2개 포함되고, 맨 앞의 위치는 3입니다.
현재 데이터 개수: 5 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 3
피크한 데이터는 5입니다.
현재 데이터 개수: 5 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 2
팝한 데이터는 5입니다.
현재 데이터 개수: 4 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 2
팝한 데이터는 1입니다.
현재 데이터 개수: 3 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 5
[1, 2, 3]
현재 데이터 개수: 3 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 6
Process finished with exit code 0
collections.deque로 스택 구현하기
파이썬의 내장 컨테이너는 딕셔너리, 리스트, 집합, 튜플이 있다. 이 외에도 여러 컨테이너를 collections 모듈로 제공한다.
주요 컨테이너는 namedtuble( ), deque.ChainMap, Counter, OrderedDict, defaultdict, UserDict, UserList, UserString 같은 컬렉션이다. 이 가운데 deque 모듈을 사용하면 스택을 간단하게 구현할 수 있다.
collection.deque는 맨 앞과 맨 끝 양쪽에서 원소를 추가·삭제하는 자료구조인 덱(deque)을 구현하는 컨테이너이다.
deque의 주요 속성과 함수는 다음과 같다.
| 속성과 함수 | 설명 |
| maxlen 속성 | deque의 최대 크기를 나타내는 속성으로 읽기 전용이다. 크기 제한이 없으면 None이다. |
| append(x) 함수 | deque의 맨 끝(오른쪽)에 x를 추가한다. |
| appendleft(x) 함수 | deque의 맨 앞(왼쪽)에 x를 추가한다. |
| clear( ) 함수 | deque의 모든 원소를 삭제하고 크기를 0으로 한다. |
| copy( ) 함수 | deque의 얕은 복사(shallow copy)를 한다. |
| count(x) 함수 | deque 안에 있는 x와 같은 원소의 개수를 계산한다. |
| extend(iterable) 함수 | 순차 반복 인수 iterable에서 가져온 원소를 deque의 맨 끝(오른쪽)에 추가하여 확장한다. |
| extendleft(iterable) 함수 | 순차 반복 인수 iterable에서 가져온 원소를 deque의 맨 앞(왼쪽)에 추가하여 확장한다. |
| index(x[, start [, stop]]) 함수 | deque 안에 있는(인덱스 start부터 인덱스 stop까지 양 끝을 포함한 범위) x 가운데 가장 앞쪽에 있는 원소의 위치를 반환한다. x가 없는 경우는 ValueError를 내보낸다. |
| insert(i, x) 함수 | x를 deque의 i 위치에 삽입한다. 이때 크기에 제한이 있는 deque일 경우 maxlen을 초과한 삽입은 IndexError를 내보낸다. |
| pop( ) 함수 | deque의 맨 끝(오른쪽)에 있는 원소를 1개 삭제하고 그 원소를 반환한다. 원소가 하나도 없는 경우에는 IndexError를 내보낸다. |
| popleft( ) 함수 | deque의 맨 앞(왼쪽)에 있는 원소를 1개 삭제하고 그 원소를 반환한다. 원소가 하나도 없는 경우에는 IndexError를 내보낸다. |
| remove(value) 함수 | value의 첫 번째 항목을 삭제한다. 원소가 없는 경우에는 ValueError를 내보낸다. |
| reverse( ) 함수 | deque 원소를 역순으로 재정렬하고 None을 반환한다. |
| rotate(n = 1) 함수 | deque의 모든 원소를 n값만큼 오른쪽으로 밀어낸다. n이 음수라면 왼쪽으로 밀어낸다. |
이 외에도 이터레이션과 pickle, len(d), reversed(d), copy.copy(d), copy.deepcopy(d), in 연산자로 멤버십 판단, d[0] 등의 형식에서 인덱스에 의한 참조를 지원한다.
양쪽 끝의 데이터를 인덱스로 접근하는 것은 O(1)로 빠르지만, 가운데 부분에 있는 데이터를 접근하는 것은 O(n)으로 느리다. 그러므로 인덱스를 사용하여 임의의 원소를 무작위로 접근하는 것은 효율적이지 않다.
collections.deque를 사용하여 고정 길이 스택 클래스를 구현한 코드
# 고정 길이 스택 클래스 구현하기(collections.deque를 사용)
from typing import Any
from collections import deque
class Stack:
"""고정 길이 스택 클래스(collections.deque를 사용)"""
def __init__(self, maxlen: int = 256) -> None:
"""스택 초기화"""
self.capacity = maxlen
self.__stk = deque([], maxlen)
def __len__(self) -> int:
"""스택에 쌓여 있는 데이터 개수를 반환"""
return len(self.__stk)
def is_empty(self) -> bool:
"""스택이 비어 있는지 판단"""
return not self.__stk
def is_full(self) -> bool:
"""스택이 가득 차 있는지 판단"""
return len(self.__stk) == self.__stk.maxlen
def push(self, value: Any) -> None:
"""스택에 value를 푸시"""
self.__stk.append(value)
def pop(self) -> Any:
"""스택에서 데이터를 팝"""
return self.__stk.pop()
def peek(self) -> Any:
"""스택에서 데이터를 피크"""
return self.__stk[-1]
def clear(self) -> None:
"""스택을 비움"""
self.__stk.clear()
def find(self, value: Any) -> Any:
"""스택에서 value를 찾아 인덱스를 반환(찾지 못하면 -1을 반환)"""
try:
return self.__stk.index(value)
except ValueError:
return -1
def count(self, value: Any) -> int:
"""스택에 포함되어 있는 value의 개수를 반환"""
return self.__stk.count(value)
def __contains__(self, value: Any) -> bool:
"""스택에 value가 포함되어 있는지 판단"""
def dump(self) -> int:
"""스택 안에 있는 모든 데이터를 나열(바닥에서 꼭대기 순으로 출력)"""
print(list(self.__stk))