[자료구조] 스택과 큐

스택과 큐는 추상적 자료구조로 특정한 규칙을 가지고 있는 배열이라면 스택과 큐가 될 수 있다.

스택 (Stack)

스택은 배열이 수직으로 쌓여있는 구조를 생각하면 쉽다.

위로 쌓여있는 구조이므로 아이템을 추가하거나 삭제할 때 맨 위에서부터 차례대로 처리할 수 있다.

이렇게 마지막 아이템부터 처리하는 구조를 LIFO(Last In, First Out) 이라고 부른다.

마지막으로 추가한 아이템이 가장 먼저 나올 수 있다.

파이썬으로 스택 구조를 구현하면 다음과 같다.

class Stack:
    
    def __init__(self):
        self.arr =[]
    
    def pop(self):
        if self.size() == 0:
            return -1
        else:
            n = self.top()
            self.arr = self.arr[:-1]
            return n

    def push(self, n):
        self.arr.append(n)
    
    def size(self):
        return len(self.arr)
    
    def empty(self):
        return int(len(self.arr) == 0)
    
    def top(self):
        if self.size() > 0:
            return self.arr[-1]
        else:
            return -1

큐 (Queue)

큐는 스택과 반대로 생각하면 된다. 큐는 가장 먼저 입장한 아이템이 가장 먼저 큐에서 나가는 배열을 말한다.

즉, FIFO (First In, First Out) 구조이다.

파이썬으로 큐 구조를 구현하면 다음과 같다.

class Queue:
    def __init__(self):
        self.que = []
    
    def push(self, x):
        self.que.append(x)

    def pop(self):
        if self.size() == 0:
            return -1
        else:
            item = self.que[0]
            self.que = self.que[1:]
            return item
        
    def size(self):
        return len(self.que)
    
    def empty(self):
        return int(len(self.que) == 0)
    
    def front(self):
        if self.size() == 0:
            return -1
        else:
            return self.que[0]

    def back(self):
        if self.size() == 0:
            return -1
        else:
            return self.que[-1]

Deque

파이썬에서는 Collections 패키지의 deque를 이용하면 쉽게 스택과 큐 구조를 사용할 수 있다.

deque는 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형으로, 스택(stack)처럼 써도 되고 큐(queue)처럼 써도 된다.

스택 구조인 리스트와 유사하며, 큐의 기능까지 가지고 있다.

• appendleft(x): 데크 왼쪽에 x 추가
• popleft(): 데크 왼쪽에서 요소를 제거

from collections import deque # stack + que 

deq = deque(i for i in range(1, 10))
print(deq)
print(deq.pop()) # 리스트의 pop()과 동일 
print(deq.popleft()) # 첫번째 아이템 추출 : list의 pop(0)
deq.append('push')
print(deq)
deq.appendleft('push : queue')
print(deq)

deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
9
1
deque([2, 3, 4, 5, 6, 7, 8, 'push'])
deque(['push : queue', 2, 3, 4, 5, 6, 7, 8, 'push'])

deque는 list보다 속도가 빠르다. pop(0)와 같은 메서드를 수행할 때 리스트라면 O(N) 연산을 수행하지만, deque는 O(1) 연산을 수행한다.

정리

정리하면 스택은 새로운 아이템이 다른 아이템위에 차곡차곡 쌓이는 배열이라 위에 아이템을 처리할 때까지 아래아이템들을 처리할 수 없다. 큐는 아이템들이 맨뒤에 추가되고 앞의 아이템들이 처리되기 전까지 뒤의 아이템들은 처리될 수 없다.

스택과 큐는 일상생활에서 많이 접할 수 있는 구조이다. 웹서핑을할 때 뒤로 가기를 누르면 이전 페이지가 나타나고 영화관에서 팝콘을 먹을 때 맨 위에 있는 팝콘부터 먹는 행동도 스택 구조 라고 말할 수 있다. 또한, 버스를 기다리며 줄을 선 순서대로 입장하는 우리의 모습은 큐 구조 로 설명할 수 있다.

스택과 큐는 단순한 구조지만 각 구조의 차이점에 대한 명확히 인식하고 적절한 상황에 적용할 수 있어야 한다. 파이썬에서는 deque 를 이용해 스택 + 큐 구조를 구현 가능하다!

---

Reference

• Stack Gif : Stack
• Queue Gif Queues
• 알고리즘 & 데이터 구조 : 노마드 코더 Nomad Coders