큐

선입선출 vs 후입선출?

어떤 데이터를 출력하느냐에 따라서 결졍된다.

• 선입선출(FIFO) : 큐 가장 먼저 들어온 데이터를 출력한다.
• 후입선출(LIFO) : 스택 마지막에 들어온 데이터를 출력한다.

큐

선입선출의 자료구조이다. 따라서 가장 먼저 들어온, 오래 기다린 데이터를 출력한다.

큐의 동작

큐도 스택처럼 접근이 제한된 자료구조이다.

• 인큐 : 요소를 큐에 추가한다. (맨 뒤에)
• 디큐 : 요소를 제거한다. (맨 앞에)

➕ 스택이라면, 맨 앞의 요소를 제거할 것이다.

큐의 종류

• 제한적 큐 : 추가할 수 있는 요소의 수에 제한이 있다. 보통 배열을 사용
• 무제한 큐 : 추가할 수 있는 요소의 수에 제한이 없다. 보통 링크드 리스트를 사용한다.

큐의 성능과 사용

큐는 삽인과 삭제에 항상 O(1)을 따른다.
접근에는 요소 전체에 대한 접근이 필요하기 때문에 O(n)으로 비효율적이다.

큐는 프로그래밍에 유용하다. 순서대로 입출력하는 상황에 이상적이므로 여러 상황에 사용할 수 있다.

큐 구현 : 링크드 리스트

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

class Que:
    def __init__(self):
        self.front = None
        self.rear = None
        self._size = 0

    def enqueue(self,item):
        self._size += 1
        if self.front is None:
            self.front = Node(item)
            return
        if self.rear is None:
            self.rear = Node(item)
            self.front.next = self.rear
            return
        node = Node(item)
        self.rear.next = node
        self.rear = node
        return

    def dequeue(self):
        if self.front is None:
            self._size += -1
            return None
        re = self.front
        self.front = self.front.next
        if self.front is not None:
            self._size += -1
        return re.data
    def size(self):
        return self._size
    def __str__(self):
        re = ""
        current = self.front
        if current is None:
            return re
        while current is not self.rear:
            re += str(current.data) + " "
            current = current.next
        re += str(current.data) + " "
        return re

a = Que()
a.enqueue(4)
a.enqueue(2)
a.enqueue(1)
a.enqueue(3)

print(a)

print(a.dequeue())
print(a.dequeue())
print(a.dequeue())
print(a.dequeue())
print(a.dequeue())

print(a.size())

큐 구현 : 파이썬에 내장된 큐 클래스

from queue import Queue

q = Queue()
q.put(3)
q.put(2)
q.put(1)

print(q.qsize())    #3
print(q.get())
print(q.get())
print(q.get())
print(q.qsize())    #0

큐 구현 : 두개의 스택을 사용해 큐 만들기

큐는 맨 뒤에 있는것만 꺼낼 수 있다..?

내가 짠 코드

class Queue:
    def __init__(self):
        self.s1 =[]
        self.s2 =[]
    def enqueue(self,item):
        self.s1.append(item)
    def dequeue(self):
        if len(self.s1) == 0:
            return None
        while len(self.s1) > 1:
            self.s2.append(self.s1.pop())
        re =  self.s1.pop()
        while len(self.s2) != 0 :
            self.s1.append(self.s2.pop())
        return re

q = Queue()


q.enqueue(4)
q.enqueue(3)
q.enqueue(2)

print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())