스택(Stack)

출처 : geeksforgeeks

LIFO

last in, first out : 마지막으로 들어온 것(push)이 가장 먼저 나간다.(pop)

list

python에서는 많은 내장함수를 가지고 있는 list로 구현할 수 있다.

파이썬 구현

from typing import Any

class FixedStack:
    class Empty(Exception):
        pass

    class Full(Exception):
        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

    def push(self, value: Any) -> None:
        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

    def find(self, value: Any) -> Any:
        for i in range(self.ptr - 1, -1, -1):
            if self.stk[i] == value:
                return i
        return -1

    def count(self, value: Any) -> bool:
        cnt = 0
        for i in range(self.ptr):
            if self.stk[i] == value:
                cnt += 1
        return cnt

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

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

시간복잡도

검색 : O(N)
삭제 : O(1)
추가 : O(1)

원하는 값을 삭제하거나 추가하고자 한다면 O(1)이 아니라 O(N)이 될 수 있다.

큐(Queue)

출처 : geeksforgeeks

FIFO

fisrt in, first out : 가장 먼저 들어왔던 것이(enqueue), 제거될 때에도 가장 먼저 제거(dequeue)된다.

deque

python에서는 deque를 이용해서 큐를 구현할 수 있다. deque를 이용해서 스택도 구현이 가능하다. deque는 append, appendleft와 pop, popleft로 후입, 선입과 후출, 선출이 가능하기 때문이다.

파이썬 구현

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) -> bool:
        cnt = 0
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.que[idx] == value:
                cnt += 1

        return cnt

    def __contains__(self, value: Any) -> bool:
        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()

시간복잡도

검색 : O(N)
삭제 : O(1)
추가 : O(1)

마찬가지로 원하는 값을 삭제하거나 추가하고자 할 때 O(1)이 아니라 O(N)이 될 수 있다.

배열에서 가장 맨 앞의 원소를 제거할 경우, 그 뒤의 원소들이 앞으로 shift되어 많은 데이터 이동이 일어나 제거 기능의 시간 복잡도가 O(N)이었다. 이는 큐도 동일하다. 큐는 FIFO가 원칙이므로 제거 시 맨 앞의 원소가 제거되고 뒤의 원소들이 앞으로 shift된다.

허나 deque를 이용하면 큐에서 제거 기능 사용 시 shift를 막을 수 있다. deque는 linked list 구조로 만들어졌기 때문이다.