Stack, Queue, Deque

들어가며

이번 글은 간단히 세가지 자료구조에 대해서 그 개념과 파이썬으로 구현시의 코드를 알아본다.

Stack

쌓다라는 의미를 가지고 있는 stack은 말 그대로 쌓아 올리는 것이다. 가장 아래를 base, 가장 위를 Top이라고 하며 실생활에서도 편의점의 제품 진열장(가장 바깥에 놓인 제품을 고객이 가장 먼저 집게됨)과 같이 어렵지 않게 찾아볼 수 있다.
출처 : 위키피디아

Stack의 핵심을 한 문장으로 나타내보면

First-In-Last-Out, FILO 이다. 가장 먼저 stack에 진입한 것은 가장 base에 쌓이게 되고, 그 이후로 위로 차곡차곡 쌓여 결국 가장 마지막에 쌓인 것이 Top이 되고, 이 Top부터 나가게 된다.

프로그래밍에 있어서는 event call stack과 같이 활용된다. depth가 존재하는 function의 경우 가장 바깥에 있는 함수가 base에 깔리고 가장 깊숙한 곳에서 실행되는 함수가 Top이 된다.

Stack을 Python Class로 나타내보자.

구현해야할 사항은 다음과 같다.
1. Stack()을 만들면 빈 스택이 하나 할당된다.
2. push(item) : 아이템을 넣기.
3. pop() : top에 있는 아이템을 빼기.
4. peek() : top에 있는 아이템을 return.
5. isEmpty() : stack이 비어있는지 확인.
6. size() : stack의 size를 return.

코드를 작성해보자

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

    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[-1]
            
    def isEmpty(self):
        return self.items == []
    
    def size(self):
        return len(self.items)       

직접 작성해서 아래와 같은 활용을 직접 해보자

s = Stack()
s.push(3)
s.pop()
...
...

Stack은 FILO이라는 것을 꼭 기억하고 넘어가자

Queue

Queue는 순서가 있는 item 집단이라고 생각하면 된다. 일반적으로 어딘가에 가서 줄을 선다고 생각하면 된다. 식당 대기줄을 선다고 하면 당연히 먼저 온 사람이 먼저 들어가고, 늦게 온 사람이 나중에 들어가야 하는 것이다. 그게 Queue에서 가장 중요한 핵심 개념이다
출처: 나무위키

가장 앞쪽을 Front라고 하고 뒷쪽을 Rear(back)이라고 한다. 앞서 말했던 줄서는 것과 같이 Front에서는 Dequeue(출력)이 일어나고, Rear에서는 Enqueue(입력)이 일어난다.

Queue의 핵심, First-In-First-Out, FIFO를 기억하자.

Queue을 Python Class로 나타내보자.

구현해야 할 사항은 다음과 같다.
1. Queue()를 만들면 빈 queue가 하나 할당된다.
2. Enqueue() : queue에 넣기
3. Dequeue() : queue에서 빼기
5. isEmpty()
6. size()

class Queue(object):
    
    def __init__(self):
        self.items = []
    
    def enqueue(self, item):
        self.items.insert(0, item)
        
    def dequeue(self):
        return self.items.pop()
    
    def isEmpty(self):
        return self.items == []
    
    def size(self):
        return len(self.items)
#이 Queue는 index가 빠른 쪽이 Rear라고 가정하고 적었다.

• 위 코드에 stack에 있던 peek과 같은 코드는 당연히 추가 될 수 있다.

stack 과 비슷하게 위 코드를 통해 Queue를 만들어 이리저리 사용해보는 걸 추천한다.

Deque(Double-ended-queue)

마지막으로 Deque이다. 나는 처음에는 디큐라고 읽는 것인 줄 알았으나 덱이라고 읽는 그러한 자료구조이다. FIFO인 queue 구조가 양쪽으로 구현되어 있어, 앞과 뒤에서 모두 추가와 삭제가 가능한 그런 구조라고 생각하면 된다.
출처 : https://www.programiz.com/dsa/deque

바로 코드로 넘어가겠다.

Deque를 Python Class로 나타내보자.

구현해야할 사항은 다음과 같다.
1. Deque()를 만들면 빈 queue가 하나 할당된다.
2. addFront() : queue의 앞에다 넣기.
3. addRear() : queue의 뒤에다 넣기.
4. removeFront() : queue의 앞에서 빼기.
5. removeRear() : queue의 뒤에서 빼기.
6. isEmpty()
7. size()

class Deque(object):
    
    def __init__(self):
        self.items = []
        
    def addFront(self, item):
        self.items.append(item)
    
    def addRear(self, item):
        self.items.insert(0, item)
        
    def removeFront(self):
        return self.items.pop()
    
    def removeRear(self):
        return self.items.pop(0)
        
    def isEmpty(self):
        return self.items == []
    
    def size(self):
        return len(self.items)

Deque를 간단하게 이용하면 다음과 같은 것이 가능하다.

d = Deque()
d.addFront('world')
d.addRear(3)
d.addRear('Hello')
print(d.removeRear() + " " + d.removeFront())

Hello world

마치며

이 글은 자료구조의 아주 기본이 되며 꽤나 간단한 Stack, Queue, Deque에 대해 알아보았다. 그다지 복잡하지 않으니 한 두번 코드를 적어보며 익혀보면 좋을것이다.