Linked list, Stack, Queue <3-4>

 

 

<< 3주차 Lecture Note 4번째>>

• Queue

---

Queue

Stack은 데이터의 출입로가 1개였지만, Queue는 2개로 구성되어 데이터가 들어가는 입구와 데이터가 나가는 출구가 나뉘어진다.

즉 첫 번째 노드는 데이터가 들어가는 입구로, 마지막 노드는 데이터가 나가는 출구로 구성되며, 중간 노드는 데이터의 추가/삭제가 안된다.

---

1. Operation of Queue

 

Enqueue

링크드리스트에 데이터를 추가하는 작업을 말한다.

 

Dequeue

링크드리스트에서 데이터를 삭제하는 작업을 말한다.

---

2. Implermentation of Queue

 

큐 구조의 코드를 보면 아래와 같다.

 

class Queue:
    lstInstance = SinglyLinkedList()
    
    def dequeue(self):
        return self.lstInstance.deleteAt(0)
    
    def enqueue(self, value):
        self.lstInstance.insertAt(value, self.lstInstance.getSize())

 

위 코드에서는 링크드리스트의 첫번째 노드가 데이터의 출구, 마지막 노드를 데이터의 입구로 구현했다.

데이터의 출구인 첫 번째 노드는 인덱스가 0으로 고정이지만, 데이터의 입구인 마지막 노드는 리스트의 사이즈에 따라 다르기때문에,

링크드리스트의 사이즈를 가져오는 getSize() 메서드를 이용해 마지막 노드의 인덱스를 확인하고 데이터를 입력하게 된다.

 

위 클래스에 따라 a → b → c  순서로 데이터를 입력하는 경우 리스트의 구성은 아래와 같다.

queue = Queue()

queue.enqueue("a")
queue.lstInstance.printStatus()

queue.enqueue("b")
queue.lstInstance.printStatus()

queue.enqueue("c")
queue.lstInstance.printStatus()

 

\(\quad\) a 

\(\quad\) a b 

\(\quad\) a b c 

dequeue를 하는 경우는 아래와 같다.

queue.lstInstance.printStatus()

queue.dequeue()
queue.lstInstance.printStatus()

queue.dequeue()
queue.lstInstance.printStatus()

queue.dequeue()
queue.lstInstance.printStatus()

 

\(\quad\) a b c 

\(\quad\) b c 

\(\quad\) c