이코테 2021 - 스택과 큐

• 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정.
• 대표적인 그래프 탐색 알고리즘 : DFS/ BFS
• DFS와 BFS 알고리즘 전 알고있어야 할 자료구조 → 스택/ 큐

 

스택(Stack)

 

스택 자료 구조 : 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조

= 선입후출

입구와 출구가 동일한 형태

ex) 여러개의 박스를 쌓을 때

 

> 삽입과 삭제의 명령으로 이루어짐

가장 마지막에 들어온 "7"이 삭제된다.

stack = []

# 삽입(5)- 삽입(2)- 삽입(3)- 삽입(7)- 삭제()- 삽입(1)- 삽입(4)- 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)

stack.pop()

stack.append(1)
stack.append(4)

stack.pop()

print(stack)
# [5, 2, 3, 1]

> 스택 자료구조의 형태는 리스트의 append와 pop 메소드를 사용하면 된다.

> 또한, append함수와 pop함수의 시간 복잡도는 상수시간 즉, O(1)이기 때문에 스택자료구조로 활용하기 적합하다

 

↓ 시간복잡도란?

----

 

 

큐(Queue)

 

큐 자료구조 : 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조

= 선입선출

입구와 출구가 모두 뚫려있는 터널 형태의 자료구조

> 이 역시 삽입과 삭제 명령어로 구현가능

ex) 마트나 편의점의 제품 정렬?

 

삭제 시, 가장 먼저 들어온 데이터가 삭제된다

 

 

> deque 라이브러리는 스택과 큐 자료구조의 장점을 모두 합친 라이브러리이다.

from collections import deque

queue = deque()

# 삽입(5)- 삽입(2)- 삽입(3)- 삽입(7)- 삭제()- 삽입(1)- 삽입(4)- 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)

queue.popleft()

queue.append(1)
queue.append(4)

queue.popleft()

print(queue)
# [3, 7, 1, 4]

> 큐 자료구조의 형태는 deque의 append와 popleft 메소드를 사용하면 된다.

> 리스트 자료형을 이용하여 큐를 구현할 수는 있지만, 시간복잡도가 높아 비효율적으로 동작하게 된다.

( 리스트의 pop메소드를 사용하게 되면, pop메소드 이후 인덱스를 재정렬 해야함으로 시간복잡도가 O(k)가 된다)

 

> 큐 자료구조를 사용할 때는 "deque" 라이브러리를 사용할 것!

> 시간복잡도는 이 역시 상수시간(O(1))이다.

 

 

 

아래 영상을 참고하였습니다