[C++] 알튜비튜 2주차 - 스택, 큐, 덱

스택(Stack)

• LIFO(last in first out)
• 자료의 맨 끝 위치에서만 모든 연산이 이루어진다.
• 모든 연산에 대한 시간복잡도는 O(1)
• 연산이 이루어지는 위치 : top, 삽입: push, 삭제: pop

 

std::stack

• push(element): top에 원소 추가
• pop(): top에 있는 원소 삭제
• top(): top에 있는 원소 반환
• empty(): 스택이 비어있는지 확인(비어있으면 true)
• size(): 스택 사이즈 반환

* 파이썬은 ?

• 따로 Stack 자료구조 제공 x. 이미 리스트에 모두 구현돼있다.
• list()
  • stack = list()일 때...
    • stack.append(element): top에 원소 추가
    • stack.pop(): top에 있는 원소를 반환하고 삭제
    • stack[-1]: top에 있는 원소
    • len(stack): 스택 사이즈 반환
    • len(stack)==0: 스택이 비어있는지 확인

 

큐(queue)

• FIFO(First in first out)
• 자료의 왼쪽 끝 위치에서 삭제, 오른쪽 끝 위치에서 삽입연산이 이루어진다.
• 모든 연산에 대한 시간복잡도: O(1)
• 삭제가 이루어지는 위치: front, 삽입이 이루어지는 위치: rear
• 삭제는 dequeue, 삽입은 enqueue

[배열로 크기 3인 큐 구현]

dequeue 연산마다 배열의 모든 원소를 한 칸씩 옮기는 것: 비효율적!

 

std::queue

• push(element): 큐의 뒤에 원소 추가
• pop(): 큐의 앞에 있는 원소 삭제
• front(): 큐의 제일 앞 원소 반환
• back(): 큐의 제일 뒤 원소 반환
• empty(): 큐가 비어있는지 확인(비어있으면 true)
• size(): 큐의 사이즈 반환

덱(Deque)

• Double-Ended Queue
• Stack + Queue
• 자료의 양 끝에서 연산이 이루어진다.
• 모든 연산에 대한 시간 복잡도: O(1)

std::deque

• push_front(element): 덱 앞에 원소 추가
• push_back(element): 덱 뒤에 원소 추가
• pop_front(): 덱 앞에 있는 원소 삭제
• pop_back(): 덱 뒤의 원소 삭제
• front(): 덱의 제일 앞에 있는 원소 반환
• back(): 덱 제일 뒤에 있는 원소 반환
• empty(): 덱이 비어있는지 확인(비어있으면 true)
• size(): 덱 사이즈 반환

* 파이썬은...?

import collections
deq = collections.deque();

이나

from collections import deque
deq = deque()

 

 

collections.deque(파이썬)

• deq=collections.deque() #덱을 정의
• .appendleft(element): 덱의 앞에 원소 추가
• .append(element): 덱의 뒤에 원소 추가
• .popleft(): 덱의 앞에 있는 원소를 반환하고 삭제
• .pop(): 덱의 뒤에 있는 원소를 반환하고 삭제
• deq[0]: 덱의 제일 앞에 있는 원소
• deq[-1]: 덱의 제일 뒤에 있는 원소
• len(deq): 덱의 사이즈 반환
• len(deq)==0: 덱이 비어있는지 확인

queue, Queue가 따로 있지만 이는 스레드 프로그래밍을 위한 것으로 일반적으로 collections.deque보다 느리다. 따라서 collections.deque의 append()와 .popleft()로 큐를 사용해보자.

 

 

정리

• 스택, 큐, 덱 모두 연산에서의 시간 복잡도 : O(1)
• 효율성을 보는 문제에 사용되는 경우가 많다.
• 순회는 벡터보다 불편.
• 무한루프(POP을 하지 않음), 런타임에러(empty 체크 안 하고 조회 or 삭제 시도) 조심!!

+ 재귀함수로 짠 알고리즘은 스택으로 구현할 수 있는 경우 많음.