[Python] Queue, Deque 사용하기

📌 Queue

class Queue:
    def __init__(self):
        self.queue = []
 
    def push(self, num):
        self.queue.append(num)
 
    def pop(self):
        return self.queue.pop(0) if len(self.queue) != 0 else -1
 
    def size(self):
        return len(self.queue)
 
    def empty(self):
        return 1 if self.size() == 0 else 0
 
    def front(self):
        return self.queue[0] if self.size() != 0 else -1
 
    def back(self):
        return self.queue[-1] if self.size() != 0 else -1

📌 CircularQueue

class CircularQueue():
    def __init__(self, size):
        self.queue = [0 for x in range(size + 1)]
        self.front = 0
        self.rear = 0
        self.max_size = size
        self.list_size = size + 1
 
    def push(self, num):
        if (self.rear + 1) % self.list_size == self.front:
            return -1
        self.queue[self.rear] = num
        self.rear = (self.rear +1) % self.list_size
 
    def pop(self):
        if self.size() == 0:
            return -1
        temp = self.queue[self.front]
        self.front = (self.front + 1) % self.list_size
        return temp
 
    def size(self):
        if self.front == self.rear:
            return 0
        elif self.rear > self.front:
            return self.rear - self.front
        else:
            return self.max_size - (self.front - self.rear) + 1
 
    def empty(self):
        return 1 if self.front == self.rear else 0
 
    def max(self):
        return max(self.queue)
 
    def print(self):
        print(self.queue)
        print(self.front)
        print(self.rear)

📌 Deque

Double Ended Queue

• 데이터를 저장하는 기본적인 구조로, 일차원의 선형자료구조이다.

Deque으로 구현

 from collections import deque
 queue = deque(["Eric", "John", "Michael"])
 queue.append("Terry")           # Terry arrives
 queue.append("Graham")          # Graham arrives
 queue.popleft()                 # The first to arrive now leaves
'Eric'
 queue.popleft()                 # The second to arrive now leaves
'John'
 queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

📌 Deque objects support the following methods

공식문서

append(x)

Add x to the right side of the deque.

appendleft(x)

Add x to the left side of the deque.

clear()

Remove all elements from the deque leaving it with length 0.

copy()

Create a shallow copy of the deque.

count(x)

Count the number of deque elements equal to x.

extend(iterable)

Extend the right side of the deque by appending elements from the iterable argument.

extendleft(iterable)

Extend the left side of the deque by appending elements from iterable. Note, the series of left appends results in reversing the order of elements in the iterable argument.

index(x[, start[, stop]])

Return the position of x in the deque (at or after index start and before index stop). Returns the first match or raises ValueError if not found.

insert(i, x)

Insert x into the deque at position i.

pop()

Remove and return an element from the right side of the deque. If no elements are present, raises an IndexError.

popleft()

Remove and return an element from the left side of the deque. If no elements are present, raises an IndexError.

remove(value)

Remove the first occurrence of value. If not found, raises a ValueError.

reverse()

Reverse the elements of the deque in-place and then return None.

rotate(n=1)

Rotate the deque n steps to the right. If n is negative, rotate to the left.

When the deque is not empty, rotating one step to the right is equivalent to d.appendleft(d.pop()), and rotating one step to the left is equivalent to d.append(d.popleft()).

maxlen

Maximum size of a deque or None if unbounded.
Deque objects also provide one read-only attribute

📝 예시 - 사용 방법

 from collections import deque
 d = deque('ghi')                 # make a new deque with three items
 for elem in d:                   # iterate over the deque's elements
...     print(elem.upper())
G
H
I

 d.append('j')                    # add a new entry to the right side
 d.appendleft('f')                # add a new entry to the left side
 d                                # show the representation of the deque
deque(['f', 'g', 'h', 'i', 'j'])

 d.pop()                          # return and remove the rightmost item
'j'
 d.popleft()                      # return and remove the leftmost item
'f'
 list(d)                          # list the contents of the deque
['g', 'h', 'i']
 d[0]                             # peek at leftmost item
'g'
 d[-1]                            # peek at rightmost item
'i'

 list(reversed(d))                # list the contents of a deque in reverse
['i', 'h', 'g']
 'h' in d                         # search the deque
True
 d.extend('jkl')                  # add multiple elements at once
 d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
 d.rotate(1)                      # right rotation
 d
deque(['l', 'g', 'h', 'i', 'j', 'k'])
 d.rotate(-1)                     # left rotation
 d
deque(['g', 'h', 'i', 'j', 'k', 'l'])

 deque(reversed(d))               # make a new deque in reverse order
deque(['l', 'k', 'j', 'i', 'h', 'g'])
 d.clear()                        # empty the deque
 d.pop()                          # cannot pop from an empty deque
Traceback (most recent call last):
    File "<pyshell#6>", line 1, in -toplevel-
        d.pop()
IndexError: pop from an empty deque

 d.extendleft('abc')              # extendleft() reverses the input order
 d
deque(['c', 'b', 'a'])

📝 활용 - 라운드 로빈 스케줄러

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    iterators = deque(map(iter, iterables))
    while iterators:
        try:
            while True:
                yield next(iterators[0])
                iterators.rotate(-1)
        except StopIteration:
            # Remove an exhausted iterator.
            iterators.popleft()