프로그래머스 자료구조 강의와 각종 인터넷 자료를 참고하여 재구성한 내용입니다.

Queue

  • 컴퓨터의 기본적인 자료구조 중 하나

  • 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조

  • LIFO의 구조를 가지는 스택과 정반대

큐의 추상적 자료구조 구현

  • array를 이용하여 구현

    • python list와 method 이용

  • linked list를 이용하여 구현

    • 양방향 연결리스트 이용

큐의 동작

  • 초기 상태: empty queue

  • 데이터 원소 A를 큐에 추가

  • 데이터 원소 B를 큐에 추가

  • 데이터 원소 꺼내기


Q = Queue()

Q.enqueue(A)

Q.enqueue(B)

r1 = Q.dequeue()

r2 = Q.dequeue()

구현(1) - Array

class ArrayQueue:

	def __init__(self):
    	self.data = []

	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()의 경우 시간복잡도는 O(N)이다.

    • enqueue는 리스트의 맨 끝에서만 일어나지만 dequeue는 두번째 원소~마지막 원소를 모두 한 칸씩 앞당겨야하기 때문이다.

구현(2) - Doubly Linked List

class Node:

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

class LinkedListQueue:

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

	def isEmpty(self):
    	if not self.head:
        	return True
        return False

    def enqueue(self, data):
    	if self.tail == None:
        	self.head = Node(data)
            self.tail = self.head
        else:
        	self.tail.next = Node(data)
            self.tail.next.prev = self.tail
            self.tail = self.tail.next

    def dequeue(self):
    	if self.head == None:
        	return None
        else:
        	temp = self.head.data
            self.head = self.head.next
            self.head.prev = None
            return temp

    def peek(self):
    	return self.head.data

    def size(self):
    	temp = self.head
        cnt = 0
        while temp != None:
        	cnt += 1
            temp = temp.next
        return cnt

참조