[알고리즘, 자료구조] Queue , Stack

1. Queue

- 선입선출 (FIFO)

- 먼저 저장한 데이터가 먼저 출력

-> enqueue : rear에 데이터가 추가

-> dequeue : front에서 데이터를 꺼냄

<Queue>

1) List 기반 Queue 구현

• enqueue - O(1)
• dequeue - O(n)

2) LinkedList 기반 Queue 구현

• enqueue - O(1)
• dequeue - O(1)

#  list 기반 queue
q = []

# enqueue O(1)
q.append(1)
q.append(2)
q.append(3)

# dequeue O(n)
q.pop(0)
q.pop(0)

#linked List 기반 queue
from collections import deque

# queue 선언
q = deque()

# enqueue O(1)
q.append(1)
q.append(2)
q.append(3)
q.appendleft(0)

# dequeue O(1)
q.popleft()
q.popleft()
q.pop()

---

 

2. Stack

- 후입선출 (LIFO)

- 가장 최근에 추가한 데이터가 가장 먼저 나옴

-> push : 데이터를 추가

-> pop : 데이터를 추출

<Stack>

 

1) List 기반 Stack 구현

• push - O(1)
• pop - O(1)

# stack 선언
s = []

# push O(1)
s.append(1)
s.append(2)
s.append(3)

# pop O(1)
s.pop()
s.pop()