👉 큐(Queue)

스택과 같이 프로그래밍이라는 개념이 탄생할 때부터 사용된 가장 고전적인 자료구조이다.

FIFO(First-In-First-Out, 선입선출)

https://www.programiz.com/dsa/queue

파이썬에서 스택과 마찬가지로 리스트가 큐의 모든 연산을 지원한다. 다만 리스트는 동적배열로 구성되어 있어 큐의 연산을 수행하는데 효율적이지 않다.
( Array에서 pop(0)은 O(n)의 시간복잡도를 가진다.)

따라서 데크(Deque)라는 별도의 자료형을 사용해야 좋은 효율을가진다.

🤚 데큐(Deque)란?
Deque는 double-ended queue의 줄임말로, 앞과 뒤 즉 양방향에서 데이터를 처리할 수 있는 자료구조를 만한다.
스택과 큐의 기능을 모두 가졌다.

• 뒤(오른쪽) 데이터 추가 및 삭제
  추가: append()
  삭제: pop()
  (O(1)의 시간복잡도를 가지며, 스택과 동일하다.)
  
  
• 앞(왼쪽) 데이터 추가 및 삭제
  추가: appendleft()
  삭제: popleft()
  (O(1)의 시간복잡도를 가지며, 위에서 언급 했듯이 Array보다 더 효율적인 연산처리를 한다.)
  

참조)https://jungeun960.tistory.com/148

✍️ 리스트를 이용한 구현

class QueueByArray:
	def __init__(self):
    	self.queue = []
    
    # 추가
    def push(self, value):
    	self.queue.append(value)
    
	# 삭제
    def pop(self):
    	# 큐 안에 데이터가 없을 때의 예외처리
    	if not self.queue:
        	return None
            
    	# O(n)의 시간복잡도를 가진다.
    	return self.queue.pop(0)
    
	# 조회
    def peek(self):
    	return self.queue[0]
   	
    def is_empty(self):
    	if len(self.queue) == 0:
        	return True
        return False

✍️ 데크(Deque)를 이용한 구현

class QueueByArray:
	def __init__(self):
    	self.queue = collections.deque()
    
    # 추가
    def push(self, value):
    	self.queue.push(value)
    
	# 삭제
    def pop(self):
    	# 큐 안에 데이터가 없을 때의 예외처리
    	if not self.queue:
        	return None
            
    	# O(1)의 시간복잡도를 가진다.
    	return self.queue.popleft()
    
	# 조회
    def peek(self):
    	return self.queue[0]
   	
    def is_empty(self):
    	if len(self.queue) == 0:
        	return True
        return False

✍️ 연결리스트를 이용한 구현

class Node:
	def __init__(self, item, next):
    	self.item = item
        self.next = next
    
class QueueByLikedList:
	def __init__(self):
    	# front 초기화
    	self.front = None
    
    # 추가    
    def push(self, value):
    	if not self.front:
        	self.front = Node(value, None)
            return
        
        node = self.front
        while node.next:
        	node = node.next
    	node.next = Node(value, None)
	
    # 삭제
    def pop(self):
    	# 데이터가 없을 때 예외처리
    	if self.front is None:
        	return None
        
        node = self.front
        self.front = self.front.next
        return node.item
    
    # 큐 비었는지 확인
    def is_empty(self):
       if not self.front:
           return True
       return False      

---

참조)
파이썬 알고리즘 인터뷰