스택과 큐
출처 : 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은 스택에서 가장 위에 있는 데이터로, 스택 포인터로 불린다.
4) 스택 응용 분야
인터럽트의 처리 : 현재 진행 중인 명령어 위치를 스택에 push하고, 인터럽트 발생 상황 처리 후 스택에서 pop을 통해 전에 진행중이던 것을 받아옴, 서브루틴 호출 작업
함수 호출(재귀 호출 포함) : 함수를 호출 시 현재 진행 중인 명령어 주소를 스택에 저장
후위표현 연산 : postifix 계산시 사용
깊이 우선 탐색(DFS : Depth-First Search) : 깊이 내려갈 때마다 스택에 값을 push하고, 더 이상 깊이 갈 곳이 없을 경우 스택에서 pop한 노드와 인접한 노드를 찾음
탐색을 하고 있는 분기에서 완벽하게 탐색을 한 이후 다른 분기를 탐색
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) 큐 구성도
한쪽에서는 ENQUEUE 연산을 이용해서 데이터를 넣고, 한쪽에서는 DEQUEUE로 연산을 이용해서 데이터를 꺼낸다.
데이터가 꺼내는 쪽에서 가장 가까운 데이터를
Front[앞]라고 데이터를 넣는 쪽에 가장 가까운 데이터를Rear[뒤]이라고 함
4. 테크
1) 테크(Deque:Double Ended Queue)의 개념
: 테크는 큐의 양쪽 끝에서 삽입과 삭제 가능한 자료구조
2) 테크의 구성도
두 개의 포인터를 사용하여, 양쪽의 삭제/삽입이 가능하다.
데크를 이용한 스택과 큐의 구현 가능
PUSH : 삽입 POP : 데크에서 Fornt와 Rear에 있는 데이터를 하나씩 꺼내는 연산
5. 그래서 언제 쓰는데?
스택
뒤로가기
뒤로 가기를 누른다는 것은 웹페이지 히스토리 스택의 맨 위에서 한 페이지를 가져 가는 것
되돌리기 : ctrl + z
유저하는 행동을 차곡차곡 쌓다가 되돌리기 순간 스택으로 가사 과거를 되돌릴 수 있는
큐
이메일 전달
푸쉬 알림 기능
쇼핑몰에서 주문을 처리하는 방식
콜센터의 백엔드(전화 온 순서대로 처리)
결론
실제로 존재하지는 않지만 규칙을 제공하고 덕분에 자료를 좀 더 구조적으로 생각 가능
Last updated
