[자료구조] 스택, 큐, 덱

스택(Stack)

데이터가 입력되면 입력되는 순서대로 쌓고, 나중에 들어온 것부터 먼저 사용하는 자료구조입니다. 스택 형태의 데이터 구조를 LIFO(Last-In-First-Out)형이라고 하며, 스택에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'이라고 합니다. 파이썬에서는 리스트를 사용해 스택을 구현할 수 있습니다.

 

초기화하기

 

원소 삽입 : append(x)

 

원소 제거 : pop()

pop()은 마지막 원소를 리턴하고 제거합니다.

 

top 가져오기 

인덱스 -1은 가장 마지막에 삽입된 원소를 가리킵니다.

 

 

큐(Deque)

데이터가 입력되면 입력되는 순서대로 쌓고, 먼저 들어온 것부터 먼저 사용하는 자료구조입니다. 이를 FIFO(First-In-First-Out), 선입선출이라고 합니다. 

 

deque(덱) 객체

deque는 스택과 큐를 합친 자료구조로, 리스트의 양쪽 끝에서 원소를 넣거나 뺄 수 있습니다.

메소드	설명
deque([iterable[, maxlen]])	초기화 함수입니다. iterable(리스트 등)을 인자로 건네면 이를 deque화 해줍니다.
append(x)	x를 덱의 오른쪽에 삽입합니다.
popleft()	덱의 가장 왼쪽에 있는 원소를 덱에서 제거하고 그 값을 리턴합니다.
clear()	모든 원소를 지웁니다.

 

스택과 달리 큐를 list로 이용하지 않는 이유

pop()의 time complexity는 O(1) < pop(0)의 time complexity는 O(N)

-> list를 큐로 사용할 경우 시간이 오래 걸려서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않습니다.

 

초기화하기

 

원소 삽입 : append(x)

 

원소 제거 : popleft()

큐에서 원소를 왼쪽에서부터 제거할 때 사용합니다. 

 

원소 삭제 : clear()

모든 원소를 지웁니다.

 

원소 수 세기 : len()

 

 참고  덱을 사용하는 다른 방법 : Queue 모듈의 Queue 클래스 이용

 

Queue 클래스가 제공하는 메소드와 멤버 변수

구분	이름	역할
메소드	qsize()	들어있는 데이터의 길이를 리턴
메소드	empty()	큐가 비어있는지 검사
메소드	put(item)	item을 큐에 삽입
메소드	get()	큐에서 원소를 제거하고 제거한 원소를 리턴
멤버 변수	queue	현재 큐에 들어있는 데이터

 

초기화하기

 

원소 삽입 : put()

※ Queue에는 원소 N개를 한번에 넣는 방법이 없어 데이터 수만큼 삽입 연산을 호출해야 합니다.

 

원소 추출 : get()

 

원소 수 세기 : qsize()