스택과 큐

스택

연속된 메모리에서 후입선출(LIFO)방식의 자료구조로 데이터를 넣는 작업을 푸시, 꺼내는 작업을 팝이라고 한다.

위에서 연속된 메모리라고 했는데, 스택 자료구조의 가장 기본적인 구현체인 리스트를 이용해 코드를 확인해보자.

아래 코드를 실행해보면,

stk = []
stk.append(0)
stk.append(1)
stk.append(2)
stk.append(3)
stk.append(4)
print(id(stk))
print(id(stk[0]))
print(id(stk[1]))
print(id(stk[2]))
print(id(stk[3]))
print(id(stk[4]))

아래와 같은 결과가 나오는데,

4309557504
4308494608
4308494640
4308494672
4308494704
4308494736

이를 통해, 리스트를 선언하면 stk라는 변수에는 리스트의 메모리 주소(참조값) 이 저장되고, 실제로 값을 추가하고 각 값의 id를 조회해보면 각 메모리 값이 32씩 연속된다는 것을 알 수 있다.

위 코드는 파이썬에서 기본적으로 제공해주는 리스트를 이용해서 알아본 것이고, 이제 스택을 실제로 구현해보자.

스택 구현 코드(고정 길이)

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 # 포인터를 1 증가

    def pop(self) -> Any:
        # 스택의 마지막 값 추출
        if self.is_empty():    # 스택이 빈 경우
            raise FixedStack.Empty # 예외 처리
        self.ptr -= 1 # 포인터 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 # 데이터를 실제로 모두 비울 필요 없이 포인터만 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) -> int:
        # 스택에 value가 몇 개 있는 지 확인
        c = 0
        for i in range(self.ptr): # 바닥 부터 선형 검색
            if self.stk[i] == value: # 검색 성공
                c += 1
        return c

큐

연속된 메모리에서 선입선출(FIFO)방식의 자료구조로 데이터를 넣는 작업을 인큐, 꺼내는 작업을 디큐이라고 한다.

파이썬에서 기본적으로 제공하는 큐는 deque를 제공하는데 deque를 이용해 아래 코드를 실행해보면 큐도 연속된 메모리임을 알 수 있다.

from collections import deque

q = deque()
q.append(1)
q.append(2)
q.append(3)
print(id(q))
print(id(q[0]))
print(id(q[1]))
print(id(q[2]))

# 실행결과
4300567360
4299122992
4299123024
4299123056

고정길이 큐 구현

큐를 구현하는 방법에는 여러가지 가 있는데, 링 버퍼를 이용해서 코드로 구현해보자.

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:
        # 큐에 포함되어 있는 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 clear(self) -> None:
        # 큐 비우기
        self.no = self.front = self.rear = 0