[Algorithm / DRALG_lec05] 순서가 있는 자료구조 - 스택과 큐

◠‿◠

---

1. 스택 (stack)

데이터 원소가 차례대로 쌓아 올려진 구조로, 가장 마지막에 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조이다.

(1) LIFO(Last In, First Out), 후입선출 구조

▲ cau_dralg_lec05 / 3p

(2) 스택(stack)의 추상자료형(ADT)

멤버함수 (member function)	반환 (return)	설명 (explanation)
stack.push(data)	None	데이터를 스택의 맨 위에 추가한다.
stack.pop()	data	스택의 가장 위에 있는 데이터를 반환하고 삭제한다.
stack.peek()	data	스택의 가장 위에 있는 데이터를 반환한다.
stack.empty()	bool	스택이 비어있으면 True(1), 아니면 False(0)를 반환한다.

(3) 스택(stack) 구현하기

기본 클래스인 list를 통해 구현 가능하다.

① 리스트 선언

a_list = []

② 내장함수 활용하기

a_list = []

a_list.append(1)	# 1 추가 : 1
a_list.appene(2)	# 2 추가 : 1 2

a_list.pop()	# 맨 위에 있는 요소 삭제 : 2

print(a_list[-1])	# 맨 위에 있는 요소 print >> 1

print(len(a_list))	# 리스트 길이 print >> 1

(4) 스택의 응용

Undo / Redo를 구현할 수 있다.

▲ cau_dralg_lec05 / 5p

 

---

2. 큐 (queue)

데이터 원소가 차례대로 들어오고, 들어온 순서대로 나가는 구조로, 가장 처음에 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조이다.

(1) FIFO(First In, First Out), 선입선출 구조

▲ cau_dralg_lec05 / 10p

(2) 큐(queue)의 추상자료형(ADT)

멤버함수 (member function)	반환 (return)	설명 (explanation)
queue.enqueue(data)	None	데이터를 큐의 맨 위에 추가한다.
queue.dequeue()	data	큐의 가장 앞에 있는 데이터를 반환하고 삭제한다.
queue.peek()	data	큐의 가장 앞에 있는 데이터를 반환한다.
queue.empty()	bool	큐이 비어있으면 True(1), 아니면 False(0)를 반환한다.

(3) 큐(queue) 구현하기

기본 클래스인 list를 통해 구현 가능하다.

① 리스트 선언

b_list = []

② 내장함수 활용하기

b_list = []

b_list.append(1)	# 1 추가 : 1
b_list.insert(0, 2)	# 2 추가 : 1 2

b_list.pop(0)	# 맨 앞에 있는 요소 삭제 : 1

print(b_list[0])	# 맨 위에 있는 요소 print >> 2

print(len(b_list))	# 리스트 길이 print >> 1

(4) 큐(queue) 모듈 활용

from queue import Queue

c_list = Queue()	# queue 선언

c_list.put(1)	# push 기능 : 1
c_list.put(2)	# push 기능 : 1 2
c_list.put(3)	# push 기능 : 1 2 3

c_list.get()	>>> 1
c_list.get()	>>> 2
c_list.get()	>>> 3

---

3. 덱 (deque)

기본 list를 활용하여 충분히 구현 가능하지만, 성능 측면에서 추천하지 않는다. 파이썬의 list는 다른 언어의 배열처럼 무작위 접근(random access)에 최적화된 자료 구조이기 때문이다. 

list의 내장함수의 시간 복잡도는 O(n)이기 때문에 담고 있는 데이터의 개수가 많아질수록 느려진다. 첫 번째 데이터를 제거한 후에는 그 뒤에 있는 모든 데이터를 앞으로 한 칸씩 당겨줘야 하고, 맨 앞에 데이터를 삽입하려면 그 뒤에 있는 모든 데이터를 뒤로 한 칸씩 밀어줘야 하기 때문이다.

deque는 double-ended queue의 약자로 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형이다. 스택(stack)처럼 써도 되고 큐(queue)처럼 써도 된다. collections.deque 모듈은 deque 자료형을 생성하는 모듈이다.