---
# System prepended metadata

title: '스택(Stack), 큐(Queue), 데크 (Deque, Deouble-Ended Queue)'
tags: [과외(하희영)]

---

# 스택(Stack), 큐(Queue), 데크 (Deque, Deouble-Ended Queue)

## 스택(Stack)
![](https://i.imgur.com/Umpsupo.png)
- LIFO(Last In, First Out) 원칙을 따르는 자료구조이다.
- 가장 최근에 삽입된 요소가 가장 먼저 제거된다.
- 함수 호출, 실행 콘택스트 관리등에 사용된다.
- 예시: 웹 브라우저의 뒤로 가기 기능

---

## 큐(Queue):
![](https://i.imgur.com/kkmqgUR.png)

- FIFO(First In, First Out) 원칙을 따르는 자료구조이다.
- 가장 먼저 삽입된 요소가 가장 먼저 제거된다.
- 너비 우선 탐색(BFS), CPU 스케줄링, 캐시 구현 등에 활용된다.
- 작업이 순차적으로 처리되어야 하는 상황에 적합하다.
- 예시: 은행에서 고객 대기열

---

## 데크 (Deque, Deouble-Ended Queue)

![](https://i.imgur.com/caQ8hMC.png)

- 양쪽 끝에서 요소의 삽입과 삭제가 가능한 자료구조이다.
- 스택과 큐의 기능을 모두 포함하고 있다.
- 양방향 연결 리스트로 구현할 수 있다.
- 예시: 왕복 1차로

---

# 리스트(List)

- 자료구조 중 하나로, 순서가 있는 요소들의 모임
- 리스트의 특징
    - 순서: 리스트의 요소들은 순서를 가지고 있어, 인덱스를 사용하여 접근할 수 있다.
    - 가변성: 리스트의 크기는 동적으로 변경할 수 있으며, 요소를 추가하거나 삭제할 수 있다.
    - 중복 허용: 리스트는 중복된 요소를 포함할 수 있다.


## Array List

![](https://i.imgur.com/2hFpsB8.png)
- 내부 구조: **동적 배열을 사용**하여 요소를 저장한다.
- 조회 속도: 인덱스를 사용하여 요소에 빠르게 접근할 수 있다. (O(1))
- 추가/삭제 속도: 배열의 중간에 요소를 추가하거나 삭제하는 경우, 요소를 이동시켜야 하기 때문에 속도가 상대적으로 느리다. (O(n))
- 메모리 사용량: LinkedList에 비해 메모리 사용량이 적다.
- 활용 시나리오: 조회가 빈번하고 추가/삭제가 상대적으로 적은 경우에 적합하다.

### Array List의 요소 추가 시

![](https://i.imgur.com/qgYI2hx.png)

---

![](https://i.imgur.com/IoY9Iy0.png)

---

## Linked List

![](https://i.imgur.com/glsQR75.png)

- 내부 구조: **이중 연결 리스트를 사용**하여 요소를 저장한다.
- 조회 속도: 인덱스를 사용하여 요소에 접근할 때, 처음이나 끝에서 순차적으로 탐색해야 하므로 속도가 상대적으로 느리다. (O(n))
- 추가/삭제 속도: 중간에 요소를 추가하거나 삭제하는 경우, 이웃하는 노드만 연결을 변경하면 되기 때문에 속도가 빠르다. (O(1) - 단, 인덱스를 찾는 과정에서의 탐색 시간은 제외)
- 메모리 사용량: 각 노드가 이전 및 다음 노드의 참조를 유지하므로 메모리 사용량이 상대적으로 높다.
- 활용 시나리오: 추가/삭제가 빈번하고 조회가 상대적으로 적은 경우에 적합하다.

### Linked List의 요소 삽입 시
![](https://i.imgur.com/Ipb8Yso.png)

---

# 트리(Tree), 그래프(Graph)

## 트리 (Tree)
![](https://i.imgur.com/xjf4wfv.png)

- 계층적인 구조를 가지며, 하나의 루트(root) 노드에서 시작하여 여러 개의 자식(child) 노드를 가질 수 있다.
- 각 노드는 하나의 부모(parent) 노드와 여러 개의 자식(child) 노드를 가질 수 있다.
- 트리는 실제로 계층적인 구조를 가진 데이터를 저장하고 탐색하기 위한 자료구조이다.

---

## 그래프 (Graph)
![](https://i.imgur.com/68Ij3Ri.png)

- 노드(node)와 간선(edge)으로 이루어진 자료구조이다.
- 노드는 그래프에서 위치를 나타내며, 간선은 노드들을 연결한다.
- 간선은 방향이 있을 수도 있고 없을 수도 있다. 방향성이 없는 그래프를 무향 그래프(undirected graph), 방향성이 있는 그래프를 유향 그래프(directed graph)라고 한다.
- 그래프는 실제로 다양한 상황에서 연결관계를 표현하고 분석하기 위한 자료구조이다.



###### tags: `과외(하희영)`