[자료구조] 2-2. 큐(Queue)

큐(Queue)

큐 자료구조는 우리가 평소에 줄을 서듯, 먼저 들어온 사람이 먼저 나가는, 선입선출(先入先出, First in First out)의 형식을 따른다.

 

 

큐의 연산

큐의 연산은 다음 5가지가 있다:

• isEmpty(): 큐가 비어있는지를 판단한다. True 또는 False값으로 반환된다.
• enqueue(data): 큐에 값을 입력시킨다.
• dequeue(): 큐의 제일 먼저온 값을 내보낸다.
• rear(): 큐의 맨 뒤에 있는 값을 반환한다.
• front(): 큐의 제일 반저온 값을 반환한다(큐에서 pop하지는 않는다)

큐의 구현 -  배열을 이용한 구현(Python)

class queue():    #큐 선언
    def __init__(self):
        self.arr = []
        
    def isEmpty(self):    #큐가 비어있는지 확인
        if self.arr == []:
            return True
        else:
            return False
        
    def enqueue(self, data):    #큐에 data 삽입
        self.arr.append(data)
        
    def dequeue(self):    #큐의 맨 앞 데이터 pop
        if self.isEmpty():
            print("Queue is Empty!")
        else:
            return self.arr.pop(0)
        
    def rear(self):    #큐의 맨 뒤 데이터 반환(pop 하지는 않음)
        if self.isEmpty():
            print("Queue is Empty!")
        else:
            return self.arr[-1]
        
    def front(self):    #큐의 맨 앞 데이터 반환(pop 하지는 않음)
        if self.isEmpty():
            print("Queue is Empty!")
        else:
            return self.arr[0]

q = queue()
print(q.isEmpty())
q.enqueue(3)
q.enqueue(7)
q.enqueue(9)
q.enqueue(1)
q.enqueue(2)
print(q.front())
print(q.isEmpty())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.rear())
print(q.dequeue())

결과

True
3
False
3
3
7
9
1
2
2

큐의 구현 - 연결리스트를 이용한 구현(Python)

새로 추가되는 노드가 tail 뒤에 붙도록 구현하고, 빠지는 노드가 head노드에서 빠지도록 하였다.

class Node():    #노드 선언
    def __init__(self, data, next = None):
        self.data = data
        self.next = next
class queue():    #큐 선언
    def __init__(self):
        self.head = None
        self.tail = None
        
    def isEmpty(self):    #큐가 비어있는지
        if self.head == None and self.tail == None:
            return True
        else:
            return False
 
    def enqueue(self, data): #tail에 추가, 빈 리스트일경우, head에.
        if self.isEmpty():
            self.head = Node(data)
            self.tail = self.head
        else:
            self.tail.next = Node(data)
            self.tail = self.tail.next
            
    def dequeue(self):    #큐 연결 리스트의 head제거
        if self.isEmpty():
            print("Queue is Empty!")
        else:
            data = self.head.data
            headNode = self.head
            self.head = self.head.next
            headNode.next = None
            return data
    
    def front(self):    #큐의 head값 출력
        if self.isEmpty():
            print("Queue is Empty!")
        else:
            return self.head.data
 
    def rear(self):        #큐의 끝값 출력
        if self.isEmpty():
            print("Queue is Empty!")
        else:
            return self.tail.data

실행

q = queue()
print(q.isEmpty())
q.enqueue(3)
q.enqueue(7)
q.enqueue(1)
q.enqueue(8)
q.enqueue(2)
print(q.isEmpty())
print(q.front())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.rear())
print(q.dequeue())

True
False
3
3
7
1
8
2
2

 

큐의 구현 - 파이썬 기본모듈을 이요한 구현

queue 모듈을 가져와서 구현할 수 있다.

put()으로 enqueue(), get()으로 dequeue()를 이용할 수 있다.

import queue
 
q = queue.Queue()
 
q.put(7)
q.put(3)
q.put(1)
q.put(8)
q.put(2)
 
print(q.get())
print(q.get())
print(q.get())
print(q.get())
print(q.get())

큐의 시간복잡도

구분	시간복잡도
탐색	O(n)
접근	O(n)
삽입 (enqueue)	O(1)
제거 (dequeue)	O(1)
rear	리스트의경우 O(1) 연결리스트의 경우 O(n)
front	O(1)