스택과 큐

이번 단원은 OS 에서 배웠던 기초 지식이 있었던 탓인지 코드가 길어도 이해하기 쉬웠고, 코드를 읽으며 이해가 바로바로 되니까 재미가 붙었던 단원이다. 

 

그랬던 탓인지 딱히 궁금증이 생기거나 막히는 부분 없이 무난하게 잘 공부했던 것 같다.

---

스택

 

스택이란 데이터를 임시저장하는 자료구조로서 후입선출 (LIFO : Last In First Out)  방식을 띄고있다. 한마디로 가장 먼저 들어간 데이터가 가장 마지막에 나온다는 뜻이다.

 

스택에서 데이터를 넣을 때 쓰는 용어는 푸시 (PUSH), 데이터를 꺼낼때는 팝 (POP) 이라고 한다. 

 

스택을 구성하는 코드는 다음과 같다.

from typing import Any


class FixedStack:
    class Empty(Exception):  # 비어있는 스택에 팝할 때 내보내는 예외처리
        pass

    class Full(Exception):  # 가득 차있는 스택에 푸시할 때 내보내는 에외처리
        pass

    def __init__(self, capacity):
        self.stk = [None] * capacity  # 스택
        self.capacity = capacity  # 스택의 크기
        self.ptr = 0  # 포인터

    def __len__(self) -> int:  # 스택에 차있는 데이터의 개수 (ptr)
        return self.ptr

    def is_empty(self) -> bool:  # 스택이 비어있는지
        return self.ptr <= 0

    def is_full(self) -> bool:
        return self.ptr >= self.capacity

    def push(self, val):  # 푸시
        if self.is_full():
            raise FixedStack.Full
        self.stk[self.ptr] = val
        self.ptr += 1

    def pop(self):  # 팝
        if self.is_empty():
            raise FixedStack.Empty
        self.ptr -= 1
        return self.stk[self.ptr]

    def peek(self):  # 가장 꼭대기에 있는 데이터를 봄 (가장 최근데이터)
        if self.is_empty():
            raise FixedStack.Empty
        return self.stk[self.ptr - 1]

    def clear(self):  # 전체삭제
        self.ptr = 0

    def find(self, val):
        for i in range(self.ptr - 1, -1, -1):  # 위에서 아래로
            if self.stk[i] == val:
                return i
        return -1

    def count(self, val):  # 데이터의 개수
        c = 0
        for i in range(self.ptr):
            if self.stk[i] == val:
                c += 1
        return c

    def __contains__(self, val) -> bool:
        return self.count(val) > 0

    def dump(self):  # 덤프
        if self.is_empty():
            print('스택이 비어 있습니다.')
        else:
            print(self.stk[:self.ptr])

코드 해석을 하자면 먼저 5번과 8번줄에서 스택이 비어있거나 가득 차있을 경우를 대비해 class Empty 와 Full 을 만들어 예외처리를 해주었다.

 

그 뒤로는 스택의 특징인 후입선출 알고리즘을 이용해 푸시와 팝 등 여러 스택에서 필수요소들의 함수를 만들었고 실행 코드를 통해 실행하면 끝이다.

 

다음은 실행 코드이다. 

from enum import Enum
from stack import FixedStack

Menu = Enum('Menu',['push','pop','peek','clear','search','dump','exit'])

def select_menu() -> Menu:
    s = [f'({m.value}){m.name}'for m in Menu]
    while (1):
        print(*s,sep = '  ',end='')

        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)

s = FixedStack(64)  # 64크기의 스택

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

    if menu == Menu.push:
        x = int(input('데이터를 입력하시오 : '))
        try:
            s.push(x)
        except FixedStack.Full:
            print('스택이 가득 차있습니다.')

    elif menu == Menu.pop:
        try:
            x = s.pop()
            print(f'pop한 데이터는 {x}입니다.')
        except FixedStack.Empty:
            print('스택이 비어있습니다.')

    elif menu == Menu.peek:
        try:
            x = s.peek()
            print(f'peek한 데이터는 {x}입니다')
        except FixedStack.Empty:
            print('스택이 비어있습니다.')

    elif menu == Menu.search:
        x = int(input('검색할 값 입력 : '))
        if x in s :
            print(f'{s.count(x)}개 포함되고, 가장 바깥의 위치는 {s.find(x)}입니다.')
        else :
            print('검색값을 찾을 수 없습니다.')

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

    elif menu == Menu.clear:
        s.clear()

    else :
        break

앞서 만들었던 함수들을 이용해 스택의 구성을 만들었고 실행만 한 코드이다. 

 

큐

 

큐란 스택과는 반대로 선입선출(FIFO : First In First Out) 형식을 갖고있는 자료구조이다.

 

가장 먼저 들어온 데이터가 가장 먼저 나가는 선입선출은 데이터를 추가하는 작업을 인큐 꺼내는 작업을 디큐라 하고 데이터를 꺼내는 쪽을 프런트, 넣는 쪽을 리어라 한다.

 

다음은 큐를 구현한 코드이다.

from typing import Any


class FixedQueue:
    class Empty(Exception):
        pass

    class Full(Exception):
        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:
        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:
        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) -> Any:
        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) -> Any:
        return self.count(value)

    def clear(self) -> None:
        self.no = self.front = self.capacity = 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()