[구버전] [Python] 03. 스택과 큐

📌 스택이란?

📚 스택 알아보기

📃 스택 (stack)

• 데이터를 임시 저장할 때 사용하는 자료구조
• 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식
  • 푸시(push) : 스택에 데이터를 넣는 작업
  • 팝(pop) : 스택에서 데이터를 거내는 작업
  • 겹쳐쌓은 접시처럼 데이터를 넣고 꺼내는 작업을 맨위부터 진행
  • 푸시하고 팝하는 윗부분을 꼭대기(top), 아랫 부분을 바닥(bottom)

 

📚 스택 구현하기

📃 스택을 구현하는데 필요한 데이터

• 스택 배열 : stk
  • 푸시한 데이터를 저장하는 스택 본체인 list 배열
  • 인덱스가 0인 원소가 스택의 바닥
  • 가장 먼저 푸시하여 데이터를 저장하는 곳은 stk[0]
• 스택 크기 : capacity
  • 스택의 최대 크기를 저장하는 정수
  • = len(stk)
• 스택 포인터 : ptr
  • 스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값
  • 스택이 비어있으면 ptr은 0
  • 가득 차 있으면 capacity와 같음

 

📃 스택 만들기

# fixed_stack.py
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( ) 함수
• 쌓여 있는 데이터 개수를 알아내는 len( ) 함수
• 스택이 비어 있는지를 판단하는 is_empty( ) 함수
• 스택이 가득 차 있는지를 판단하는 is_full( ) 함수

 

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( ) 함수
  • 스택에 데이터를 추가함
  • 스택이 가득 차서 더 이상 푸시할 수 없다면 FixedStack.Full로 예외 처리를 보냄
• pop( ) 함수
  • 스택의 꼭대기에서 데이터를 꺼내서 그 값을 반환
  • 스택이 비어서 팝할 수 없다면 FixedStack.Empty를 통해 예외 처리를 보냄
  • 스택이 비어있지 않는다면 스택 포인터의 값을 1감소하고 stk[ptr]에 저장된 값을 반환
• peek( ) 함수
  • 스택의 꼭대기 데이터(다음에 팝하는 데이터)를 보냄
  • 스택이 비어있는 경우 FixedStack.Empty를 통해 예외 처리를 보냄
  • 스택이 비어있지 않는다면 꼭대기 원소 stk[ptr-1]에 저장된 값을 반환
  • 데이터의 입출력은 없으므로 ptr은 변화하지 않음
• clear( ) 함수
  • 스택에 샇여 있는 데이터르 모두 삭제하여 빈 스택으로 만듦
  • 스택 포인터를 0으로 만듦

 

📃 raise문(raise statement)으로 예외 처리

• 프로그램의 예외 처리를 의도적으로 내보냄
• 파이썬이 제공하는 예외 처리는 표준 내장 예외 처리라고 함
• 표준 내장 예외 처리는 BaseException 클래스와 직간접적으로 파생한 클래스로 제공
• 프로그래머가 정의하는 사용자 정의 예외 처리는 BaseExcption 클래스가 아닌 Exception 클래스에서 파생

def find(self, value: Any) -> Any:
        """스택에서 vlaue를 찾아 인덱스를 반환(없으면 -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 dump(self) -> None:
        """덤프(스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력)"""
        if self.is_empty():
            print('스택이 비어 있습니다.')
        else:
            print(self.stk[:self.ptr])

• find( ) 함수
  • 스택 본체의 stk 안에 vlaue와 같은 값이 있는지 검사
  • 검색은 꼭대기쪽에서부터 바닥쪽으로 선형 검색을 진행함
  • 검색에 성공하면 발견한 원소의 인덱스를 반환하고, 실패하면 -1을 반환
• count( ) 함수
  • 스택에 쌓여 있는 데이터의 개수를 구하여 반환
• contain( ) 함수
  • 스택에 데이터가 있는지 판단
  • 있으면 True, 없으면 False
  • 멤버십 판단 연산자(membership test operator)인 in을 사용하여 수행
• dump( ) 함수
  • 스택에 샇여 있는 ptr개의 모든 데이터를 순서대로 출력

 

📃 스택 프로그램 만들기

#fixed_stack_test.py
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.검색:
        x = int(input('검색할 값을 입력하세요: '))
        if x in s:
            print(f'{s.count(x)}개 포함되고, 맨 앞의 위치는 {s.find(x)}입니다.')
        else:
            print('검색값을 찾을 수 없습니다.')

    elif menu == Menu.덤프:
        s.dump()

    else:
        break

 

📚 collections.deque로 스택 구현하기

• 파이썬은 여러 컨테이너를 collections 모듈로 제공
• namedtuple( ), deque, ChainedMap, Counter, 등과 같은 컬렉션들이 제공
• deque 모듈을 사용하면 스택을 간단하게 구현

 

 

📃 deque의 주요 속성과 함수

속성과 함수	설명
maxlen 속성	deque의 최대 크기를 나타내는 속성
append(x)	deque의 맨 끝(오른쪽)에 추가
appendleft(x)	deque의 맨 끝(왼쪽)에 추가
clear( )	deque의 모든 원소를 삭제하고 크기를 0으로 변경
count(x)	deque의 얕은 복사(shallow copy)
extend(iterable)	순차 반복 인수 iterable에서 가져온 원소를 deque의 맨 끝(오른쪽)에 추가하여 확장
index(x[, start[, stop]])	deque 안에 있는(인덱스 start부터 인덱스 stop까지 양 끝을 포함한 범위) x 가운데 가장 파에 있는 원소의 위치를 반환
insert(i, x)	x를 deque의 i 위치에 삽입
pop( )	deque의 맨 끝(오른쪽)에 있는 원소를 1개 삭제하고 그 원소를 반환
remove(value)	vlaue의 첫 번째 항목을 삭제
reverse( )	deque 원소를 역순으로 재정렬하고 None을 반환
rotate(n = 1)	dequed의 모든 원소를 n만큼 오른쪽으로 밀어냄

 

📃 deque를 활용하여 스택 만들기

# stack.py
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가 포함되어 있는지 판단"""
        return self.count(value)

    def dump(self) -> int:
        """스택 안에 있는 모든 데이터를 나열(바닥에서 꼭대기 순으로 출력)"""
        print(list(self.__stk))

 

📌 큐란?

📚 큐 알아보기

• 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(LIFO) 구조
• 인큐(enqueue) : 데이터를 추가하는 작업
• 디큐(dequeue) : 데이터를 꺼내는 작업
• 데이터를 꺼내는 쪽을 프런트(front), 데이터를 넣는 쪽은 리어(rear)

 

📚 배열로 큐 구현하기

• 큐 또한 배열을 사용하여 구현
• 인큐의 처리 복잡도 : O(1)
• 디큐의 처리 복잡도 : O(n), 선출 후 원소를 앞으로 옮김

 

📚 링 버퍼로 구현하기

• 링 버퍼(ring buffer) : 디큐할 때 배열 안의 원소를 옮기지 않는 큐
• 원소를 옮길 필요 없이 front와 rear의 값을 업데이트하는 것만으로도 인큐, 디큐 가능

# fixed_queue.py
from typing import Any

class FixedQueue:

    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:
        """큐가 가득 차 있는지 판단"""
        return self.no >= self.capacity

• 예외 처리 클래스
  • Empty : 비어있는 큐에 deque(), peek() 함수를 호출할 때 보내는 예외 처리
  • Full : 가득 차 있는 큐에 enque() 함수를 호출할 때 보내는 예외 처리

.

• 초기화하는 init()
  • que : 큐의 배열로 밀어 넣는 데이터를 저장하는 list 배열
  • capacity : 큐의 최대 크기를 나타내는 int형 정수
  • front, rear : 맨 앞의 원소, 맨 끝의 원소를 나타내는 인덱스
  • no : 큐에 쌓여 있는 데이터 개수를 나타내는 int형 정수
• len()
  • 큐에 추가한 데이터 개수를 반환
• is_empty()
  • 큐가 비어있는지를 판단
• is_full()
  • 큐가 가득차 있어서 데이터를 추가할 수 없는 상태인지를 검사

 

📃 데이터를 넣는 enque() 함수

    def enque(self, x: Any) -> None:
        """데이터 x를 인큐"""
        if self.is_full():  # 큐가 가득 차 있는 경우 예외 처리 발생
            raise FixedQueue.Full
        self.que[self.rear] = x
        self.rear += 1
        self.no += 1
        if self.rear == self.capacity:
            self.rear = 0

• enque() 함수는 큐에 데이터를 인큐
• 큐가 가득 차서 인큐할 수 없는 경우에만 FixedQue.Full을 내보냄
• rear 값이 배열의 맨 끝인 경우 rear를 배열의 맨 앞 인덱스 0으로 되돌림
• 다음에 인큐하는 데이터가 que[0] 위치에 제대로 저장

 

📃 데이터를 꺼내는 deque() 함수

    def deque(self) -> Any:
        """데이터를 디큐"""
        if self.is_empty(): # 큐가 비어 있는 경우 예외 처리 발생
            raise FixedQueue.Empty
        x = self.que[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capacity:
            self.front = 0
        return x

• deque() 함수는 큐의 맨 앞부터 데이터를 디큐하여 그 값을 반환
• 큐가 비어있어 디큐할 수 없는 경우에 예외 처리인 FixedQueue.Empty를 내보냄
• 디뷰하기 전에 front가 배열의 맨 끝인 경우, front를 1증가시켜 배열의 맨 앞 인덱스인 0으로 되돌림
• 다음에 디큐를 수행할 때 데이터를 que[0] 위치에서 꺼냄

 

    def peek(self) -> Any:
        """큐에서 데이터를 피크(맨 앞 데이터를 들여다봄)"""
        if self.is_empty():
            raise FixedQueue.Empty
        return self.que[self.front]

    def find(self, value: Any) -> Any:
        """큐에서 value를 찾아 인덱스를 반환(없으면 -1을 반환)"""
        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()

• peek() 함수
  • 맨 앞 데이터, 즉 다음 디큐때 꺼낼 데이터를 들여다봄
  • 큐가 비어있다면 예외 처리 FixedQueue.Empty를 내보냄
• find() 함수
  • 큐의 배열에서 value와 같은 데이터가 포함되어 있는 위치를 알아냄
  • 맨 앞에서 맨 끝쪽으로 선형 검색
  • 스캔할 때 주목하는 인덱스를 구하는 식은 (i + front) % capacity
• count() 함수
  • 큐에 있는 데이터(value) 개수를 구하여 반환
• contains() 함수
  • 큐에 데이터가 들어있는지를 판단
  • 내부의 count() 함수를 호출하여 구현
• clear() 함수
  • 현재 큐에 들어 있는 모든 데이터를 삭제
  • 디큐가 no, front, rear 값으로 수행되므로 que 배열의 원솟값을 변경할 필요는 없습니다
• dump() 함수
  • 큐에 들어가 있는 모든 데이터를 맨 앞부터 맨 끝쪽으로 순서대로 출력

 

📃 링 버퍼로 큐 프로그램 만들기

# fixed_que_test.py

from enum import Enum
from fixed_queue import FixedQueue

Menu = Enum('Menu', ['인큐', '디큐', '피크', '검색', '덤프', '종료'])

def select_menu() -> Menu:
    """메뉴 선택"""
    select = [f'({m.value}}){m.name}' for m in Menu]
    while True:
        print(*select, sep='    ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)

q = FixedQueue(64)

while True:
    print(f'현재 데이터 개수: {len(q)} / {q.capacity}')
    menu = select_menu()

    if menu == Menu.인큐:
        x = int(input('인큐할 데이터를 입력하세요: '))
        try:
            q.enque(x)
        except FixedQueue.Full:
            print('큐가 가득찼습니다')

    elif menu == Menu.디큐:
        try:
            x = q.deque()
            print(f'디큐한 데이터는 {x}입니다')
        except FixedQueue.Empty:
            print('큐가 비어있습니다.')

    elif menu == Menu.피크:
        try:
            x = q.peek()
            print(f'피크한 데이터는 {x}입니다')
        except FixedQueue.Empty:
            print('큐가 비어있습니다.')            

    elif menu == Menu.검색:
        x = int(input('검색할 데이터를 입력하세요: '))
        if x in q:
            print(f'{q.count(x)}개 포함되고, 맨 앞의 위치는 {q.find(x)}입니다')
        else:
            print('검색값을 찾을 수 없습니다')

    elif menu == Menu.덤프:
        q.dump()

    else:
        break

    elif menu == Menu.덤프:

• 현재 작성한 링버퍼는 오래된 데이터를 지움
• 최근 입력된 n개의 데이터만 저장함