[자료구조 공부기록] 4. Queue + Python 구현

 

Queue의 개념도,  생김새는 배열이나 리스트와 크게 다를바 없습니다.

 특징

• 선형구조를 가진 자료구조입니다.
• FIFO(First In First Out/먼저 들어온 원소가 가장 먼저 나감) 구조를 가지고 있습니다.
• 오래된 데이터가 있는 곳이 앞(front), 새로운 데이터가 쌓인 곳이 뒤(back)입니다.

장점 및 단점

 

1) 장점

• 데이터의 삽입, 삭제가 빠릅니다.

 

2) 단점

• 중간에 있는 데이터에 접근이 불편합니다.
• 배열로 구현할 경우 삽입, 삭제 시 데이터를 모두 옮겨주어야 합니다.

---

Queue의 데이터 삽입과 삭제 과정

 

큐의 데이터 삽입은 Enqueue, 삭제(데이터를 내보냄)는 Dequeue라고 합니다. 

 

큐에는 구현 방식에 따라서 몇 가지 분류가 있습니다. 

 

일반적으로 

 

• 선형 큐 : 일반적인 큐이지만 데이터 Enqueue, Dequeue 할 때 데이터를 옮겨줘야 합니다.

 

Circular Queue

• 원형 큐(Circular Queue) : 원형으로 생긴 큐로 위 그림처럼 front의 위치가 바뀌면 그 자리에 다시 Enqueue 할 수 있는 그런 형식의 큐입니다.

정상적인 큐라면 Python 부터 나갑니다. 하지만 우선순위 큐라면?

• 우선순위 큐(Priority Queue) : 위에 봤던 정상적인 큐라면 Python부터 나갑니다 하지만 우선순위 큐이고 JAVA의 순위가 Python이나 C보다 높다면 Dequeue 될 때 JAVA가 먼저 나오게 되는 형태의 큐입니다.
• 연결 리스트 큐(linked list Queue) : 말그대로 linked list를 사용하여 구현된 큐입니다.

---

# 데이터 저장 노드 정의
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
# Queue 클래스 정의
class Queue:
    def __init__(self):

        temp_node = Node(None)

        self.head = temp_node
        self.tail = temp_node
        self.head.next = self.tail
    
    # Enqueue func
    def Enqueue(self, data):
        
        input_node = Node(data)
        
        self.tail.next = input_node
        self.tail = input_node
        
    # Dequeue func
    def Dequeue(self):
        
        if self.head.next is not None:
            self.head = self.head.next
            return self.head.data        
        else:
            return -1


a = Queue()

for i in range(8):
    a.Enqueue(i)

for i in range(9):
    print(a.Dequeue(i))

 

사실 연결 리스트 및 스택 구현하고 크게 다른 점은 없습니다.  

 

다른 기능을 더 넣을까 싶다가 귀찮아서 말았습니다.