스택(Stack)

-스택의 개념

쌓아 올린다는 뜻, 차곡차곡 쌓아 올린 형태의 자료구조   

-스택의 특징

같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있다.

• top으로 정한 곳을 통해서만 접근 가능
  top = 가장 최근에 들어온 가장 위에 있는 자료 (삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.)
  -> top을 통해 삽입하는 연산 'push', 삭제하는 연산 'pop'
  

따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다.
이러한 구조를 후입선출 (LIFO, Last In First Out) 구조라고 한다.

큐(Queue)

-큐의 개념

사전적 의미 : 1. 줄, 혹은 줄을 서서 기다리는 것
**선입선출 (FIFO, First In First Out)** 방식의 자료구조

-큐의 특징

한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

**삭제연산(디큐, dnQueue)**만 수행되는 곳을 **프론트(front)**
**삽입연산(인큐, enQueue)**만 이루어지는 곳을 **리어(rear)**

큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성
접근방법은 가장 첫 원소와 끝 원소로만 가능
가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

즉, 큐에서 front 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며,
rear 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

-큐의 종류

1. 선형 큐(Linear Queue)
   : 가장 간단한 형태의 큐
   • 맨 앞과 맨 뒤의 포인터인 front와 rear를 가지고 있으며, 새로운 원소는 항상 rear에 추가되고 front에서 제거
2. 원형 큐(Circular Queue)
   : 선형 큐의 확장 개념
   • 마지막 원소가 첫 번째 원소와 연결되는 구조를 가지고 있음
     공간을 효율적으로 활용, 사용 가능한 메모리가 제한적인 상황에서 자주 사용
3. 우선순위 큐(Priority Queue)
   : 각 원소에 우선순위 값을 할당하고, 가장 높은 우선순위를 가진 원소가 먼저 처리되도록 보장
   • 운영 체제에서 프로세스의 스케줄링이나 비상 작업 관리 등 실시간 시스템에서 자주 사용
4. 덱(Deque)
   : 양쪽 끝에서 원소의 삽입과 제거가 모두 가능한 큐
   • 다른 종류의 큐에 비해 더 많은 유연성을 제공하여 양쪽에서 원소를 추가하거나 제거해야 하는 상황에서 적합