TIL-43. 스택, 큐, 덱에 대해 알아보자

스택(Stack) - LIFO(Last Input First Out)

데이터를 저장하는 기본적인 구조로 일차원의 선형(linear) 자료구조이다.
값을 저장하는 연산과 꺼내는 연산이 제공되지만 스택의 경우
차곡차곡 들어가고 마지막에 넣은 값부터 꺼내오는 후입선출이 특징이다.

스택 구현 예시

class Stack: 
    def __init__(self): 
        self.items = [] 
    
    def push(self, val): 
        self.items.append(val) 

    def pop(self): 
        try: 
            self.items.pop() 
        
        except IndexError:  
            print("Stack is empty") 
    
    def top(self): 
        try: 
            return self.items[-1] 
        
        except IndexError: 
            print("Stack is empty") 
    
    def __len__(self): 
        return len(self.items) 
        
    def isEmpty(self): 
        return self.__len__() == 0

---

큐(Queue) - FIFO(First Input First Out)

큐는 스택과 동일하게 차례대로 데이터가 저장되지만
데이터를 꺼낼 때는 가장 먼저 넣었던 데이터부터 꺼낸다는 선입선출의 차이점이 있다.

큐 구현 예시

class Queue:
    def __init__(self):
        self.items = []
    def enqueue(self,val):
        self.items.append(val)
    def dequeue(self):
        try:
            return self.items.pop(0)
        except IndexError:
            print("Queue is empty")
    def front(self):
        try:
            return self.items[0]
        except IndexError:
            print("Queue is empty")
    def __len__(self):
        return len(self.items)
    def isEmpty(self):
        return len(self)

원형큐(Circular Queue)

위에서 말한 큐는 일반적인 선형큐인데, 이 선형큐의 문제점을 개선한 것이 바로 원형큐이다.
선형큐는 rear가 배열의 마지막 인덱스를 가리키고 있다면
앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용할 수 없다는 단점이 있었다.

원형큐에서는 포인터 증가 방식이 (rear+1)%arraysize로 변환하므로
배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해진다.

원형큐 동작 과정

• Enqueue
  rear 포인터를 1 증가시키고 그 위치에 데이터를 삽입한다.
  만약 rear+1이 배열의 끝인데 포화 상태가 아니라면 배열의 첫 번째 인덱스에 데이터를 삽입한다.

  • 배열의 포화 상태 여부 판단을 위해 1칸을 비워둔다.(rear+1)%arraysize == front라면
    배열이 포화상태이므로 데이터를 삽입하지 않는다.

• Dequeue
  front의 포인터를 1 증가시키고 그 위치의 데이터를 가져온다.
  rear == front라면 배열이 공백이므로 데이터를 가져오지 못한다.
  

원형큐 구현 예시

from _typeshed import ReadableBuffer


size = 4

class CircularQueue:
    def __init__(self): 
        self.front = 0
        self.rear  = 0
        self.items = [None] * size
    
    def isEmpty(self):
        return self.front == self.rear

    def isFull(self):
        return self.front == (self.rear+1)%size

    def clear(self):
        self.front = self.rear

    def enqueue(self, item): 
        if not self.isFull():
            self.rear = (self.rear+1)%size
            self.items[self.rear] = item

    def dequeue(self):
        if not self.isEmpty():
            self.front = (self.front+1)%size
            return self.items[self.front]

---

덱(Deque) - Stack + Queue

덱은 스택과 큐의 연산을 모두 지원하는 자료구조이다.
양쪽에서 데이터의 삽입/삭제가 가능하다.
파이썬에서는 collections라는 모듈에 deque란 클래스로 구현돼 있다.

덱 구현 예시(파이썬 collections 모듈 사용)