스택(Stack)과 큐(Queue)는 리스트(List) 자료구조의 특별한 경우이다.

01. Stack(후입선출)

---

: 데이터(data)를 순서대로 쌓는 자료구조를 말한다.

🔨 1. Stack의 구조

• Stack은 후입선출(Last In First Out, LIFO) 구조로

  → 가장 마지막에 넣은 데이터가 스택의 맨 위에 위치하기 때문에 가장 먼저 빼서 사용할 수 있다.

• 배열과 마찬가지로 Stack에서 데이터를 넣는 것은 Push 라고 하며 데이터를 읽는 것과 동시에 꺼내는것(삭제)을pop이라고 한다.

• 스택 자료구조의 대표적 예는 뒤로가기 버튼으로

  → 인터넷 서핑을 할 때 뒤로가기를 누르면 바로 이 전 페이지, 즉 가장 최근의 페이지를 보여준다.

• 자료구조 Stack의 특징은 : 입력과 출력이 하나의 방향으로 이뤄지는 제한적 접근이라는 것이다.
  

※ 후입선출(Last In First Out, LIFO) 은 FILO(First In Last Out)이라고도 한다.

🔨 2. Stack의 특징

1️⃣ LIFO(Last In Fist Out, 후입선출)

• 가장 먼저 들어간 데이터가 가장 나중에 나오는 후입선출의 구조

ex1) 1, 2, 3, 4 를 차례대로 스택에 넣는다.

stack.push(데이터)
------------------
1 <- 2 <- 3 <- 4
------------------
: 들어간 순서대로 1번이 가장 먼저 들어가고 4번이 마지막으로 들어간다.

ex2) 빈 스택이 될 때까지 데이터를 전부 빼낸다.
stack.pop()
------------------

------------------
4, 3, 2, 1
: 가장 마지막에 있던 데이터부터 차례대로 나오게 된다.

• 후입선출로 스택 구조는 조회가 필요치 않아
  → 데이터를 저장하고 검색하는 프로세스가 매우 빠르며 & 최상위 블록에서 데이터를 저장하고 검색할 수 있다 는 장점이 있다.

2️⃣ 데이터는 하나씩 넣고 뺄 수 있다.

• 데이터를 한꺼번에 여러 개를 넣거나 뺄 수 없다.

3️⃣ 하나의 입출력 방향을 가지고 있다.

• 입력과 출력이 한반향인 제한적 접근 구조이다.

4️⃣ 저장되는 데이터는 유한하고 정적이여야 한다. 🤙 콜 스택(Call Stack)

• 콜스텍 내부의 함수 실행 데이터는 → 스택의 프레임으로 저장된다.
  • 여기서 프레임은 해당 기능에 필요한 데이터가 저장되는 공간 블록을 말한다.
• 따라서 함수가 새로운 변수를 선언할 때마다 → 새로 선언된 변수는 스택의 최상위 블록으로 push된다.
• 후입선출 구조에 따라 함수가 종료될 때마다 최상위 블록이 삭제(pop)되므로 → 함수가 완전히 종료되면 스택에 들어간 모든 변수가 삭제된다.
• 여기서 스택에 쌓인 데이터가 정적 특성을 가져야 → 컴파일 시간이 결정된다.
  • 컴파일(Compile)이란 어떤 언어의 코드 전체를 다른 언어로 바꿔주는 과정을 말한다.
• 마지막으로 스택에 저장되는 데이터의 종류는 : 로컬변수(value type 또는 프리미티브, 프리미티브 상수), 포인터 및 함수 프레임이다.

5️⃣ 스택의 크기는 제한되어 있다.

• 힙(heap)에 비해 스택은 크기가 제한되어 있어 → 스택 오버플로(Stack Overflow)같은 에러가 자주 발생한다.
• 대부분의 언어는 스택에 저장할 수 있는 값의 크기가 제한되어 있다.

🔨 3. Stack의 실사용 예제

• 브라우저의 뒤로가기, 앞으로 가기 기능

1. 새로운 페이지로 접속하면 -> 현재 페이지는 prev stack에 보관한다.
2. 뒤로 가기버튼을 눌러 이전 페이지로 돌아갈 때엔 -> 현재 페이지를 next stack에 보관하고 prev stack에서 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
3. 앞으로 가기 버튼을 눌르면 - > next stasck에서 가장 마지막으로 보관된 페이지를 가져온다.
4. 마지막으로 현제 페이지를 prev stack에 보관한다.

02. Queue(선입선출)

---

: 큐(Queue)는 줄(Line)이라는 뜻으로, 줄을 서서 기다리다, 대기 행렬이라는 뜻을 가진다.

• 톨게이트를 Queue의 자료구조, 자동차를 데이터(data)로 비유할 수 있다.
• 큐는 선입선출 구조로 → 가장 먼저 들어온 데이터가 가장 먼저 빠져나온다.

🔨 1. Queue의 구조

• Stack과 반대되는 개념인 선입선출(FIFO, First In First Out / LILO, Last In Last Out) 구조이다.
• 자료구조 Queue는 데이터가 입력된 순서대로 처리할 때 사용한다.
• 데이터를 넣는 것을 enqueue, 데이터를 꺼내는 것을 dequeue라고 한다.

🔨 2. Queue의 특징

1️⃣ FIFO(First In Fist Out, 선입선출)

• 먼저 들어간 데이터가 가장 먼저 나오는 구조

예1) 1, 2, 3, 4를 큐에 차례대로 넣습니다.

						queue.enqueue(데이터)
출력 방향 <---------------------------< 입력 방향
				     1 <- 2 <- 3 <- 4
				<---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 큐가 빌 때까지 데이터를 전부 빼냅니다.

						queue.dequeue(데이터)
출력 방향 <---------------------------< 입력 방향

				<---------------------------<
1, 2, 3, 4
제일 첫 번째 있는 데이터부터 차례대로 나오게 됩니다.

2️⃣ 데이터는 하나씩 넣고 뺄 수 있다.

• 데이터를 한꺼번에 여러 개를 넣거나 뺄 수 없다.

3️⃣ 두 개의 입출력 방향을 가지고 있다.

• Queue 자료구조는 데이터의 입력, 출력 방향이 다르다.

🔨 3. Queue의 실사용 예제

🖨️ 프린트

파워포인트 속 페이지를 순서대로 프린트를 한다고 가정해보자.

1. 컴퓨터 출력 버튼을 누른다.
2. 프린터의 임시 기억 장치인 Queue에 하나씩 들어온다.
3. Queue에 들어온 문서를 순서대로 인쇄한다.

💡 버퍼(Buffer)

• 컴퓨터 장치들 사이에서 데이터를 주고받을 때, 각 장치 사이의 속도 차이나 시간 차이를 극복하기 위해

  → 임시 기억 장치의 자료 구조로 Queue를 사용하고, 이를 통틀어 버퍼(Buffer)라고 한다.

💡 버퍼링(Buffering)

• 대부분 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생한다.
• 이에 반해 CPU에 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖습니다.
  
  

🤔 컴퓨터와 프린터 사이의 데이터 통신을 정리하자면 …

일반적으로 프린터는 속도가 느리고 CPU는 데이터 처리 속도가 빠르다.
따라서 CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 다음 → 인쇄 작업 Queue 에 저장하고 다른 작업을 수행한다.
프린터는 인쇄 작업 Queue에서 데이터를 받아 → 일정한 속도로 인쇄한다.