[DS] FIFO 큐 (FIFO Queue) ☑️

 

파이썬 내장 리스트로 구현한 큐

class ListQueue:
    def __init__(self):
        self.__queue = []
    def enqueue(self, x):
        self.__queue.append(x)
    def dequeue(self):
        return self.__queue.pop(0)
    def front(self):
        if self.isEmpty():
            return None
        else:
            return self.__queue[0]
    def isEmpty(self):
        return len(self.__queue) == 0
    def dequeueAll(self):
        self.__queue = []
    def printQueue(self):
        print("Queue from front :", end=' ')
        for i in self.__queue:
            print(i, end=' ')
        print()

리스트로 큐를 구현하는 경우
front 인덱스를 클래스의 인스턴스 변수로 선언하여 관리하면 실행 시간을 단축시킬 수 있다!!!

class Queue:
    def __init__(self): 
        self.q = []; self.sz = 0; self.frnt = 0
    def push(self, x): 
        self.q.append(x); self.sz += 1
    def pop(self):
        if self.sz == 0: return -1
        retItem = self.q[self.frnt]
        self.sz -= 1; self.frnt += 1
        return retItem
    def size(self): return self.sz
    def empty(self): return 1 if self.sz == 0 else 0
    def front(self): return -1 if self.sz == 0 else self.q[self.frnt]
    def back(self): return -1 if self.sz == 0 else self.q[-1]
    
import sys
n = int(input()); q = Queue()
for _ in range(n):
    x = list(sys.stdin.readline().split())
    if len(x) == 2: q.push(x[1])
    elif x[0] == "pop": print(q.pop())
    elif x[0] == "size": print(q.size())
    elif x[0] == "empty": print(q.empty())
    elif x[0] == "front": print(q.front())
    elif x[0] == "back": print(q.back())

연결 리스트로 구현한 큐

from CircularLinkedList import *

class LinkedQueue:
    def __init__(self):
        self.__queue = CircularLinkedList()
    def enqueue(self, x):
        self.__queue.append(x)
    def dequeue(self):
        return self.__queue.pop(0)
    def front(self):
        if self.isEmpty():
            return None
        else:
            return self.__queue.get(0)
    def isEmpty(self):
        return self.__queue.isEmpty()
    def dequeueAll(self):
        self.__queue.clear()
    def printQueue(self):
        print("Queue from front :", end=' ')
        for i in self.__queue:
            print(i, end=' ')
        print()

큐 응용

(1) 좌우 동형 문자열 체크

from ListStack import *
from ListQueue import *

def isPailndrome(a):
    s = ListStack(); q = ListQueue()
    if len(a) == 0: return False
    for i in range(len(a)):
        s.push(a[i]); q.enqueue(a[i])
    while s.pop() == q.dequeue():
        if q.isEmpty():
            return True
    return False

print(isPailndrome("aab"))
print(isPailndrome("aabbcbbaa"))
print(isPailndrome(""))
print(isPailndrome("lioninoil"))

 

 

collections.deque 사용하기

from collections import deque

class Queue:
    def __init__(self, list=[]):
        self.queue = deque(list)
    def enqueue(self, element):
        self.queue.appendleft(element)
    def dequeue(self):
        return self.queue.pop()
    
q = Queue()
q.enqueue(2)
q.enqueue(4)
q.enqueue(6)

for _ in range(3): print(q.dequeue())