Stack & Queue & Deque

생성일

2023/03/05 07:34

태그

자료구조

Stack & Queue & Deque

스택과 큐는 자료구조에서 가장 기본이 되는 추상자료형(Abstract Data Type, ADT)이다.

추상자료형(ADT)은 구현 방법을 명시하지 않고, 자료구조의 특성과 연산을 명시한 것이다.

스택 (Stack)

•

스택이라는 이름은 쌓아올린다는 의미를 가지고 있다. 그래서 스택은 쌓아올린 형태의 자료구조를 의미한다.

•

스택은 한 쪽 방향에만 자료를 추가 및 삭제할 수 있으며, 가장 마지막에 삽입된 자료의 위치를 top 이라 한다.

•

스택은 top 에만 접근이 가능하기 때문에, 그 외의 위치에 대한 데이터 추가 및 삭제가 불가능하다.

•

LIFO (Last-In-First-Out, 후입선출) 방식으로 동작한다.

ADT Stack의 연산

push(item) : 스택에 item을 삽입한다 (만약 size를 초과한다면, false를 반환할 수 있다) O(1)

pop() : 스택의 top에 위치한 item을 반환하면서 동시에 제거한다 (반환하지 않을 수 있다) O(1) 

peek() : 스택의 top에 위치한 item을 삭제없이 반환한다 O(1)

ifFull() : 스택이 가득 차있다면 treu, 아니라면 false를 반환한다 O(1) 

isEmpty() : 스택에 item이 없다면 true, 아니라면 false를 반환한다. O(1)

스택의 장단점

top 위치의 데이터에 바로 접근하므로 데이터 삽입, 삭제의 시간복잡도가 O(1) 로 빠르다.

top 이외의 데이터에 접근할 수 없으므로, 탐색이 불가능하다. 탐색하려면 모든 데이터를 pop() 해야 한다.

스택의 활용

•

재귀 알로리즘

•

DFS 알고리즘

•

작업 실행 취소와 같은 역추적 작업이 필요할 때

•

괄호 검사, 후위 연산법, 문자열 역순 출력 등

큐 (Queue)

큐라는 이름은 대기열을 의미한다. 줄을 서서 기다리는 사람들과 유사하다.

•

큐는 한쪽에서 삽입, 반대 쪽에서 삭제가 이루어진다.

•

삽입이 이루어지는 쪽을 rear

•

데이터가 삭제되는 쪽은 front 라고 한다.

•

선입선출 (First-In-First-Out, FIFO)

ADT Queue의 연산

enqueue(item) : 큐에 item을 삽입한다. O(1)

dequeue() : 큐의 front에 위치한 item을 반환하고 삭제한다. O(1), O(N)

peek() : 큐의 front에 위치한 item을 삭제없이 반환한다. O(1)

ifFull() : 큐가 가득 차있다면 true, 아니라면 false를 반환한다. O(1)

isEmpty() : 큐에 item이 없다면 true, 아니라면 false를 반환한다. O(1)

큐의 장단점

front 위치의 데이터에 바로 접근하므로 데이터 삽입, 삭제의 시간 복잡도가 O(1) 로 빠르다.

큐 역시 front 가 아닌 중간에 위치한 데이터 접근이 불가능하다.

큐를 Linked List가 아니라 일반 Array 로 구현하면 dequeue의 시간복잡도가 O(n) 이 됨에 유의한다 (front의 item을 삭제하면 모두 앞으로 한 칸 씩 이동하게 된다)

큐의 활용

•

데이터를 입력된 순서대로 처리해야할 때

•

BFS 알고리즘

•

프로세스 관리

•

대기 순서 관리

덱 (Deque)

덱(Deque)은 Double-Ended Queue의 약어이다.

•

큐의 앞(front)과 뒤(rear, back) 모두에서 삽입과 삭제가 가능한 큐를 말하며, 때문에 스택처럼도 큐처럼도 사용 가능

ADT Deque의 연산

push_front(item) : 큐의 front에 item을 추가한다. O(1)

pop_front() : front의 item을 삭제 및 반환한다. O(1)

push_rear(item) : 큐의 rear에 item을 추가한다. O(1)

pop_rear() : rear의 item을 삭제 및 반환한다. O(1)

Deque의 장단점

데이터의 앞, 뒤 모두에서 삽입, 삭제가 모두 가능하며, O(1)의 빠른 시간복잡도를 갖는다.

스택, 큐에 비해 구현이 어렵다.

크기가 가변적이다.

index를 통해 임의의 원소에 O(1) 시간복잡도로 바로 접근이 가능하다.

새로운 원소 삽입 시, 메모리를 재할당하고 복사히자 않고, 새로운 단위의 메모리 블록(chunk)를 할당하여 삽입한다. 

Deque의 활용

•

데이터를 앞, 뒤 모두에서 삽입, 삭제하는 과정이 필요한 경우

•

데이터의 크기가 가변적일 경우

Underflow & Overflow

자료구조가 비어있을 때, pop()과 같은 출력을 시도하면 underflow, 자료구조의 공간이 가득 찼을 때 push()와 같은 삽입을 시도하면 overflow 되며 오류를 야기한다.

ref)

•

https://github.com/da-in/tech-interview-study/blob/main/Tech Interview Cheat Sheet/Data Structure/Stack&Queue&Deque.md

•

https://www.tutorialandexample.com/difference-between-stack-and-queue

•

https://devuna.tistory.com/22

•

https://2jinishappy.tistory.com/134

•

https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D-Stack-%ED%81%90-Queue-%EB%8D%B1-Deque

•

https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm?key=queue

•

https://www.tutorialspoint.com/data_structures_algorithms/dsa_queue.htm

•

https://www.geeksforgeeks.org/deque-in-python/

•

https://en.cppreference.com/w/cpp/container/deque