스택

• 데이터를 임시 저장할 때 사용하는 자료구조로, 후입선출(LIFO)방식임.
  
• 푸시 : 스택에 데이터를 넣는 작업
• 팝 : 스택에서 데이터를 꺼내는 작업

스택 구현하기

• 스택 배열:stk
  데이터를 저장하는 스택 본체(list형 배열)
• 스택 크기:capacity
  스택의 최대 크기
• 스택 포인터:ptr
  스택에 쌓여있는 데이터의 개수

from typing import Any

class FixedStack:
    """고정 길이 스택 클래스"""

    class Empty(Exception):
        """비어 있는 FixedStack에 pop 또는 peek를 호출할 때 내보내는 예외 처리"""
        pass

    class Full(Exception):
        """가득 찬 FixedStack에 push를 호출할 때 내보내는 예외 처리"""
        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() 함수
  비어있으면 True, 아니면 False를 반환
• 스택이 가득 차 있는지 판단하는 if_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()함수
  스택에 데이터를 추가, 스택이 가득 찼을 경우 FixedStack.Full을 통해 예외처리를 내보냄
  스택이 가득 차 있지 않으면 전달받은 value를 배열원소 stk[ptr]에 저장하고 스택 포인터 ptr을 1증가 시킴
• 데이터를 팝하는 pop()함수
  스택의 꼭대기에서 데이터를 꺼내서 값을 반환, 스택이 비어있는 경우 FixedStack.Empty를 통해 예외 처리를 보냄
  스택이 비어있지 않으면 스택 포인터 ptr의 값을 1감소 시키고 stk[ptr]에 저장된 값을 반환
• 데이터를 들여다보는 peek()함수
  스택의 꼭대기 데이터를 들여다봄. 비어있는 경우 FixedStack.Empty를 통해 예외 처리를 내보냄
  스택 포인터는 변화하지 않고 stk[ptr-1]의 값을 반환
• 스택의 모든 데이트 삭제 clear()함수
  스택에 쌓여 있는 데이터를 모두 삭제해 빈 스택을 만듬

    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) -> bool:
        """스택에 포함되어있는 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)

    def dump(self) -> None:
        """덤프(스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력)"""
        if self.is_empty():  # 스택이 비어 있음
            print('스택이 비어 있습니다.')
        else:
            print(self.stk[:self.ptr])

• 데이터를 검색하는 find()함수
  스택 배열 stk 안에 value와 값이 같은 데이터가 있는지 확인
  꼭대기에서 바닥 쪽으로 선형 검색을 수행(인덱스가 큰 쪽에서 작은 쪽)
• 데이터의 개수를 세는 count() 함수
  스택에 쌓여 있는 데이터의 개수를 구하여 반환
• 데이터가 포함되어 있는지 판단하는 __contains__() 함수
  포함돼 있으면 True, 아니면 False를 반환
• 스택의 모든 데이터를 출력하는 dump() 함수
  스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 꼭대기까지 순서대로 출력

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

    def dump(self) -> int:
        """스택 안에 있는 모든 데이터를 나열"""
        print(list(self.__stk))

큐

• 스택과 같이 데이터를 임시 저장하는 자료구조지만 먼저 넣은 데이터를 먼저 꺼내는 선입선출(FIFO) 구조임
  
• 인큐
  큐에 데이터를 추가하는 작업
• 디큐
  데이터를 꺼내는 작업
• 프런트
  데이터를 꺼내는 쪽
• 리어
  데이터를 넣는 쪽

배열로 큐 구현하기

인큐할 때 복잡도는 O(1)
디큐를 하면 맨 앞의 데이터를 꺼내고 다시 모든 원소를 앞쪽으로 한 칸 씩 옮겨야 하기 때문에, 처리의 복잡도는 O(n)임

->데이터를 꺼낼 때마다 이런 작업을 수행하면 프로그램의 효율성이 떨어짐

우선순위 큐

• 인큐할 때 데이터에 우선순위를 부여하고 추가하고, 디큐할 때 우선순위가 가장 높은 데이터를 꺼내는 방식(정렬 알고리즘에 자세히 정리)

링 버퍼로 큐 구현하기

• 디큐할 때 배열 안의 원소를 옮기지 않는 큐
  
• 맨 앞 원소와 맨 끝 원소를 식별하는 변수: front, rear
  논리적인 데이터 순서일 뿐 배열의 물리적 원소의 순서는 아님

  프런트 : 맨 앞 원소의 인덱스
  리어 : 맨 끝 원소 바로 뒤의 인덱스

• 인큐와 디큐를 수행하면 front와 rear의 값이 변함

링 버퍼로 큐를 구현하는 프로그램

from typing import Any

class FixedQueue:

    class Empty(Exception):
        """비어 있는 FixedQueue에 대해 deque 또는 peek를 호출할 때 내보내는 예외처리"""
        pass

    class Full(Exception):
        """가득 찬 FixedQueue에 enque를 호출할 때 내보내는 예외처리"""
        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
        
    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

    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
        
    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()