WEEK02 - TIL 스택/큐

'스택' 자료구조는 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출-먼저 입력되는 데이터가 나중에 출력된다)의 자료구조이다. → 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.

- 대표적 예시: 박스 쌓기

= 여러 개의 박스를 쌓아야할 때(스택하고자 할 때) 아래쪽에서부터 박스를 차례대로 올려놓는다.

쌓아놓은 박스를 다시 내리고자 할 때는 가장 위쪽에 있는 박스부터 차례대로 내리게 된다.

 

스택 자료구조 기억은 박스 쌓기 예시로 기억하면 좋다!!

다양한 알고리즘에서 사용되기에, 스택 자료구조의 동작 방법과 사용 방법에 대해 꼭 알아야 한다!

 

- 스택 자료구조는 삽입과 삭제 두 연산으로 구성된다.

삽입 과정이 차례대로 쌓이다, 삭제 연산을 만나면 가장 마지막에 들어왔던 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[::-1]) #최상단 원소부터 출력
print(stack) #최하단 원소부터 출력

파이썬은 단순히 리스트 자료형을 이용해서 스택처럼 사용할 수 있다.

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

파이썬에서는 별도로 다른 라이브러리를 이용할 필요없이 기본적으로 제공되는 객체인 리스트를 이용하면 된다! 👍

---

'큐' 자료구조는 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다.

→ 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다. (ex. 은행 창구 - 번호표 뽑고 대기열)

즉, 차례대로 먼저 들어온 데이터가 먼저 처리를 받는, 일종의 대기열을 나타내고자 할 때!

 

- 큐 동작 예시

가장 먼저 들어왔던 데이터가 오른쪽에 위치하고, 마지막에 들어온 데이터가 왼쪽에 들어와서 위 그림과 같이 쌓인다.

삭제 진행 시 가장 오른쪽에 있는 데이터(5)부터 삭제를 진행한다.

삽입(1)-(4)를 다시 진행하면 왼쪽으로 쌓이게 되고, 삭제 연산을 진행하면 맨 오른쪽에 있던 데이터(2)가 삭제되어 최종적으로 위 그림과 같은 형태가 된다.

 

 - 큐 구현 예제

# 큐(queue) 구현을 위해 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) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

※ 리스트를 이용해서도 기능적으로 충분히 큐를 구현할 수 있지만, 시간복잡도가 높아서 비효율적으로 동작할 수 있기 때문에, 큐를 이용할 때는 꼭 deque 라이브러리를 사용하는 것을 권장한다!! [관행처럼 쓰이는 거니까 그냥 쓰래~]

 

- deque 라이브러리는 스택과 큐 자료구조의 장점을 모두 합친 형태의 자료구조로 볼 수 있다. 덱 라이브러리에 원소를 삽입할 때 append는 list 때의 append와 동일하게 동작한다고 한다~ == 시간복잡도는 상수

- popleft 메서드 또한 시간복잡도가 O(1)이다.

 

 

 

ㄲ읏~~🤸‍♀️