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

스택 (Stack)

💡 정의

자료의 입력과 출력을 한 곳(방향)으로 제한한 자료구조

 

💡 특징

- 후입선출 구조: 마지막(Last)에 들어온(In) 데이터가 먼저(First) 나간다(Out) → Last-in-first-out(LIFO)

- 시간복잡도: 삽입 삭제 연산 O(1)
- top을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다.
- top 위치 이외의 데이터에 접근할 수 없으므로 탐색할 수 없다. 탐색하려면 모든 데이터를 꺼내면서 진행해야 한다.

 

💡 관련 용어

- top(peek): 가장 최근에 저장된 데이터이자 먼저 삭제 될 데이터
- push: 데이터 넣기/삽입. (삽입 된 데이터는 삭제시 가장 먼저 삭제 될 데이터가 됨.)
- pop: 데이터 꺼내기/삭제. (가장 최근에 저장된 데이터가 삭제됨.)

 

---

큐 (Queue)

💡 정의

자료의 입력과 출력을 한 쪽 끝(front, rear)으로 제한한 자료구조

 

💡 특징

- 선입선출 구조: 처음(First)에 들어온(In) 데이터가 먼저(First) 나간다(Out) → First-in-First-Out(FIFO)
- 시간 복잡도: 삽입 삭제 연산 O(1)
- 데이터 접근, 삽입, 삭제가 빠르다.
- 중간에 있는 데이터에 대한 접근이 불가능하다.

- 데이터를 삭제하기 전에는 큐가 empty 한지, 큐에 데이터를 추가하려 할 때는 큐가 full 인지 확인 후 진행해야 한다.

 

💡 관련 용어

- enqueue: 데이터 넣기/삽입.
- dequeue: 데이터 꺼내기/삭제.
- rear: 데이터가 삽입되는 곳.
- front: 데이터가 삭제되는 곳.

 

---

덱 (Deque)

💡 정의

자료의 입력과 출력을 양 쪽 끝에서 가능하게 하는 자료구조

 

💡 특징

- 시간복잡도: 삽입 삭제 연산 O(1) / 탐색 O(1)
- 데이터의 삽입 삭제가 빠르고 앞, 뒤에서 삽입 삭제가 모두 가능하다.
- 연속적인 메모리를 기반으로 하는 시퀀스 컨테이너. 선언 이후 크기를 줄이거나 늘릴 수 있는 가변적 크기.
- index 를 통해 임의의 원소에 바로 접근이 가능하다.
- 새로운 원소 삽입 시, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.
- 중간에서의 삽입 삭제가 어렵다.
- 스택, 큐에 비해 비교적 구현이 어렵다.

 

💡 관련 용어

- 스크롤(scroll) : 입력이 한쪽 끝으로만 가능하도록 제한한 덱
- 셸프(shelf) : 출력이 한쪽 끝으로만 가능하도록 제한한 덱

 

---

 

[출처 및 참고]

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