출처 : https://www.youtube.com/watch?v=Nk_dGScimz8

들어가기 전

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

추상적 자료구조

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

스택

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은 스택에서 가장 위에 있는 데이터로, 스택 포인터로 불린다.

4. 스택 응용 분야

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

4. BFS란

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

큐(Queue)

큐의 개념

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

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

예시

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

큐 구성도

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

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

3. 테크

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

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

테크의 구성도

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

4. 그래서 언제 쓰는데?

스택

1. 뒤로가기

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

2. 되돌리기 : ctrl + z

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

큐

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

결론

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