Stack(스택)

스택은 후입선출(Last-In First-Out, LIFO) 의 원리를 따르는, 즉 가장 최근에 추가된 요소가 가장 먼저 제거되는 자료구조이다. 주요 메소드는 다음과 같다.

• push() : 스택의 맨 위에 원소를 추가
• pop() : 스택의 맨 위 원소를 제거하고 반환
• peek() : 스택의 맨 위 원소를 반환하지만 제거는 X (= stack[-1])
• empty() : 스택이 비어있다면 1, 그렇지 않다면 0 반환

스택은 데이터의 삽입과 삭제가 동일한 위치에서 이루어지는 자료구조로, 스택의 최상단 원소 top에 대한 접근만이 가능하다. push의 경우 top 위치에 원소가 추가되고 pop의 경우 top 위치의 원소가 제거되는 방식이다.

Overflow/Underflow

• Overflow : 스택에서 오버플로우는 스택에 push 시 스택의 공간이 가득 차서 더이상 push할 수 없을 때 발생한다. 즉 스택이 할당된 메모리 공간을 초과해 저장하려고 할 때 발생하는데 주로 재귀호출이 중첩되거나 반복문에서 스택에 많은 데이터를 삽입할 때 발생할 수 있다.
• Underflow : 스택에서 pop 연산 시 스택이 비어있어 제거할 데이터가 없는 상황일 때 발생한다.

위처럼 스택에서 오버/언더플로우를 방지하기 위해 연산 전 적절한 검사 수행 이후에 연산을 수행하도록 하여야 한다.

스택 구현

파이썬에서 리스트를 통해 간단히 스택을 구현할 수 있다.

class Stack:
    def __init__(self):
        self.stack = []

    def empty(self):
        return len(self.stack) == 0

    def push(self, element):
        self.stack.append(element)

    def pop(self):
        if not self.empty():
            return self.stack.pop()
        else:
            raise IndexError("cannot pop because of an empty stack")

    def peek(self):
        if not self.empty():
            return self.stack[-1]
        else:
            raise IndexError("cannot peek because of an empty stack")

    def size(self):
        return len(self.stack)

내장 라이브러리 사용 - Deque

from collections import deque

stack = deque()
stack.append(1)	# 원소 삽입
stack.pop()		# 
stack[-1]	# (=peek)

파이썬에서는 스택을 위한 별도 라이브러리는 존재하지 않아 양쪽 끝으로의 추가와 제거를 지원하는 collections 모듈의 deque(Double-Ended Queue)를 이용해 사용할 수 있다.

스택의 top 부분에 대해서만 push, pop, peek 연산이 수행되므로 모두 O(1)의 시간 복잡도를 갖는다. 비교적 간단한 구조를 갖고 있어 효율적으로 연산이 수행될 수 있다.

---

Queue (큐)

큐는 스택과 달리 선입선출(First-In First-Out, FIFO) 의 원리를 따르는 자료구조로, 가장 먼저 삽입된 데이터가 가장 먼저 제거된다. 큐에서는 다음의 주요 연산을 지원한다.

• enqueue() : 큐의 가장 뒤쪽에 원소 삽입
• dequeue() : 큐의 가장 앞쪽 원소를 제거하고 반환
• peek(), front() : 큐의 맨 앞 원소를 조회, 제거하지는 않고 조회만
• isEmpty() : 큐가 비어있는지 반환
• size() : 큐 사이즈 반환

Overflow/Underflow

특히 배열을 이용한 큐 경우, 스택과 마찬가지로 오버플로우와 언더플로우 발생에 유의해야 한다.

• Overflow : 큐에 데이터를 삽입(enqueue) 시 큐의 저장 용량을 초과한 데이터를 추가하려고 할 때 발생, 따라서 enqueue 전에 확인해야 함
• Underflow : dequeue 시 큐에 데이터가 없는 상황에서 dequeue를 시도할 때 발생, 큐가 비어있는지 확인하고 dequeue 수행

큐 구현

큐 또한 스택과 마찬가지로 리스트를 사용해 구현이 가능하다.

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            raise IndexError("cannot dequeue because of an empty queue")

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            raise IndexError("cannot peek because of an empty queue")

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

내장 라이브러리 사용 - Queue

from queue import Queue

queue = Queue()
queue.put(1)
queue.put(2)
queue.put(3)

queue.get()		# (=dequeue)
queue.queue[0]	# (=peek)
queue.empty()
queue.qsize()

파이썬 collections 모듈의 Queue 라이브러리를 사용함으로써 큐를 간단히 사용할 수 있다. 이 때 enqueue put, dequeue는 get, peek은 queue[0]로 사용할 수 있다.

큐에서 데이터의 삽입과 제거는 각각 정해진 큐의 맨 뒤와 앞에서만 이루어지가 때문에 모두 O(1)의 시간 복잡도를 갖는다. peek, size 연산 또한 마찬가지이다.

스택 vs 큐

구분	스택 (Stack)	큐 (Queue)
삽입	O(1)	O(1)
삭제	O(1)	O(1)
확인	모든 요소 확인에 O(n), 최상단 요소에 O(1)	모든 요소 확인에 O(n), 첫 번째 요소에 O(1)
구조	후입선출(LIFO, Last In First Out)	선입선출(FIFO, First In First Out)
주요 용도	함수 호출과 반환, 역추적(backtracking)	대기열 처리, 작업 스케줄링