[파이썬 자료구조] 큐(Queue) - 개념, 연산, 구현(배열, 연결리스트)

이번에는 '큐'라는 자료구조를 알아보자.

 

큐는 스택과 마찬가지로 자료를 (data element)를 보관할 수 있는 (선형) 구조를 뜻한다.

 

단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고 → 인큐 (enqueue) 연산

꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있다. → 디큐 (dequeue) 연산

즉 선입선출 특징을 가지는 선형 자료구조이다. 이 점에서 스택과 차이점이 있다.

 

1. 연산의 정의

큐의 연산은 스택과 거의 비슷하다.

단지 push 를 enqueue로 pop을 dequeue로 바꾸고 isFull을 추가하였다. 

 

• size() - 현재 큐에 들어 있는 데이터 원소의 수를 구함
• isEmpty() - 현재 큐가 비어 있는지를 판단
• isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단
• enqueue(x) - 데이터 원소 x를 큐에 추가
• dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거 (또한, 반환)
• peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음)

큐가 가득 차면 더이상 데이터를 넣을 수 없다. 따라서 큐의 길이를 기억하고 있는 것이 용이하다.

 

 

2. 배열로 큐 구현

class ArrayQueue:
	def size(self):  # 큐의 크기를 리턴
		return len(self.data)  

	def isEmpty(self): # 큐가 비어있는지 판단
		return self.size()==0

	def enqueue(self,item): # 데이터 원소를 추가
		self.data.append(item)

	def dequeue(self):# 데이터 원소를 삭제 (리턴)
		return self.data.pop(0) 

	def peek(self): # 큐의 맨 앞 원소 반환
		return self.data[0]

이와 같이 간단히 구현할 수 있다. 스택에서와 차이점은 dequeue 부분과 peek부분인데, 큐는 선입선출이기 때문에 큐의 맨 앞의 원소를 가장 먼저 뺀다.

 

배열로 구현 했을 때 알고리즘 복잡도는 다음과 같다.

• size() : O(1)
• isEmpty() : O(1)
• enqueue() : O(1)
• dequeue() : O(n)
• peek() : O(1)

 

 

3. 양방향 연결리스트로 구현한 큐

from dd import * # 더블 링크드리스트를 구현한 코드는 https://polarmin.tistory.com/9 이곳에서 보실 수 있습니다.
class LinkedListQueue:

    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.getLength()


    def isEmpty(self):
        return self.size()==0


    def enqueue(self, item):
        node = Node(item)
        self.data.insertAt(self.size()+1,node)


    def dequeue(self):
        return self.data.popAt(1)


    def peek(self):
        return self.data.getAt(1).data

 

이것도 스택과 꽤 비슷하다. 주의할 점은 popAt(1) 이라는 점. 0이 아니다. 이유는 연결리스트에서 head와 tail 부분에 각각 더미노드를 놓았기 때문에 실제 큐의 시작점은 1부터 이다. 주의!!!!!!!!