알고리즘 - 자료구조(1) 스택, 큐

이번 포스트에서는 프로그래밍이라는 개념이 탄생할 때부터 사용된 가장 고전적인 자료구조 중 하나인 스택과 큐에 대해 알아보자. 그 중 스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조다.

스택과 큐는 Delete 연산에 의해 집합에서 삭제되는 원소가 미리 결정되어 있는 동적 집합이다. 스택에서는 가장 최근에 삽인된 원소가 삭제된다. 이와 유사하게 큐에서는 집합에서 가장 오랜 시간 동안 존재한 원소가 삭제된다.

파이썬은 스택 자료형을 별도로 제공하지 않지만, 리스트가 사실상 스택의 모든 연산을 지원한다. 큐 또한 마찬가지다. 다만 리스트는 동적 배열로 구현됭 있어 큐의 연산을 수행하기에는 효율적이지 않기 때문에, 큐르 ㄹ위해서는 데크(deque)라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다. 굳이 성능을 고려하지 않는다면 리스트를 잘 사용하기만 해도 충분하다.

1. 스택(Stack)

스택이란?

스택은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(FILO)방식이다. 데이터를 제한적으로 접근할 수 있는 구조이고, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조이다.

스택은 콜 스택(call stack)이라 하여 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조에도 널리 활용된다. 컴파일러가 출력하는 에러도 스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다. 또한 스택은 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다. 이외에도 꽉 찬 스택에 요소를 삽입하고자 할 때 스택에 요소가 넘쳐서 에러가 발생하는 것을 스택 버퍼 오버플로(stack buffer overflow)라고 부른다. 질의응답 서비스 사이트인 스택오버플로의 명칭도 여기서 유래했다.

스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조로서, 스택과 연관된 알고리즘을 제대로 이해하느냐 못하느냐에 따라 기본 알고리즘을 설계할 수 있느냐 없느냐가 결정되기도 한다.

스택 구조

• 스택은 LIFO 또는 FILO 데이터 관리 방식을 따름
• 대표적인 스택의 활용: 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• 주요기능
  - push(): 데이터를 스택에 넣기
  - pop(): 데이터를 스택에서 꺼내기
• 스택의 크기: 스택에 쌓을 수 있는 데이터의 최대 개수
  

스택 구조와 프로세스

• 스택 구조는 프로세스 실행 구조의 가장 기본
• 함수 호출 시 프로세스 실행 구조를 스택과 비교해서 이해 필요

스택의 장단점

장점

• 구조가 단순해서 구현이 쉽다.
• 데이터 저장/읽기 속도가 빠르다.

단점(일반적인 스택 구현 시)

• 데이터 최대 갯수를 미리 정해야 한다. -> 파이썬의 겨우 재귀 함수는 1000번까지만 호출이 가능함
• 저장 공간의 낭비가 발생할 수 있다. -> 미리 최대 갯수만큼 저장 공간 확보해야 함

스택의 경우 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다. 이경우, 위에서 열거한 단점이 있을 수 있다.

스택 구현하기

스택 배열: stk

푸시한 데이터를 저장하는 스택 본체인 list형 배열, 인덱스가 0인 원소를 스택의 바닥이라고 한다.

스택 크기: capacity

스택의 최대 크기를 나타내는 int형 정수이다. 이 값은 배열 stk의 원소 수인 len(stk)와 일치한다.

스택 포인터: ptr

스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값을 스택 포인터라고 한다.

스택 포인터의 범위를 지정할 때 주의할 점

Fixed Stack 클래스를 사용하여 스택 작업을 수행하는 경우 스택 포인터 ptr값은 반드시 0 이상이거나 capcity이하가 된다. 따라서 is_empty(), is_full() 함수는 <,>= 연산자가 아니라 ==를 사용해서 다음과 같이 정의할 수도 있다.

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

하지만 프로그램 오류 등으로 ptr 값이 0보다 작아지거나 capacity보다 커질 가능성도 있으므로 이 방법은 추천하지 않는다. 부등호로 판단하면 스택 배열의 최솟값과 최댓값에서 벗어나 접근하는 것을 막을 수 있다. 이렇게 코드를 간단하게 설계하는 것만으로도 오류 없이 잘 작동할 수 있도록 한다.

예외 처리 클래스 Empty

pop() 함수 또는 peek() 함수를 호출할 때 스택이 비어 있으면 내보내는 예외 처리이다.

STACK-EMPTY(S)
if S.top == 0
    return True
else return False

예외 처리 클래스 Full

push() 함수를 호출할 때 스택이 가득 차 있으면 내보내는 예외 처리이다.

초기화하는 init() 함수

스택 배열을 생성하는 등의 준비 작업을 수행한다. 매개변수 capcity로 전달받은 값을 스택의 크기를 나타내는 필드인 capacity로 복사하여, 원소 수가 capacity이고 모든 원소가 None인 리스트형 stk를 생성한다. 스택이 비어 있으므로 스택 포인터의 값을 0으로 한다.

쌓여 있는 데이터 개수를 알아내는 len() 함수

스택에 쌓여 있는 데이터 개수를 반환한다. 여기서는 스택 포인터 값을 그대로 반환한다.

스택이 비어 있는지를 판단하는 is_empty() 함수

비어 있으면 True, 아니면 False 반환

is_full() 함수

가득 차 있으면 True, 아니면 False 반환

from typing import Any

class FixedStack:

    class Empty(Exception):
        pass
        
    class Full(Exception):
        pass
    
    def __init(self, capcity: int = 256) -> None:
        self.stk = [None] * capacity
        self.capacity = capacity
        self.ptr = 0
        
    def __len__(self):
        return self.ptr
        
    def is_empty(self) -> bool:
        return self.ptr <= 0
        
    def is_full(self) -> bool:
        return self.ptr >= self.capacity

데이터를 푸시하는 push() 함수

스택에 데이터를 추가한다. 스택이 가득 차 더 이상 푸시할 수 없는 경우 FixedStack.Full을 통해 예외 처리를 내보낸다.

PUSH(S, x)
S.top = S.top+1
S[S.top] = x

데이터를 팝하는 pop() 함수

스택의 꼭대기에서 데이터를 꺼내서 그 값을 반환한다. 스택이 비어서 팝할 수 없는 경우에는 FixedStack.Empty를 통해 예외 처리를 내보낸다.

POP(S)
if STACK-EMPTY(S)
    error"스택 부족"
else S.top = S.top-1
    return S[S.top+1]

데이터를 들여다보는 peek() 함수

스택의 꼭대기 데이터(다음에 팝하는 데이터)를 들여다본다. 스택이 비어 있는 경우 FixedStack.Empty를 통해 예외 처리를 내보낸다.

스택의 모든 데이터를 삭제하는 clear() 함수

스택에 쌓여 있는 데이터를 모두 삭제하여 빈 스택을 만든다. 스택 포인터 값을 0으로 하면 끝난다.

    def push(self, value: Any) -> None:
        if self.is_full():
            raise FixedStack.FUll
        self.stk[ptr] = value
        self.ptr += 1
        
    def pop(self) -> Any:
        if self.is_empty():
            raise FixedStack.Empty
        ptr -= 1
        return self.stk[ptr]
        
    def peek(self) -> Any:
        if self.is_empty():
            raise FixedStack.Empty
        return self.stk[ptr-1]
        
    def clear(self) -> None:
        self.ptr = 0

데이터를 검색하는 find() 함수

스택 본체의 배열 stk 안에 value와 값이 같은 데이터가 포함되어 있는지 확인하고, 포함되어 있다면 배열의 어디에 들어 있는지를 검색한다.

데이터 개수를 세는 count() 함수

스택에 쌓여 있는 데이터(value)의 개수를 구하여 반환한다.

데이터가 포함되어 있는지 판단하는 contains() 함수

스택에 데이터(value)가 있는지 판단한다. 있으면 True, 없으면 False를 반환한다. 멤버십 판단 연산자(membership test operator)인 in을 사용할 수 있다.

스택의 모든 데이터를 출력하는 dump() 함수

스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 꼭대기까지 순서대로 출력한다. 스택이 비어 있으면 '스택이 비어 있습니다.'를 출력한다.

    def find(self, value: Any) -> int:
        for i in range(self.ptr-1, -1, -1):
            if self.stk[i] == value
                return i
        return -1
        
    def count(self, value: Any) -> int:
        c = 0
        for i in range(self.ptr)
            if self.stk[i] == value:
                c += 1
        return c
        
    def __contains__(self, value: Any) -> bool:
        if self.find(value) == -1:
            return False
        else:
            return True
            
    def dump(self) -> None:
        if self.is_empty():
            print("스택이 비어 있습니다.")
        else:
            print(self.stk[:self.ptr])

던더(dunder) 함수

밑줄 2개(__)인 더블 언더스코어를 줄여서 던더라고 한다. 던더 함수로 len()함수와 contains() 함수를 정의하면 len(obj), x in obj로 사용할 수 있다.

2. 큐(Queue)

큐란?

스택과 같이 데이터를 임시 저장하는 자료구조이다. 하지만 스택처럼 가장 나중에 넣은 데이터를 가장 먼저 꺼내지 않는다. 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조이다.

관련 용어

• 인큐(Enqueue): 큐에 데이터를 넣는 기능
• 디큐(Dequeue): 큐에서 데이터를 꺼내는 기능
• 프런트(Front): 데이터를 꺼내는 쪽
• 리어(Rear): 데이터를 넣는 쪽

파이썬 queue 라이브러리

• Queue(), LifoQueue(), PriorityQueue() 제공
• Queue(): 가장 일반적인 큐 자료구조
• LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조(like 스택)
• PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

어디에 많이 쓰일까?

멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현하기 위해 많이 사용됨(운영체제 참조)

큐 구현하기

인큐 시 맨 끝에 넣고, 디큐 시 가장 앞에서 꺼낸 후 모든 원소를 하나씩 앞으로 옮긴다. 넣을 땐 처리 복잡도가 O(1)이지만, 꺼낼 때는 O(n)이다.

링버퍼로 큐 구현하기

링버퍼 : 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조
어떤 원소가 맨 앞 원소이고, 끝 원소인지 식별하는 변수가 각각 front, rear이다.

• 프런트(front): 맨 앞 원소의 인덱스
• 리어(rear): 맨 끝 원소 바로 뒤의 인덱스(다음 인큐되는 데이터가 저장되는 위치)

링버퍼로 구현 시 꺼낼 때, 넣을 때 모두 처리 복잡도가 O(1)이다.

예외 처리 클래스 Empty와 Full

스택과 같음

초기화하는 __init() 함수

큐 배열을 생성하는 등의 준비 작업을 하며 다음과 같이 5개의 변수에 값을 설정한다.

• que: 큐의 배열로서 밀어 넣는 데이터를 저장하는 list형의 배열
• capacity: 큐의 최대 크기를 나타내는 int형 정수. que의 원소 수와 일치
• front, rear: 맨 앞 원소, 맨 뒤 원소 인덱스
• no: 큐에 쌓여 있는 데이터 개수를 나타내는 int형 정수. 변수 front와 rear의 값이 같을 경우 큐가 비어 있는지 또는 가득 차 있는지 구별하기 위해 필요. 큐가 비어 있는 경우 no가 0이 되고, 가득 차 있는 경우 capacity와 같은 값이됨

is_full(), is_empty(), len() 함수

스택과 같음

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.capcity = capacity
        self.que = [None] * self.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

데이터를 넣는 enque() 함수

큐에 데이터를 인큐한다. 큐가 가득 차서 인큐할 수 없는 경우 예외 처리인 FixedQueue.Full을 내보낸다.

ENQUEUE(Q,x)
    Q[Q.tail] = x
    if Q.tail == Q.length
        Q.tail = 1
    else Q.tail = Q.tail + 1

    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

데이터를 꺼내는 deque() 함수

큐의 맨 앞부터 데이터를 디큐하여 그 값을 반환한다. 그러나 큐가 비어 있어 디큐할 수가 없는 경우 예외 처리인 FixedQueue.Empty를 내보낸다.

DEQUEUE(Q)
    x = Q[Q.head]
    if Q.head == Q.length
        Q.head = 1
    else Q.head = Q.head + 1
    return x

    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

peek(), find(), count(), contains(), clear(), dump() 함수

스택과 같음

    def peek(self) -> Any:
        if self.is_empty():
            raise FixedQueue.Empty
        return self.que[self.front]
        
    def find(self, vlaue: 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) -> int:
        c = 0
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.que[idx] == value:
                c += 1
        return -1
        
    def __contains__(self, value: Any) -> bool:
        return self.count(value) > 0
    
    def clear(self) -> None:
        self.front = self.rear = self.no = 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()
        

++ 링 버퍼의 활용 ++

링 버퍼는 오래된 데이터를 버리는 용도로 활용할 수 있다. 예를 들어 원소 수가 n인 배열에 데이터를 계속해서 입력할 때 가장 최근에 들어온 데이터 n개만 저장하고 나머지 오래된 데이터는 버리는 경우에 이용하는 경우이다.

n = int(input())
a = [None] * n

cnt = 0
while True:
    a[cnt % n] = int(input())
    cnt += 1
    
    retry = input("n")
    if retry in {"N", "n"}
        break


i = cnt - n
if i < 0: i = 0

while i < cnt:
    print(a[i%n])
    i += 1