[자료구조]Queue

Queue

Stack과 반대의 개념 FIFO(First In First Out) 먼저 push된게 먼저 pop이 됩니다

Queue의 종류

• queue
• double ended queue
• priority queue\

class Queue:
    def __init__(self):
        self._queue = []

    def push(self, data):
        return self._queue.append(data)

    def pop(self):
        if len(self._queue) == 0: return None
		
        data = self._queue[0]
        del self._queue[0]
        return data

    def peek(self):
        if len(self._queue) == 0: return None

        return self._queue[0]

queue = Queue()
queue.push(1)
queue.push(2)
queue.push(3)
queue.push(4)

In [28]: print(queue.pop())
1

In [29]: print(queue.pop())
2

In [30]: print(queue.pop())
3

In [31]: print(queue.pop())
4

In [32]: print(queue.pop())
None

Double Ended Qeue(Deque)

일반적으로 Deque라고 불립니다.

양끝에서 pop과 push를 할 수 있는 자료구조입니다.

Queue + Stack이라고 생각하면 편합니다.

class DoubleEndedQueue:
    def __init__(self):
        self._queue = []

    def __repr__(self):
        return f"Queue : {self._queue}"

    def insert(self, data):
        return self._queue.insert(0, data)

    def append(self, data):
        return self._queue.append(data)

    def pop_front(self):
        return self._remove_element(index = 0)

    def pop_tail(self):
        return self._remove_element(index = -1)

    def _remove_element(self, index):
        if len(self._queue) == 0: return None

        data = self._queue[index]
        del self._queue[index]

        return data

deque = DoubleEndedQueue()
deque.append(1)
deque.insert(2)
deque.append(3)
deque.insert(4)

In [121]: print(deque)
Queue : [4, 2, 1, 3]

In [122]: deque.pop_front()
Out[122]: 4

In [123]: print(deque)
Queue : [2, 1, 3]

In [124]: deque.pop_tail()
Out[124]: 3

In [125]: print(deque)
Queue : [2, 1]

그렇다면! Queue는 언제 사용해야할까!?

Queue는 FIFO이기 때문에 일반적으로 Waiting 시스템이나 스케쥴링 시스템등 순서대로 처리가 필요한 경우에 자주 사용됩니다.

• 맛집 예약 시스템
• OS 프로세스 스케쥴링 시스템(Priority Queue)
• 최근 방문한 사이트 주소 기록(Dequeue)
• 문서 작성 툴에서 undo 기록(Dequeue)