Stack 과 Que

코딩테스트 스터디를 하다가 큐와 스택을 알게되었다.
선입선출, 후입선출 이라는 것 정도만 알고있었는데, 생각보다 알고리즘과 자료를 효율적으로 처리히기 위해 알아야겠다는 생각이 들었고,
함수의 호출과 런타임도 관련있지않을까해서 공부해보았다.

스택과 큐

스택(Stack)과 큐(Queue)는 데이터 구조(Data Structure)로서, 데이터를 저장하고 조작하는 방법을 정의하는 추상적인 개념이다.
컴퓨터 과학(CS)에서 사용되며, 데이터의 삽입, 삭제, 조회 등을 효율적으로 처리하기 위해 사용한다.

스택(Stack) 이란?

스택(stack)은 stack은 순서가 보존되는 선형 자료구조로 Last In, First Out"(LIFO) 원칙을 따르는 자료구조이다.
ㄷㅔ이터를 받은 순서대로 정렬하며, 가장 마지막에 들어온 자료부터 순차적으로 실행한다.
이유는 stack안의 자료에는 top을 통해서만 접근할수있어 먼저들어온것부터 아래쪽에쌓이고 top을 통해서 나가기 위해서는 위에 쌓이것부터 빠져나가야 맨아래있는 가장 먼저들어온 자료가 빠져나갈수 있기때문이다.
이를 후입선출,Last In, First Out"(LIFO) 메커니즘이라 한다.

쌓아 올린것을 위에서부터 꺼내서 쓴다니까 프링글스가 떠올랐다.
프링글스안에 감자칩이 한줄로 쌓여있는데, 가장처음에들어간것은 아래에쌓여있고 마지막에 들어간 감자칩이 위에있는 감자칩일것이고,
우리는 맨위쪽에 손을넣어서 맨위에 있는것부터 집어먹으니 딱 맞는 예시가 아닐까?

(근데 하나씩 꺼내먹지 않을수도있네?)

아무튼 스택 자료구조는 차곡차곡 쌓아 올린 형태의 자료구조에서 가장마지막에 들어간 자료를 먼저 꺼내오는것을 말하며, 브라우저의 뒤로가기나 실행취소에 사용된다

📌 스택의 특징

스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고, top을 통해서만 접근할 수 있다.

top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.

자료를 삭제할 때도 top을 통해서만 가능하다.
스택에서 top을 통해 삽입하는 연산을 'push'(데이터 삽입) , top을 통한 삭제하는 연산을 'pop'(데이터 삭제)라고 한다.

따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조를 가지게 된다.

이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.

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

스택은 주로 함수 호출 시 호출된 함수의 정보를 저장하는 데에 사용되지만, 역추적(BackTracking) 이나 웹 브라우저의 뒤로가기(Undo) 기능과 같이 최근에 수행된 작업을 되돌리는 데에도 활용된다.

📝 스택 정리

이름	설명
Push (데이터 추가)	- 새로운 데이터를 스택에 추가하는 과정
	- 새로운 데이터는 스택의 맨 위(top)에 위치한다.
	- 스택에는 일반적으로 크기 제한이 있으며, 스택이 가득 찼는지 확인해야한다.
Pop (데이터 삭제)	- 스택의 맨 위에 있는 데이터를 제거하는 과정을 "pop"이라한다.
	- 가장 최근에 추가한 데이터가 가장 먼저 삭제된다.
Top (맨 위 데이터 조회)	- 택의 맨 위에 있는 데이터를 조회하는 것을 "top" 연산이라한다.
	- top 연산을 통해 가장 최근에 추가한 데이터를 확인할 수 있다.
Is Empty (비어있는지 확인)	- 스택이 비어있는지 여부를 확인하는 연산이다.
	- 스택에 데이터가 없는 경우 true를 반환한다.
Size (크기 확인)	- 스택에 저장된 데이터의 개수를 확인하는 연산이다.

---

큐(Queue) 란?

큐(Queue) 의 사전적 의미는 줄 혹은 줄을 서서 기다리는 것으로 stack처럼 순서가 보존되는 선형자료구조이다.
예를들면, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이 선입선출(FIFO, First in first out) 방식의 자료구조를 말한다.

📌 큐의 특징

stack이 정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는것과 달리,

`큐`는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 `양쪽`으로 이루어진다.
데이터를 저장할 때는 큐의 뒤에 데이터를 추가하며, 데이터를 꺼낼 때는 큐의 맨 앞에서부터 하나씩 꺼내게된다.

이때 `삽입연산만 이루어지는 곳을 리어(rear)`, `삭제연산만 수행되는 곳을 프론트(front)`로 정하여 각각의 연산작업만 수행된다.

큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부른다.

큐는 작업을 순차적으로 처리해야 하는 상황에서 사용되는데,
예를 들면 `프로세스의 스케쥴링`이나 네`트워크 패킷처리`, `BFS (Breadth-First Search)`와 같은 `그래프 알고리즘`에서 사용된다.

📝 큐 정리

이름	설명
Enqueue (데이터 추가)	- 새로운 데이터를 큐에 추가하는 과정이다.
	- 새로운 데이터는 큐의 뒤(rear)에 위치한다.
	- 큐의 크기가 제한되어 있다면, 새로운 데이터를 추가하기 전에 큐가 가득 찼는지 확인해야 한다.
Dequeue (데이터 삭제)	- 큐의 가장 앞(front)에 있는 데이터를 제거하는 과정이다.
	- 가장 오래된 데이터가 먼저 사라진다.
Front (가장 앞 데이터 조회)	- 큐의 가장 앞에 있는 데이터를 조회하는 것.
	- front 연산을 통해 가장 오래된 데이터를 확인할 수 있다.
Is Empty (비어있는지 확인)	- 큐가 비어있는지 여부를 확인하는 연산이다.
	- 큐에 데이터가 없는경우 true를 반환한다.
Size (크기 확인)	- 큐에 저장된 데이터의 개수를 확인하는 연산이다.

---

📝 오늘의 느낀점

나는 대체 아는게 뭐냐구우우우우😭