파이썬 자료구조와 알고리즘_스택(Stack), 큐(Queue)

스택(stack)은 배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조다. 스택은 배열 인덱스 접근이 제한되며, 후입선출(last in, first out, LIFO) 구조다. 스택의 동작의 시간복잡도는 모두 O(1)이다.

 

스택의 동작

- push: 스택 맨 끝(맨 위)에 항목을 삽입한다.

- pop: 스택 맨 끝 항목을 반환하는 동시에 제거한다.

- top/peak: 스택 맨 끝 항목을 조회한다.

- empty: 스택이 비어 있는지 확인한다.

- size: 스택 크기를 확인한다.

 

파이썬에서는 리스트의 append()와 pop() 메서드로 스택을 구현할 수 있다.

 

 

 

큐(queue)는 스택과 다르게 항목이 들어온 순서대로 접근 가능하다. 즉, 먼저 들어온 데이터가 먼저 나가는 선입선출(first in, first out, FIFO) 구조다. 큐 역시 배열의 인덱스 접근이 제한된다. 큐의 동작의 시간복잡도는 모두 O(1)이다.

 

큐의 동작

- enqueue: 큐 뒤쪽에 항목을 삽입한다.

- dequeue: 큐 앞쪽의 항목을 반환하고, 제거한다.

- peek/front: 큐 앞쪽의 항목을 조회한다.

- empty: 큐가 비어 있는지 확인한다.

- size: 큐의 크기를 확인한다.

 

 

 

 

 

출처: 파이썬 자료구조와 알고리즘, 미아 스타인 지음 최길우 옮김