스택(Stack)은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO)방식이다.
스택에 데이터를 넣는 작업을 푸시(push)라고하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다. 겹쳐 쌓은 접시처럼 데이터를 넣고 꺼내는 작업을 맨 위부터 수행한다. 이렇게 푸시하고 팝하는 윗부분을 꼭대기(Top)이라고 하고 아랫부분을 바닥(Botton)이라고 한다.
스택 구현하기
스택을 구현하는 프로그램을 만들겠다. 스택의 기본 개념을 이해하기 위해 스택을 생성할 때 크기가 결정된 고정 길이 스택을 만들어보겠다.
- 스택 배열: stk
푸시한 데이터를 저장하는 스택 본체인 list형 배열이다. 인덱스가 0인 원소를 스택의 바닥이라고 하며 가장 먼저 푸시하여 저장하는 곳은 stk[0]이 된다.
- 스택크기: capacity
스택의 최대 크기를 나타내는 int형 정수로 이 값은 배열 stk의 원소 수인 len(stk)와 일치한다. (이때 스택 크기만큼 스택 포인터가 쌓이지 않은 경우 스택 크기와 스택 포인터는 다를 수 있다. )
- 스택 포인터: ptr
스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값을 스택 포인터(stack pointer)라고 한다. 물론 스택이 비어있다면 ptr의 값은 0이 되고 가득 차 있으면 capacity와 같은 값이 된다.
스택 포인터의 범위를 지정할 때 주의할 점 fixedstack 클래스를 사용하여 스택작업을 수행하는 경우 스택 포인터 ptr값은 반드시 0이상이거나 capacity값 이하가 된다. 따라서 is_empty( ), is_full( ) 함수는 <,>=연산자가 아니라 ==를 사용해서 다음과 같이 정의할 수도 있다.
def 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값을 그대로 반환한다.
📌(스택에 쌓여 있는 데이터 개수 = 스택 포인터 ptr 값)
- 스택이 비어 있는지를 판단하는 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 #스택 포인터 0으로 초기화
def __len__(self) -> int:
#스택에 쌓여 있는 데이터 개수를 반환
return self.prt
def is_empty(self) ->int:
#스택이 비어 있는지를 판단 이때 스택이 비어 있다면 True를 그렇지 않다면 False를 반환한다.
return self.ptr <= 0
def is_full(self) -> bool:
#스택이 가득 차 있는지 판단 이때 스택이 가득 차 있다면 True 그렇지 않다면 False를 반환
return self.prt >= self.capacity
예외 처리의 기본 구조
파이썬에서는 프로그램을 실행하다가 오류가 발생하면 예외 처리 메세지를 내보낼 수 있다. 예외 처리를 수행하면 오류를 복구하여 프로그램이 실행되다가 중단되는 것을 피할 수 있다. 또한 예외처리는 원래 처리하는 코드와 오류가 발생할 때 대처하는 코드를 분리할 수 있다는 장점이 있다.
try 문 - 원래 처리
except 문 - 예외 포착과 처리
else 문 - 예외가 포착되지 않음
finally 문 - 마무리
- 데이터를 푸시하는 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으로 하면 끝난다.
📌스택에서 푸시나 팝 등 모든 작업은 스택 포인터 ptr을 바탕으로 이루어진다. 따라서 스택의 배열 원솟값을 변경할 필요가 없다.
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
raise 문을 통한 예외 처리
파이썬은 raise문 (raise statement)으로 프로그램의 예외 처리를 의도적으로 내보낼 수 있다. valueError클래스, zeroDivisionError 클래스 등 파이썬이 제공하는 예외 처리를 표준 내장 예외처리라고 한다. 표준 내장 예외 처리는 BaseException 클래스와 직간접적으로 파생한 클래스로 제공된다.
프로그래머가 정의하는 사용자 정의 예외처리는BaseException 클래스가 아니라 Exception 클래스(또는 파생 클래스)에서 파생되는 것이 원칙이다. 왜냐하면 BaseException 클래스는 사용자 정의 클래스가 파생하는 것을 전제로 하기 때문이다.
데이터를 검색하는 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개의 모든 데이터를 바닥부터 꼭대기까지 순서대로 출력한다. 스택이 비어있다면 '스택이 비어 있습니다.'를 출력한다.
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 #실패시 -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]")
__len__() 함수와 __countains__()함수 알아보기
__len__() 함수
클래스에 __len__() 함수를 정의하면 클래스형의 인스턴스를 len( ) 함수에 전달할 수 있다. 예를 들어 클래스의 인스턴스 obj에 대한 __len__()함수를 호출하는 obj.__len__()를 간단하게 len(obj)로 작성할 수 있다.
__countains__()
클래스에 __countains__() 함수를 정의하면 클래스형의 인스턴스에 멤버십 판단 연산자인 in을 적용할 수 있다. 예를 들어 클래스형의 인스턴스 obj에 대한 __countains__() 함수를 호출하는 obj.__countains__(x)를 간단히 x in obj로 작성할 수 있다.
📌밑줄 2개(_ _)인 더블 언더스코어(Double Underscore)는 줄여서 던더(Dunder)라고 한다. 그래서 더블 언더스코어 함수를 줄여서 던더 함수라고 하고, __len__()을 던더 렌 던더, 또는 던더 렌이라고 한다.
collection.deque로 스택 구현하기
내장 컨테이너를 제공하고 있다. 또한 여러 컨테이너를 collections 모듈로 제공하며 이때 deque 모듈을 사용하면 스택을 간단하게 구현할 수 있다. deque는 맨 앞과 양쪽에서 원소를 추가, 삭제하는 자료구조인 덱(deque)을 구현하는 컨테이너이며, deque의 주요 속성과 함수를 다음 아래의 블로그를 통해서 살펴보며 이해하는 것을 추천합니다. (스크롤을 내려 속성과 함수를 한 번씩 다 살펴보시길 바랍니다.)
큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조이다. 예를 들어 은행 창구에서 차례를 기다리거나 마트에서 계산을 기다리는 줄을 생각하면 쉽다. 큐에 데이터를 추가하는 작업을 인큐(enqueue)라고 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다. 또 데이터를 꺼내는 쪽을 프런트(front), 데이터를 넣는 쪽을 리어(rear)라고 한다.
배열로 큐 구현하기
스택과 마찬가지로 큐 또한 배열을 사용하여 구현할 수 있다. 다음을 참고하여 배열로 어떻게 큐를 구현하는지 살펴보자.
19
22
37
53
19(디큐)
22
37
53
24(인큐)
22
37
53
24
a ------------------> b ------------------> c
24 인큐 19 디큐
24 인큐하기
데이터 24를 인큐하면 다음과 같이 맨 끝에 저장되어 있는 que[3]의 다음 원소인 que[4]에 24를 저장한다. 처리 복잡도는 O(1)이고 비교적 적은 비용으로 구현할 수 있다.
19 디큐하기
다음으로 데이터 19를 디큐할 때 que[0]에 저장되어 있는 19를 꺼내면서 2번째(즉, que[1]) 이후의 모든 원소를 c와 같이 앞쪽으로 옮겨가야 한다. 이 때 처리 복잡도는 O(n)이며, 데이터를 꺼낼 때마다 이런 작업을 수행한다면 프로그램의 효율성을 기대할 수는 없다.
우선순위 큐
우선순위 큐(priority queue)를 알아보자. 인큐할 때는 데이터에 우선순위를 부여하여 추가하고, 디큐할 때는 우선순위가 가장 높은 데이터를 꺼내는 방식을 사용한다. 파이썬에서 우선순위를 부여하는 큐는 heapq모듈에서 제공하며 heap에서 data의 인큐는 heapq.heappush(heap,data)로 수행하고, 디큐는 heapq,heappop(heap)으로 수행합니다.
링 버퍼로 큐 구현하기
디큐할 때마다 배열의 원소를 옮겨서 효율성이 떨어지는 위의 방법대신 링버퍼(ring buffer)를 사용해서 디큐할 때 배열 안의 원소를 옮기지 않는 큐를 구현하도록 해보자. 배열의 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조이다. 어떤 원소가 맨 앞이고, 어떤 원소가 맨 끝 원소인지 식별하는 변수가 각각 front와 rear이다.
a. 7개의 데이터 35, 56, 24, 68, 95, 73, 19가 늘어선 순서대로 queue[7], queue[8], ...., queue[11], queue[0], queue[1]에 저장된다. front값은 7이고 rear값은 2이다.
b
b. a에서 82를 인큐한 다음의 상태이며 맨 끝의 다음에 위치한 que[rear], 즉 que[2]에 82를 저장하고 rear값을 1 증가시켜 3으로 만든다.
c
링 버퍼로 큐를 구현하면 원소를 옮길 필요 없이 front와 rear 값을 업데이트하는 것만으로도 인큐와 디큐를 수행할 수 있다. 모든 처리 복잡도는 O(1)로 앞에서 본 큐의 처리 복잡도(디큐의 복잡도O(n))보다는 훨씬 복잡도가 낮아서 효율성이 좋다.
이제 링 버퍼를 사용해 큐를 구현하도록 하자. 스택과 마찬가지로 큐를 생성할 때 크기(큐에 넣을 수 있는 데이터의 최대 개수)가 결정된 고정 길이 큐이다. 고정 길이 큐를 구현하는 FixedQueue 클래스를 보여주며 먼저 큐가 비어 있는지 또는 가득 차 있는지 알아내는 예외 처리 클래스와 함수를 살펴보자.
#고정 길이 큐 클래스 FixedQueue 구현하기
from typing import Any
class FiexQueue:
class Empty(Exception):
#비어 있는 FixedQueue에서 디큐 또는 피크할 때 내보내는 예외 처리
pass
class Full(Exception):
#꽉 차있는 FixedQueue에서 인큐할 때 내보내는 예외 처리
pass
def __init__(self,capacity: int) -> None:
#큐 초기화
self.no = 0 #현재 데이터 개수
self.front = 0 #맨 앞 원소의 커서
self.rear = 0 #맨 끝 원소의 커서
self.capacity = capacity #큐의 크기 스택에서는 스택크기로 쓰였다.
self.que = [None] * capacity
def __len__(self) -> int:
#큐에 있는 모든 데이터 개수를 반환
return self.no
def is_empty(self) -> bool:
#큐가 비어있는지 판단
return self.no <= 0
def is_full(self) -> bool:
#큐가 꽉 차있는지 판단
self.no >= self.capacity
예외 처리 클래스 Empty와 Full
비어 있는 큐에 depue( ), peek( ) 함수를 호출할 때 내보내는 예외처리는 Empty 클래스이고, 가득 차있는 큐에 enque( )함수를 호출할 때 내보내는 예외처리는 Full 클래스이다.
초기화하는 __init__( ) 함수
__init__() 함수는 큐 배열을 생성하는 등의 준비 작업을 하며, 다음과 같이 5개의 변수의 값을 설정한다.
que: 큐의 배열로서 밀어 넣는 데이터를 저장하는 list형 배열
capacity: 큐의 최대 크기를 나타내는 int형 정수. 이 값은 배열 que의 원소 수와 일치한다.
front,rear: 맨 앞의 원소, 맨 끝의 원소를 나타내는 인덱스이고 큐에 넣은 데이터 중에 가장 처음 넣은 맨 앞 원소의 인덱스가 front이고, 가장 마지막에 넣은 맨 끝 원소의 바로 다음 인덱스가 rear이다. rear는 다음에 인큐할 때 데이터를 저장하는 원소의 인덱스이다.
no: 큐에 쌓여 있는 데이터 개수를 나타내는 int형 정수로 변수 front와 rear의 값이 같을 경우 큐가 비어있는지 가득 차 있는지를 구별하기 위해 필요하다. 큐가 비어 있는 경우에는 no가 0이 되고, 가득 차 있는 경우에는 capacity와 같은 값이 된다.
__len( ) 함수는 큐에 추가한 데이터 개수를 반환한다. no의 값이 그대로 반환 된다.
큐가 비어 있는지를 판단하는 is_empty( ) 함수
is_empty( ) 함수는 큐가 비어 있는지를 판단한다. 비어 있으면 True를 그렇지 않으면 False를 반환한다.
큐가 가득 차 있는지를 판단하는 is_full( ) 함수
is_full( ) 함수는 큐가 가득 차 있어서 더 이상 데이터를 추가할 수 없는 상태인지를 검사한다. 가득 차 있으면 True를 그렇지 않으면 False를 반환한다.
def enque(self, x:Any) -> None:
if self.if_full():
raise FixedQueue.Full #큐가 가득 차 있는 경우 예외 처리 발생
self.que[self.rear] = x #입력받은 x값을 현제 rear 위치에 넣어준다.
self.rear += 1 #rear을 뒤로 한 칸 보내준다.
self.no += 1 #인큐 해줬으니 큐에 쌓여 있는 데이터 개수를 1개 늘려준다
if self.rear == self.capacity:
self.rear = 0
데이터를 넣는 enque( ) 함수
enque( ) 함수는 큐에 데이터를 인큐한다. 하지만 큐가 가득 차서 인큐할 수 없는 경우엔 예외처리인 FixedQueue.Full을 내보낸다.
def deque(self) -> None:
if self.if_empty():
raise FixedQueue.Empty #큐가 비어 있는 경우 예외 처리 발생
x = self.que[self.front]
self.front += 1
self.no -= 1 #디큐했으니 쌓여있는 데이터 갯수를 1개 빼준다.
# 큐의 크기인 capacity와 같을 경우 front를 1 증가시켜 배열의 맨 앞 인덱스인 0으로 되돌려 준다.
if self.front == self.capacity:
self.front = 0
데이터를 들여다보는 peek( ) 함수
peek( ) 함수는 맨 앞 데이터, 즉 다음 디큐에서 꺼낼 데이터를 들여다본다. que[front]의 값을 반환할 뿐 데이터를 꺼내지는 않으므로 front, rear,no의 값은 변하지 않는다. 큐가 비어 있을 때는 예외 처리 FixedQueue.Empty를 내보낸다.
검색하는 find( ) 함수
find( ) 함수는 큐의 배열 value와 같은 데이터가 포함되어 있는 위치를 알아낸다. 맨끝 쪽으로 선형 검색을 수행하고 이때 스캔은 배열의 맨 앞 원소부터가 아니라 큐의 맨 앞 원소(front)부터 시작한다. 따라서 스캔할 때 주목하는 인덱스 idx를 구하는 식은 (i+front)%capacity이다.
i
0
1
2
3
4
5
6
idx
7
8
9
10
11
0
1
데이터 개수를 세는 count( ) 함수
count( ) 함수는 큐에 있는 데이터(value)의 개수를 구하여 반환한다.
데이터가 포함되어 있는지를 판단하는 __contains( ) 함수
__contains__( ) 함수는 큐에 데이터(value)가 들어있는지 판단한다. 들어있을 땐 True를 그렇지 않을 땐 False를 반환한다. 내부의 count( ) 함수를 호출하여 구현한다.
큐의 전체 원소를 삭제하는 clear( ) 함수
clear( ) 함수는 현재 큐에 들어 있는 모든 데이터를 삭제한다.
큐의 전체 데이터를 출력하는 dump( ) 함수
dump( ) 함수는 큐에 들어 있는 모든 데이터를 맨 앞부터 맨 끝 쪽으로 순서대로 출력한다. 하지만 큐가 비어 있으면 "큐가 비어있습니다."를 출력한다.
def peek(self)->Any:
if.self.is_empty():
raise FixedQueue.Empty
return self.que[self.front]
def find(self,value:Any) -> Any:
#쌓여있는 데이터 개수만큼 for문 반복
for i in range(self.no):
#큐의 맨 앞 원소부터 스캔을 시작하기 위함
idx = (i +self.front) % self.capacity
#검색 성공
if self.que[idx] == value:
return idx
#검색 실패
return -1
def count(self,value:Any) -> bool:
#큐에 있는 value의 개수 반환
c = 0
for i in range(self.no):
idx = (i+self.front) % self.capacity
if self.que[idx] == value:
c+=1
return c
def __contains__(self, value:Any) -> bool:
#큐에 value가 있는지 판단
return self.count(value)
def clear(self) -> None:
#큐의 모든 데이터를 비움
self.no = self.front = self.rear =0
def dump(self) -> None:
if self.is_empty():
print("큐가 비어있습니다.")
else:
for i in range(self.no):
print(self.que[i+self.front]%self.capacity,end="")
print()
양방향 대기열 덱의 구조
양방향 대기열 덱의 구조
덱이란? 덱(deque: double - ended queue)은 맨 앞과 맨 끝 양쪽에서 데이터를 모두 삽입, 삭제할 수 있는 자료구조이다. 2개의 포인터를 사용해 양쪽에서 삭제, 삽입을 할 수 있으며, 큐와 스택을 합친 형태라고 생각하면 된다.
