S4) Unit 1. [자료구조/ 알고리즘] 자료구조 & Stack & Queue

📣  자료구조란?

𝟭. 자료구조의 정의

✔️ 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것
➰ 데이터 : 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값
➰ 데이터는 필요에 따라 특징을 잘 파악하고, 분석하고 정리해서 활용해야만 의미를 가질 수 있다.
➰ 이를 위해 데이터를 체계적으로 정리해서 저장해두는 게 유리하다!
 

𝟮. 자료구조의 분류

✔️ 알고리즘 테스트에 자주 등장하는 4가지 개념
➰ Stack, Queue, Tree, Graph

 

𝟯. 자료구조의 특징

✔️ 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다.
➰ 어떠한 상황에 적합한 자료구조를 빠르고 정확하게 적용해서 문제를 해결할 수 있다.

---

📣  Stack 이란?

𝟭. Stack의 정의

✔️ 데이터를 순서대로 쌓는 자료구조
➰ 동그란 원통에 구슬을 넣고, 가장 맨위에 있는 구슬을 먼저 빼는 것처럼 데이터를 구슬처럼 사용할 수 있다.
 

𝟮. Stack의 구조

✔️ LIFO(Last In First Out) 혹은 FILO(First In Last Out)
➰ 입력과 출력이 양쪽이 아닌 스택의 최상단에서만 제한적으로 이루어진다.
➰ 맨 처음 넣은 데이터는 제일 밑에 위치하므로 제일 나중에 꺼낼 수 있고, 맨 마지막에 넣은 데이터는 제일 위에 위치하므로 첫번째로 꺼낼 수 있다.
➰ 데이터를 넣는 것을 PUSH, 꺼내는 것을 POP 이라고 한다.
 

𝟯. Stack의 특징

1️⃣ LIFO(Last In First Out)
➰ 후입선출의 구조
➰ 스택 구조 내에서는 특정 데이터를 조회할 수 없으며, 최상단에서만 데이터를 저장하고 꺼낼 수 있다 -> 매우 빠르다는 장점이 있다.

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

// stack
// 먼저 넣은 데이터가 맨 마지막에 위치한다.
| 4 |
| 3 |
| 2 |
| 1 |


stack.pop();

// stack
// 맨 마지막에 넣은 데이터가 제일 처음 빠진다.
| 3 |
| 2 |
| 1 |

 
2️⃣ 하나의 입출력 방향을 가지고 있다.
➰ 데이터를 넣고 뺄 수 있는 곳이 스택의 최상단 한 곳이다.
➰ 데이터를 넣을 때도 최상단으로 넣고, 뺄 때도 최상단에서 뺄 수 있다.
 
3️⃣ 데이터는 하나씩 넣고 뺄 수 있다.
➰ 입출력 공간이 한 군데 이기 때문에 데이터는 하나씩 다룰 수 있다.
➰ 여러 개의 데이터를 빼고 싶을 땐 pop()을 여러 번 수행해야하는 것이다.
 

𝟰. Stack의 실사용 예제

✔️ 브라우저의 뒤로 가기, 앞으로 가기 기능
➰ 새로운 페이지에 접속할 때, 현재 페이지를 Prev Stack에 보관한다.
➰ 뒤로 가기를 누르면 현재 페이지는 Next Stack에 넣고, Prev Stack에 최상단에 보관된 페이지를 현재 페이지로 가져온다.
➰ 앞으로 가기를 누르면 Next Stage에 가장 최상단에 보관된 페이지를 현재 페이지로 가져오고, 현재 페이지였던 페이지는 Prev Stack에 넣는다.

---

📣  Queue 란?

𝟭. Queue의 정의

✔️ Stack과 반대되는 개념으로 먼저 집어 넣은 데이터가 먼저 나오는 임시 기억 장치
 

𝟮. Queue의 구조

✔️ FIFO(First In First Out) 혹은 LILO(Last In Last Out)
➰ 먼저 들어간 데이터가 먼저 나온다.
➰ 입력 방향과 출력 방향이 처음과 끝으로 고정되어 있으며, 입력 시에는 큐의 끝(tail)에서, 꺼낼 때는 큐의 맨 앞(head)에서 진행된다.
➰ 데이터를 넣는 것을 enqueue, 꺼내는 것을 dequeue 라고 한다.
 

𝟯. Queue의 특징

1️⃣ FIFO(Fist In First Out)
➰ 선입선출의 구조

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);

// Queue
|  1   <-   2   <-   3   <- 4   |
출력(head)                      입력(tail)

queue.dequeue();

// Queue
|  2   <-   3   <- 4   |
출력(head)             입력(tail)

 
2️⃣ 두 개의 입출력 방향을 갖고 있다.
➰ 데이터를 입력할 때는 큐의 맨 끝(tail)으로만 입력 가능하고, 출력할 때는 큐의 맨 앞(head)으로만 출력이 가는ㅇ하다.
➰ 입출력 방향이 같다면 Queue 라고 볼 수 없다!
 
3️⃣ 데이터는 하나씩 넣고 뺄 수 있다.
➰ 각 처리 시마다 한 개의 데이터를 넣거나 뺄 수 있다.
➰ 여러 개의 데이터를 빼고 싶다면 큐의 맨 앞에서 한 번에 한 개의 데이터만 뺄 수 있으므로 여러 번 실행해야 한다.
 

𝟰. Queue의 실사용 예제

✔️ 프린터에서의 문서 인쇄
➰ 우리가 문서를 작성하고 출력 버튼을 누르면 문서는 인쇄 작업 Queue에 들어간다.
➰ 프린터는 인쇄 작업 Queue에 들어온 순서대로 문서를 인쇄한다.
 
✚ 버퍼(buffer)
✔️ 컴퓨터 장치들 사이에서 데이터를 주고받을 때, 각 장치에서 존재하는 속도나 시간 차이를 극복하기 위해 사용하는 것
➰ 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼를 사용한다.

(왼) 대부분의 컴퓨터 장치에서 불규칙적으로 이벤트 발생 / (오) CPU에서 규칙적으로 이벤트 처리

➰ 일반적으로 프린터는 속도가 느리고, CPU는 그에 비해 데이터 처리 속도가 빠르다.
➰ CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 후, Queue에 저장하고 다른 작업을 수행한다.
➰ 프린터는 Queue에서 데이터를 받아 들어온 순서대로 일정한 속도로 인쇄한다.