스택(Stack), 큐(Queue), 덱(Deque)

오늘의 포스팅은 자료구조인 스택, 큐, 덱입니다!! 

특히 차례대로 쌓이는 작업을 어떤 순서대로 처리할지 나타내는 자료구조들 입니다

 

알고리즘 문제를 풀 때 막무가내로 풀다가 시간초과가 나는 경우가 빈번한데요 

특정 상황에서 위 자료구조를 사용하면 시간단축을 확실히 할 수 있습니다!! 

# 스택(Stack) 

- 한쪽에서만 넣고 뺄 수 있음 

LIFO(last-in,first-out) = 후입 선출

책이 점점 쌓임 - 마지막에 쌓은 책을 제일먼저 꺼내는 것 

예) 웹 브라우저 방문이력 확인 / 텍스트 에디터 되돌리기 기능 

 

 

->파이썬에서는 list 자료형으로 구현

stack = [1,2,3] 선언 

 

<스택 연산>   -> 시간복잡도 O(1)

stack.append()    자료 넣기 
stack.pop()          자료 빼기 

-> stack.pop(i) - 특정 인덱스 번호 제거시 시간복잡도 증가(  O(1)-> O(n) ) 

stack[-1]              가장 최근 자료(위에 있는 자료) 확인 
len(stack) == 0    비어있는지 확인  
len(stack)            자료 개수 확인 

 

관련문제

스택 : https://www.acmicpc.net/problem/10828

 

# 큐(Queue), 덱(Deque)

- 큐: 한쪽에서만 자료 넣고 다른쪽에서만 뺄 수 있음

FIFO(first-in, first-out) = 선입 선출
음식점 줄서기 - 먼저 줄선사람 먼저 음식 먹음 
예) 항공권 예약 대기표처리, 인쇄기 작업 스케쥴링 등  

 

- 덱: 양쪽에서 자료 넣고 뺄 수 있음

 

 

 -> 파이썬에서는 queue라는 라이브러리가 존재하지만 collections 라이브러리의 deque 모듈로 모두 구현가능 

from collections import deque 

queue = deque ([1,2,3]) 과 같이 선언

 

<큐, 덱 연산> -> 시간복잡도 O(1)

append( )           원소를 뒤에 추가

appendleft( )      원소를 앞에 추가

pop( )                 마지막 원소 제거

popleft( )            첫번째 원소 제거

 

## 전문성을 살리기 위해 발음 조심하자

Deque -> 덱

dequeue -> 디큐

 

관련문제

요세푸스 문제 : https://www.acmicpc.net/problem/1158