코딩테스트를 대비한 알고리즘 포스팅 해시(Hash)편은 여기 참고 !

🐣 스택/큐란 ?

두번째로 정리할 알고리즘인 스택(Stack), 큐(Queue)는 둘다 막대 형식의 자료구조라고 이해하면 쉽다. 둘다 데이터를 임시 저장할때 주로 사용하는 자료구조로, 데이터를 입력하는 순서는 같지만 데이터를 출력하는 방식이 서로 반대이다.

스택(Stack): LIFO(Last-In-First-Out) 형식의 자료구조
큐(Queue): FIFO(First-In-First-Out) 형식의 자료구조

스택(Stack)

스택은 데이터를 임시 저장할때 사용하는 자료구조로, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조이다. 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다. 후입선출 !
스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조로서, 대표적으로 컴퓨터 내부의 프로세스 구조의 함수 동작 방식에 활용된다.

큐(Queue)

큐 또한 데이터를 임시 저장하는 자료구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다. 선입선출 !
큐는 멀티 태스팅을 위한 프로세스 스케줄링 방식을 구현하기 위해 많이 사용된다.

---

✏️ python에서 스택/큐를 구현하는 방식: list/deque

스택을 사용하면 좋은 경우 !

• 재귀 알고리즘
• DFS 알고리즘
• 작업 실행 취소와 같은 역추적 작업이 필요할 때
• 괄호 검사, 후위 연산법, 문자열 역순 출력 등

큐를 사용하면 좋은 경우 !

• 데이터를 입력된 순서대로 처리해야 할 때
• BFS 알고리즘
• 프로세스 관리
• 대기 순서 관리

스택/큐의 기본연산

1. 탐색
   peek() : 가장 위에 있는 원소를 읽어 반환한다.(삭제X)

2. 삽입
   push(): 원소를 추가한다.

3. 삭제
   pop(): 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.

4. 빈 스택인지 확인
   empty(): 비어있다면 1, 아니면 0을 반환한다.

삽입, 삭제 시 맨 위의 데이터를 삽입 또는 삭제하므로 시간복잡도는 늘 O(1)이다. 하지만 특정 데이터를 찾을 경우 해당 데이터를 찾을 때까지 수행을 해야하므로 O(n)의 시간복잡도를 갖는다.

• 또한 스택이 비어있을 때 stack.pop을 시도할 경우 stack underflow가 발생하고, 스택의 크기가 꽉차있을때 stack.push를 시도할 경우 stack overflow가 발생한다.

list로 스택을 구현하는 방법

파이썬에서는 스택을 list, Linkedlist로 구현한다.

stack = [] # stack 생성
stack.append(1) # stack push
stack.append(2)
stack.append(3)
stack.pop() # stack pop

deque로 큐를 구현하는 방법

파이썬에서는 큐를 deque 패키지를 사용해 구현한다.

from collections import deque

queue = deque([]) # queue 생성
queue.append(1) # queue push
queue.append(2)
queue.append(3)
queue.popleft() # queue pop

파이썬에서 큐를 리스트가 아닌 deque 패키지로 사용하는 이유는 시간복잡도 때문이다. 삽입의 경우 스택, 큐 모두 선입하므로 상관이 없지만, 삭제 pop()의 경우 스택은 맨 끝의 데이터를, 큐는 맨 처음의 데이터를 뱉어내야한다.

큐를 구현할때 deque의 popleft() 대신 list의 pop(i)를 사용하면 0,1,2,3,...n까지 전부 탐색을 해보고 i번째 인덱스의 원소를 뱉어낸다. 따라서 이때 걸리는 시간복잡도는 O(1)이 아니라 O(n)이다. 반면 deque의 popleft()를 사용하면 큐 안에 원소가 몇 개 존재하든 시간복잡도는 O(1)이다.

---

해당 포스팅을 작성하는데 참고한 블로그

• 자료구조-스택,큐,덱
• 알고리즘-자료구조 스택,큐
• 스택-큐 시간복잡도

스택/큐 알고리즘을 활용한 코딩테스트 문제 풀이

• 프로그래머스 Lv1 같은 숫자는 싫어
• 프로그래머스 Lv2 기능개발