스택과 큐

스택 Stack

LIFO 구조 (Last In First Out)

• push() : 요소를 컬랙션에 추가
• pop() : 아직 제거되지 않은 가장 최근에 삽입한 요소를 제거

Class Node:
	def __init__(self, item, next):
    	self.item = item
        self.next = next

	Clas Stack:
		def __init__(self):
        self.last = None
        
        def push(self, item):
        	self.last = Node(item, self.last)
        
        def pop(self):
        	item = self.last.item
            self.last = self.last.next
            return item
            

큐 Queue

FIFO 구조 (First In First Out)
Deque, Priority Queue(우선순위 큐) 같은 변형 존재

• push(x) : 요소 x를 삽입
• pop() : 큐의 첫 요소를 삭제

원형 큐

기존의 FIFO 구조를 가지나, 마지막 위치가 시작 위치와 연결되는 원형 구조.
기존 Queue는 공간이 꽉 차게 되면 더 이상 요소 추가가 불가능 + 앞 공간이 남아 있어도 그 공간을 매울 수 있는 방법이 없었음

원형 큐는 이 빈 공간들을 재활용 할 수 있음.

- 동작 원리 -> 투 포인터와 비슷함
	
    1. 시작위치와 마지막 위치를 연결하는 원형 구조 만들기
    2. 요소의 시작, 끝 점을 따라 투 포인터가 움직임

def __init__(self, k):
	self.q = [None] * k
    self.maxlen = k
    self.p1 = 0
    self.p2 = 0

def enQueue(self, value):
	if self.q[self.p2] is None:
    	self.q[self.p2] = value
    	self.p2 = (self.p2 + 1) % self.maxlen
   	else:
    	return False

출처 : 파이썬 알고리즘 인터뷰