파이썬 큐 Queue 간단 구현!!

 

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
            return
        self.tail.next = new_node
        self.tail = new_node
        
    def dequeue(self):
        if self.is_empty():
            return 'array is empty'
        cur = self.head
        self.head = self.head.next
        return cur.data


    def peek(self):
        if self.is_empty():
            return 'array is empty'
        return self.head.data

    def is_empty(self):
        return self.head is None

stack과 마찬가지로 node사용해서 만들어주려고한다.

 

stack은 프링글스에 비유했는데 queue는 드라이브 스루같은 느낌이다.  맥날, 혹은 스타벅스에 가면 드라이브 스루가 있다. 먼저 들어간 차가 먼저 나오고 차는 뒤에서 부터 들어간다. 이런 개념이 큐이다.

 

먼저 head와 tail을 설정해주고 처음에는 두개가 같은 노드를 참조한다.

 

head     tail

     node1

 

노드를 추가(enqueue)해주면 아래와 같이 tail이 마지막을 계속 따라간다.

 

head         taile

node1 -> node2

 

  head                            taile

node1 -> node2 -> node 3

 

이제 추가말고 데이터를 꺼내보자. (dequeue) 아래와 같은 그림이 그려질 것이다.

 

                     head         taile

node1 -> node2 -> node 3

 

아까 스택과 다른점은 위 큐 아래 스택

new_node = Node(value)
self.tail.next = new_node
self.tail = new_node

new_node = Node(value)
new_node.next = self.head
self.head = new_node

큐는 현재 꼬리의 다음에 새로운 노드를 넣고 꼬리가 그 새로운 노드를 참조하는 반면

스택은 먼저 새로운 노드를 생성한 뒤 next에 현재의 head를 넣고 현재의 head를 새로운 노드로 바꾼다.

 

생각해보니까 큐는 이미 헤드가 있기 때문에head-> -> -> ->tail 이런 방향으로 tail이 생성이 되도 상관이 없지만(헤드라는 기준이 있기 때문에)스택은 <-<-<-<-<-head 이런식으로 기준이 없고 head가 기준이 되기때문에 기존 데이터들을 먼저 next로 옮겨야 한다.