연등 때 먹는 프링글스는 한 번 꺼내 먹게되면 계속 먹게된다.
시즈닝이 잘 안 묻어 있는 조각을 보면 아래 있는 조각을 꺼내고 싶지만,
통이 좁아서 꺼내기가 어렵다.

스택(stack)도 마찬가지로 먼저 입력된 데이터를 바로 꺼낼 수 없다.

???: 스택이 뭔데?

알려줄테니 따라와라

스택

스택은 데이터를 임시 저장할 때 사용하는 자료구조이고,
데이터의 입력과 출력 순서는 후입선출(LIFO) 방식을 사용한다.

스택 구현

스택을 구현하기 위해서 기본 개념을 잡고 가자.

푸시(push): 스택에 데이터를 넣는 작업
팝(pop): 스택에서 데이터를 꺼내는 작업

파이썬에서 스택은 리스트형 배열로 구현할 수 있고,
인덱스가 0인 원소를 스택의 바닥, 가장 마지막에 푸시한 데이터는 top이라고 사용한다.

그럼 스택을 구현해보자.

내장함수로 구현

a_list.append(1) : 괄호 안의 요소를 리스트 맨 뒤에 넣음

a_list = [1,2,3]
a_list.append(1)
=> [1,2,3,1]

a_list.pop() : 리스트의 맨 뒤에 요소를 꺼내고 리스트에서 삭제함

a_list = [1,2,3]
a_list.pop()
=> [1,2]

print(a_list.pop())
출력: 2
a_list : [1]

클래스로 구현

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 is_empty(self) -> bool:
        # 스택이 비어 있는지 판단
        return self.ptr <= 0
    
    def is_full(self) -> bool:
        # 스택이 가득 차 있는지 판단
        return self.ptr >= self.capacity
    
    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]

스택 포인터(ptr): 스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값
스택이 비어 있으면 ptr의 값은 0, 가득 차 있으면 capacity와 같은 값이 된다.

큐

큐(Queue) 는 스택과 같이 데이터를 임시 저장하지만,
선입선출(FIFO)구조라는 점에서 차이가 있다.

큐 구현

큐를 구현하기 전 마찬가지로 개념부터 잡고 가자.

인큐(enqueue): 큐에 데이터를 추가하는 작업
디큐(dequeue): 데이터를 꺼내는 작업
프런트(front): 데이터를 꺼내는 쪽
리어(rear): 데이터를 넣는 쪽 (back과 동일)

스택과 마찬가지로 큐 또한 배열을 사용하여 구현한다.

내장함수로 구현

파이썬에서 큐를 사용하는 가장 간단한 방법은 list를 사용하는 것이다.
list 객체의 pop(0) 함수를 호출하면 첫 번째 데이터를 제거할 수 있다.

queue = [4, 5, 6]
queue.append(7)
queue.append(8)

queue.pop(0)
queue.pop(0)

print(queue)

반대 방향으로 큐 자료 구조를 사용하고 싶다면 insert(0, x) 함수를 사용하면
rear에서 데이터가 들어가고 front에서 나오게 된다.

리스트로 큐를 구현하는 방법이 간단해서 자주 사용하려 했지만,
공부를 하는 과정에서 이 방법은 큰 단점이 있다는 것을 알게 됐다.

파이썬의 list는 다른 언어의 배열처럼 무작위 접근(random access)에 최적화된 자료구조 이다.

첫 번째 데이터를 제거한 후 그 뒤에 있는 모든 데이터를 앞으로 한 칸씩 당기고,
맨 앞에서 데이터를 삽입하는 경우 그 전 모든 데이터를 뒤로 한 칸씩 밀어줘야 하기 때문에
pop(0) 또는 insert(0, x) 연산은 시간 복잡도 0(n)으로
데이터의 개수가 많아질수록 느려진다는 단점이 있다.

덱(deque)으로 구현

from collections import deque

queue = deque([4, 5, 6])
queue.appendleft(3)
queue.appendleft(2)

queue.pop()
queue.pop()

>>> print(queue)
deque([2, 3, 4])

collections모듈의 덱(deque) 자료구조는 데이터를 양 방향에서 추가하고 제거할 수 있다.

popleft()와 appendleft(x) 메서드를 제공하여 첫 번째 데이터를 제거하거나 추가할 수 있다.

위의 두 메서드는 모두 O(1)의 시간 복잡도를 가지고 있지만,
내부적으로 linked list를 사용하고 있기 때문에
i 번째 데이터에 접근하려면 맨 앞/뒤부터 i 번 순회(iteration)가 필요하다.

링 버퍼로 구현

링 버퍼 자료구조를 사용하면 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되어
디큐할 때 배열 안의 원소를 옮기지 않아도 된다.

front와 rear의 값을 업데이트 하는 것만으로 인큐와 디큐를 수행하기 때문에
모든 처리의 복잡도는 O(1)이다.

큐에 넣을 수 있는 데이터의 최대 개수가 결정된 고정 길이 큐를 구현해보자.

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
    
    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:
        # rear값과 큐의 크기인 capacity값이 같은 경우 rear를 배열의 맨 앞 인덱스 0으로 되돌린다.
            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:
        # front값과 큐의 크기인 capacity값이 같은 경우 front를 1 증가시켜 배열의 맨 앞 인덱스 0으로 되돌린다.
            self.front = 0
        return x
    
    def peek(self) -> Any:
        # 꼭대기 데이터를 들여다봄
        if self.is_empty():
            raise FixedQueue.Empty
        return self.que[self.front]
    
    def clear(self) -> None:
        # 모든 데이터를 삭제
        self.no = self.front = self.rear = 0

링 버퍼는 오래된 데이터를 버리는 용도로 활용할 수 있다.

원소 수가 n인 배열에 데이터를 계속 입력할 때
가장 최근에 들어온 데이터 n개만 저장하고, 나머지 오래된 데이터를 버리는 경우를 구현해보자.

# 원하는 개수(n)만큼 값을 입력받아 마지막 n개를 저장

n = int(input('정수를 몇 개 저장할까요?: '))
a = [None] * n

cnt = 0
while True:
    a[cnt % n] = int(input(f'{cnt + 1}번째 정수를 입력하세요.: '))
    cnt += 1
    
    retry = input(f'계속 할까요?(Y: Yes / N: No): ')
    if retry in {'N', 'n'}:
        break
        
i = cnt - n
if i < 0: i = 0
    
while i < cnt:
    print(f'{i + 1}번째 = {a[i % n]}')
    i += 1

cnt가 10개 이하라면 앞에서 차례대로 출력할 수 있지만,
10개 이상인 경우에는 마지막에 저장된 10개(n)의 데이터 순서로 출력해야 한다.

그래서 마지막에 나머지 연산자 %를 사용하여 마지막에 남은 값의 인덱스 순서대로 출력하는 것이다.

이제 문제 풀어보면서 실제로 적용해보자~