스택 & 큐

  • Stack & Queue는 데이터를 임시 저장 하기 위해서 사용하는 자료구조
  • 데이터를 입력하고 출력하는 방향이 정해져 있다.

기본 개념

Stack

  • 선입선출 (FILO = First In Last Out)
  • Python에서 스택을 구현할 땐 별도의 라이브러리 없이 리스트 자료형을 사용한다.
  • 삽입 : append()
  • 삭제 : pop()

개념 예제 코드

#Python에서 스택을 구현할 땐 리스트 자료형 사용하여 구현한다.

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)

stack.pop()

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

stack.pop()

## 결과 예상해볼 것

print(stack)
print(stack[::-1])
print(stack[-1])
Stack 결과
[5, 2, 3, 1] [1, 3, 2, 5] 1

Queue

  • 선입선출(FIFO = First In First Out)
  • Python에서 Queue를 구현할 때 사용하는 방법은 3가지가 있다.
    1. 리스트
    2. Queue 사용
    3. dequeue 클래스 사용

사용방법

  1. 리스트
    • 데이터를 넣는 enqueue를 append()
    • 데이터를 뺴는 dequeue를 pop()
    • 리스트에서 pop()은 O(n)의 시간복잡도를 가지기 때문에 큐를 구현할 땐 더 효율적인 방법을 사용한다.
  2. Queue 사용
    • queue모듈의 Queue는 데이터를 단방향에서 추가하고 제거할 수 있는 자료구조이다.
    • 데이터를 넣는 enqueue를 put()
    • 데이터를 빼는 dequeue를 get()
    • Queue 사용에서 get()은 O(1)의 시간복잡도를 가지기에 효율성이 좋다. ([시간복잡도] 리스트 < Queue 사용)
  3. deque 클래스 사용
    • double - ended queue
    • collections 모듈의 deque는 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조이다.
    • 양방향이기에 append(), pop() 뿐만 아니라 appendleft(), popleft() 가능 하고 각각 맨 앞에 데이터를 삽입하거나 맨 앞에서 제거가 가능하다.
    • appendleft(), popleft()는 각각 O(1)의 시간복잡도를 가지기에 효율성이 좋다.([시간복잡도] 리스트 <= Queue사용, deque 클래스 사용)

개념 예제 코드

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)

queue.popleft()

queue.pop()

queue.appendleft(10)

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

queue.popleft()

## 결과 예상해볼 것

print(queue)
Queue 결과
deque ([2, 3, 1, 4])

활용 예시

Stack

  1. 웹 브라우저 방문기록 (뒤로가기)
  2. 역순 문자열 만들기
  3. 후위 표기법 계싼
  4. 괄호 검사

Queue

  1. 우선순위가 같은 작업 예약
  2. 은행업무
  3. 콜센터 고객 대기시간
  4. 프로세스 관리
  5. 너비 우선 탐색(BFS) 구현
  6. 캐시(Cache) 구현

0개의 댓글

Powered by GraphCDN, the GraphQL CDN