CS

[자료구조] Stack & Queue

말하는 알감자 2024. 1. 12. 01:17

자료구조(Data Structure)란 데이터를 표현하고, 관리하고 처리하기 위한 구조를 의미한다.

그중 스택과 큐는 자료 구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다.

- 삽입(Push) : 데이터를 삽입한다.
- 삭제(Pop) : 데이터를 삭제한다.
- 오버플로(overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생
- 언더플로(underflow) : 특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행하면, 데이터가 전혀 없는 상태이므로 언더플로 발생

스택 (Stack)

stack은 박스 쌓기에 비유할 수 있다.

박스는 아래에서 부터 위로 차곡 차곡 쌓아 올린다.

그리고 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야 한다.

이러한 구조를 선입후출 (First In Last Out - FILO) 구조 또는 후입선출 (Last In First Out - LIFO) 라고 한다.

아래 그림을 보면, 삽입 시 미리 들어가 있는 값들의 맨위로 들어가고, 삭제 시 맨 마지막으로 넣은 값을 삭제한다.

이렇게 동작하기 때문에 FIFO 구조라고 한다.

예시와 그림을 통해 더 자세하게 알아보도록 하겠다.

- 예시

ex) 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()

  1. 초기 단계
  2. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  3. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  4. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  5. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  6. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  7. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  8. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  9. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  10. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()

- 코드 : stack.py

stack = []

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

print(stack) # 최하단 원소부터 출력
print(stack[::-1] # 최상단 원소부터 출력

+) 참고

파이썬에서 스택을 이용할 때는 별도의 라이브러리를 사용할 필요가 없다.

기본 리스트에서 append(), pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.

append() 메서드는 리스틑의 가장 뒤쪽에 데이터를 삽입하고, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼내기 때문이다.

큐 (Queue)

queue는 대기 줄에 비유할 수 있다.

은행에 업무를 위해 줄을 설 때, 먼저 온 사람이 먼저 업무를 처리할 수 있다. (물론 새치기는 없다고 가정한다.)

나중에 온 사람일수록 나중에 들어가기 때문에 흔히 '공정한' 자료 구조라고 비유된다.

이러한 구조를 선입선출(First In First Out - FIFO) 구조라고 한다.

예시와 그림을 통해 더 자세하게 알아보도록 하겠다.

- 예시

ex) 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()

  1. 초기 단계
  2. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  3. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  4. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  5. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  6. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  7. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  8. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  9. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()
  10. 삽입(3) - 삽입(5) - 삭제() - 삽입 (7) - 삽입(1) - 삭제() - 삭제() - 삽입(4) - 삭제()

- 코드 : queue.py

from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

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

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

+) 참고

파이썬으로 queue를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자.

deque는 스택과 큐의 장점을 모두 채택한 것으로, 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며, queue라이브러리를 이용하는 것보다 간편하다.

더불어 대부분의 코딩 테스트에서는 collections 모듈과 같은 기본 라이브러리 사용을 허하므로 안심하고 사용해도 괜찮다.

저작자표시 (새창열림)