스택, 큐

스택(Stack)

정말 간단하게 말자하면 스택 이란 쌓아 올린다는 뜻입니다.
여기서 말하는 스택이란 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태라고 생각하면 됩니다.

스택은 후입선출(LIFO, Last In, First Out) 방식으로 데이터를 저장합니다.
즉, 가장 최근에 추가된 항목이 가장 먼저 제거됩니다.
스택은 한쪽 끝에서만 데이터를 추가하거나 제거할 수 있는 자료 구조입니다. 이를 '푸시(push)'와 '팝(pop)'이라고 합니다.

비어있는 스택에서 원소를 추출하려고 할때 stack underflow 라고 하며
스택이 넘치는 경우를 stack overflow 라고 합니다.

🍎 스택 용어

🍳 top(peek) - 가장 최근에 저장된 데이터이자 먼저 삭제 될 데이터입니다. 그림상에서 요소 4가 해당됩니다.
🍳 push - 데이터를 삽입하는것을 말하며 삽입 된 데이터는 삭제시 가장 먼저 삭제 될 데이터가 됩니다.
🍳 pop - 데이터를 삭제할 때 사용하며 가장 최근에 저장된 데이터가 삭제됩니다.

🍎 사용되는 예

브라우저의 뒤로가기
실행 취소 (Ctrl + z)
재귀 함수
역순 문자열 (문자열 거꾸로 뒤집기)

스택의 자료구조는 삽입과 삭제시에 O(1), 탐색에는 O(n)의 시간복잡도를 가지게 됩니다.

큐(Queue)

Queue 의 사전적 의미는 줄을 서서 기다리는 것을 의미합니다.
여기서 말하는 큐는 일상생활에서 놀이동산에서 줄을 서서 기다리는 것처럼,
선입선출(FIFO, First in first out) 방식을 의미합니다.

큐는 선입선출(FIFO, First In, First Out) 방식으로 데이터를 저장합니다. 즉, 가장 먼저 추가된 항목이 가장 먼저 제거됩니다.
큐는 데이터가 입력되는 쪽(front)에서만 삭제가 가능하고, 데이터가 출력되는 쪽(rear)에서만 추가가 가능합니다.

🍎 큐 용어

🍳 Enqueue - 데이터 삽입
🍳 Dequeue - (JS의 shift): 데이터 삭제
🍳 Front - Dequeue시 삭제되는 데이터 (가장 먼저 저장된 데이터)를 가르킵니다.
🍳 Rear - 추가될 새로운 요소의 위치를 가르킵니다.

🍎 사용되는 예

BFS 알고리즘
프로세스 관리 (JS의 콜백 큐)
프린터의 대기열
큐에는 우선순위 큐, 원형 큐라는 2개의 종류가 더 있기 때문에 지금 설명하는 큐는 선형 큐(Linear Queue)라고도 부릅니다.

큐는 스택과 마찬가지로 삽입과 삭제에는 O(1), 탐색에는 O(n)의 시간복잡도를 가집니다.

실전

예를 들어 setTimeout 이라는 함수를 실행시킨다고 가정해 봅시다.
setTimeout 이라는 함수는 바로 실행 할 수 없는 코드이며,
싱글 스레드 언어 특성상 저 코드를 위해 기다려야 하기 때문에 Stack 에서 치워버리고 싶어 한다.
그래서 대기실 이라는 곳에 보관한다.

대기실에는 ajax 코드, 이벤트 리스너, setTimeout 등이 있다.

대기실에 있던 코드들은 실행이 완료 된 후에는 Queue 라는 곳에 저장해 놓고
Stack 에 아무런 코드가 없을 경우 하나씩 올려서 실행시킨다.
Queue 는 FIFO(first in first out) 의 규칙을 따른다.

예전에 for 문으로 3초 정도 연산을 하는 함수를 만들었다.
그때 이벤트 리스너로 모달창을 띄우는 코드를 실행했을때 작동이 되지 않았다. 왜?
Stack 에 아무것도 없어야 Queue 에서 대기가 끝난 코드가 Stack 에 올라가서 실행되는데 Stack 에는 연산을 실행하고 있기 때문에 코드가 실행 되지 않았다.
따라서 이걸 생각하고 코드를 짜는 습관을 들이도록 하자.