# 스택과 큐

> 출처 : <https://www.youtube.com/watch?v=Nk\\_dGScimz8>

## 1. 들어가기 전

> 스택과 큐는 우리의 상상에만 존재 실제로 프로그래밍 언어들에서는 존재하지 않음 스택과 큐는 **일종의 규칙**

### 추상적 자료구조

* 자료구조의 방법이 코드로 정의 된 것이 아니라 그 구조의 행동 양식에만 설명
* 스택과 큐는 **결국 배열 위에 어떤 규칙을 설정한 모습**

## **2. 스택**

### 1) **스택의 개념**

스택은 한 방향으로만 자료를 넣고 꺼낼 수 있는 **`LIFO(Last-In-First-Out)`** 형식의 자료 구조

* **`선입후출`** 구조 또는 **`후입 선출`** 구조 : 박스는 아래부터 위로 쌓는데 그 아래에 있는 박스를 치우기 위해서 위에 있는 박스부터 내려야 함
* stack.append() : **삽입(PUSH)**, stack.pop() : **삭제(POP)**
* print(stack\[::-1]) : 최상단 원소부터 출력
* print(stack) : 최하단 원소부터 출력(먼저 들어온 데이터들)

### 2) 예시

* 팬케이크를 위로 쌓는다고 했을 때 막 만든 걸 위로 올림 그리고 마지막에 올린 거\[Last in] 먼저 먹는\[First Out] 형식

### 3) **스택의 구조**

* **한 방향으로만** PUSH와 POP을 이용하여 자료를 넣고 꺼낸다
* TOP은 스택에서 가장 위에 있는 데이터로, **스택 포인터**로 불린다.

![](https://velog.velcdn.com/images/prettylee620/post/2dcc061c-d90c-45fc-ac02-13c3e9973105/image.png)

### 4) **스택 응용 분야**

* **인터럽트의 처리** : 현재 진행 중인 명령어 위치를 스택에 push하고, 인터럽트 발생 상황 처리 후 스택에서 pop을 통해 전에 진행중이던 것을 받아옴, **서브루틴 호출 작업**
* **함수 호출(재귀 호출 포함)** : 함수를 호출 시 현재 진행 중인 명령어 주소를 스택에 저장
* **후위표현 연산** : postifix 계산시 사용
* **깊이 우선 탐색(DFS : Depth-First Search)** : 깊이 내려갈 때마다 스택에 값을 push하고, 더 이상 깊이 갈 곳이 없을 경우 스택에서 pop한 노드와 인접한 노드를 찾음
* 탐색을 하고 있는 분기에서 **완벽하게 탐색을 한 이후** 다른 분기를 탐색

![](https://velog.velcdn.com/images/prettylee620/post/a30c0618-c8b7-4091-bc49-b0205ad71469/image.png)

### 5) **BFS란**

* 너비 우선 탐색
* **가까운 노드부터 탐색**
* 선입선출 방식인 큐 자료구조 이용
* 시작 노드를 넣은 다음 방문 처리 후 시작 노드를 꺼내고 방문하지 않은 인접 노드 모두를 큐에 삽입
* 실제 수행 시간 DFS보다 좋은 편
* **A(인접한 B, C, D방문) > B -> C -> D -> E(B에 인접한)** **> F(C에 인접한) > G(F에 인접한)**

## **3. 큐(Queue)**

### **1) 큐의 개념**

: 큐는 한쪽 끝에서는 삽입 작업이 이뤄지고, 반대쪽 끝에서는 삭제 작업이 이루어지 **`FIFO(First-In-First-Out)`** 형식의 자료 구조

* 대기줄에 비유
* **선입선출 구조** : 나중에 온 사람일수록 나중에 들어가는 공정한 자료구조
* queue.append(): 삽입, `queue.popleft()` : 삭제

#### 예시

* 줄 맨 앞에 서 있는 사람이 가장 먼저 버스를 타는 원리
* 큐 **뒤에** 요소를 `추가`
* 큐 **앞에** 요소를 `제거`\[First Out]

### **2) 큐 구성도**

![](https://velog.velcdn.com/images/prettylee620/post/eceea723-6e1a-42d8-81e6-0e7c7ab0508a/image.png)

* 한쪽에서는 **ENQUEUE 연산**을 이용해서 데이터를 넣고, 한쪽에서는 **DEQUEUE로 연산**을 이용해서 데이터를 꺼낸다.

![](https://velog.velcdn.com/images/prettylee620/post/b7b02c3f-9aeb-4fa0-8be7-9b5e6c240561/image.png)

* 데이터가 **꺼내는 쪽에서** 가장 가까운 데이터를 `Front[앞]`라고 데이터를 **넣는 쪽에** 가장 가까운 데이터를 `Rear[뒤]`이라고 함

## **4. 테크**

### **1) 테크(Deque:Double Ended Queue)의 개념**

![](https://velog.velcdn.com/images/prettylee620/post/5a1ed890-219c-4f66-abb5-115c682cc3b5/image.png)

: 테크는 큐의 양쪽 끝에서 삽입과 삭제 가능한 자료구조

### **2) 테크의 구성도**

* 두 개의 포인터를 사용하여, 양쪽의 삭제/삽입이 가능하다.
* 데크를 이용한 스택과 큐의 구현 가능
* PUSH : 삽입 POP : 데크에서 Fornt와 Rear에 있는 데이터를 하나씩 꺼내는 연산

## 5. 그래서 언제 쓰는데?

#### 스택

1. 뒤로가기

* 뒤로 가기를 누른다는 것은 웹페이지 히스토리 스택의 맨 위에서 한 페이지를 가져 가는 것

![](https://velog.velcdn.com/images/prettylee620/post/fb9e92c5-18d6-4956-a3d2-42d8df67cc2c/image.png)

2. 되돌리기 : ctrl + z

* 유저하는 행동을 차곡차곡 쌓다가 되돌리기 순간 스택으로 가사 과거를 되돌릴 수 있는

![](https://velog.velcdn.com/images/prettylee620/post/7ae90aa8-a7af-4e1e-aa9d-1a0340b64705/image.png)

#### 큐

1. 이메일 전달
2. 푸쉬 알림 기능
3. 쇼핑몰에서 주문을 처리하는 방식
4. 콜센터의 백엔드(전화 온 순서대로 처리)

## 결론

> 실제로 존재하지는 않지만 규칙을 제공하고 덕분에 자료를 좀 더 구조적으로 생각 가능
