728x90
04-1 스택이란?
스택 알아보기
- 스택(stack): 데이터를 임시 저장할 때 사용하는 자료구조
- 스택에 데이터를 넣는 작업을 푸시(push)라 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 합니다.
- 푸시하고 팝하는 윗부분을 꼭대기(top)이라 하고, 아랫부분을 바닥(bottom)이라고 합니다.
스택 구현하기
- 스택 배열: stk
푸시한 데이터를 저장하는 스택 본체인 list형 배열입니다. 가장 먼저 푸시하여 데이터를 저장하는 곳은 stk[0]입니다. - 스택 크기: capacity
스택의 최대 크기를 나타내는 int형 정수입니다. 이 값은 배열 skt의 원소 수인 len(stk)와 일치합니다. - 스택 포인터: ptr
스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값을 스택 포인터(stack pointer)라고 합니다. 스택이 비어 있으면 ptr의 값은 0이 되고 가득 차 있으면 capacitiy와 같은 값이 됩니다.
실습 4-1 고정 길이 스택 클래스 FixedStack 구현하기
# 고정 길이 스택 클래스 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- 예외 처리 클래스 Empty
: pop() 함수 또는 peek() 함수를 호출할 때 스택이 비어 있으면 내보내는 예외 처리입니다. - 예외처리 클래스 Full
: push() 함수를 호출할 때 스택이 가득 차 있으면 내보내는 예외 처리입니다. - 초기화하는 __init__() 함수
: __init__() 함수는 스택 배열을 생성하는 등의 준비 작업을 수행합니다. 매개변수 capacity로 전달받은 값을 스택의 크기를 나타내는 필드인 capacity로 복사하여, 원소 수가 capacity이고 모든 원소가 None인 리스트형 stk를 생성합니다. 이때 스택이 비어 있으므로 스택 포인터 ptr의 값을 0으로 합니다. - 쌓여 있는 데이터 개수를 알아내는 __len__() 함수
: __len__() 함수는 스택에 쌓여 있는 데이터 개수를 반환합니다. 여기서는 스택 포인터 ptr 값을 그대로 반환합니다. - 스택이 비어 있는지를 판단하는 is_empty() 함수
: is empty() 함수는 데이터가 하나도 쌓여 있지 않은 상태, 즉 스택이 비어 있는지 판단합니다. 스택이 비어 있으면 True를, 그렇지 않으면 False를 반환합니다. - 스택이 가득 차 있는지를 판단하는 is_full() 함수
: is_full() 함수는 더 이상 데이터를 푸시할 수 없는 상태, 즉 스택이 가득 차 있는지 판단합니다. 스택이 가득 차 있으면 True를, 그렇지 않으면 False를 반환합니다.
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- 데이터를 푸시하는 push() 함수
: push() 함수는 스택에 데이터를 추가합니다. 그러나 스택이 가득 차서 더 이상 푸시할 수 없는 경우에는 FixedStack.Full을 통하여 예외처리를 내보냅니다. 스택이 가득 차 있지 않으면 전달받은 value를 배열 원소stk[ptr]에 저장하고 스택 포인터 ptr을 1 증가시킵니다. - 데이터를 팝하는 pop() 함수
: pop() 함수는 스택의 꼭대기에서 데이터를 꺼내서 그 값을 반환합니다. 그러나 스택이 비어서 팝할 수 없는 경우에는 FixedStack.Empty를 통하여 예외 처리를 내보냅니다. 스택이 비어 있지 않으면 스택 포인터 ptr의 값을 1 감소시키고 stk[ptr]에 저장된 값을 반환합니다. - 데이터를 들여다보는 peek() 함수
: peek() 함수는 스택의 꼭대기 데이터(다음에 팝하는 데이터)를 들여다봅니다. 그러나 스택이 비어 있는 경우에는 FixedStack.Empty를 통하여 예외 처리를 내보냅니다. 스택이 비어 있지 않으면 꼭대기 원소 stk[ptr-1]의 값을 반환합니다. 데이터의 입출력이 없으므로 스택 포인터는 변화하지 않습니다. - 스택의 모든 데이터를 삭제하는 clear() 함수
: clear() 함수는 스택에 쌓여 있는 데이터를 모두 삭제하여 빈 스택을 만듭니다. 스택 포인터 ptr의 값을 0으로 하면 끝납니다.
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])- 데이터를 검색하는 find() 함수
: find() 함수는 스택 본체의 배열 stk 안에 value와 값이 같은 데이터가 포함되어 있는지 확인하고, 포함되어 있다면 배열의 어디에 들어 있는지를 검색합니다. 검색은 꼭대기 쪽에서 바닥 쪽으로 선형 검색을 합니다. 즉, 배열의 인덱스가 큰 쪽에서 작은 쪽으로 스캔합니다. 검색에 성공하면 발견한 원소의 인덱스를 반환하고 실패하면 -1을 반환합니다. - 데이터 개수를 세는 count() 함수
: count() 함수는 스택에 쌓여 있는 데이터(value)의 개수를 구하여 반환합니다. - 데이터가 포함되어 있는지 판단하는 __contains__() 함수
: __contains__() 함수는 스택에 데이터(value)가 있는지 판단합니다. 있으면 True를 반환하고 그렇지 않으면 False를 반환합니다. 예를 들어 스택 s에 데이터 x가 포함되어 있는지 판단은 s.__contains__(x)뿐만 아니라 멤버십 판단 연산자(membership test operator)인 in을 사용하여 x in s로 수행할 수 있습니다. - 스택의 모든 데이터를 출력하는 dump() 함수
: dump() 함수는 스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 꼭대기까지 순서대로 출력합니다. 스택이 비어 있으면 '스택이 비어 있습니다.'를 출력합니다.
스택 프로그램 만들기
# 고정 길이 스택 클래스(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)종료: 5
[1, 2, 3, 1, 5]
현재 데이터 개수: 5 / 64
(1)푸시 (2)팝 (3)피크 (4)검색 (5)덤프 (6)종료: 3
: 5
[1, 2, 3, 1, 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)종료: 6collections.deque로 스택 구현하기
파이썬의 내장 컨테이너는 딕셔너리(dictionary), 리스트(list), 집합(set), 튜플(tuple)이 있습니다. 이 외에도 여러 컨테이너를 collections 모듈로 제공합니다. 중요 컨테이너는 namedtupe(), 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가 없는 경우는 Value Error를 내보냅니다. |
| insert(i, x) 함수 | x를 deque의 i 위치에 삽입합니다. 이때 크기에 제한이 있는 deque일 경우 maxlen을 초과한 삽입은 IndexError를 내보냅니다. |
| pop() 함수 | deque의 맨 끝(오른쪽)에 있는 원소를 1개 삭제하고 그 원소를 반환합니다. 원소가 하나도 없는 경우에는 IndexError를 내보냅니다. |
| popleft() 함수 | deque의 맨 앞(왼쪽)에 있는 원소를 1개 삭제하고 그 원소를 반환합니다. 원소가 하나도 없는 경우에는 IndexError를 내보냅니다. |
| remove(value) 함수 | value의 첫 번째 항목을 삭제합니다. 원소가 없는 경우에는 ValueError를 내보냅니다. |
| reverse() 함수 | deque 원소를 역순으로 재정렬하고 None을 반환합니다. |
| rotatte(n = 1) 함수 | deque의 모든 원소를 n값만큼 오른쪽으로 밀어냅니다. n이 음수라면 왼쪽으로 밀어냅니다. |
실습 4C-1 고정 길이 스택 클래스 구현하기(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[-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가 포함되어 있는지 판단"""
return self.count(value)
def dump(self) -> int:
"""스택 안에 있는 모든 데이터를 나열(바닥에서 꼭대기 순으로 출력)"""
print(list(self.__stk))
- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file: https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EC%8A%A4%ED%83%9D%EA%B3%BC%20%ED%81%90.ipynb
GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습
파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습. Contribute to heejvely/Algorithm development by creating an account on GitHub.
github.com
728x90
'Code > Algorithm' 카테고리의 다른 글
| [Algorithm] 재귀 알고리즘_1 (2) | 2022.12.06 |
|---|---|
| [Algorithm] 스택과 큐_2 (0) | 2022.12.05 |
| [Algorithm] 검색 알고리즘_4 (해시법) (0) | 2022.11.28 |
| [Algorithm] 검색 알고리즘_3 (이진 검색) (2) | 2022.11.28 |
| [Algorithm] 검색 알고리즘_2 (선형 검색) (0) | 2022.11.27 |