자료구조 :) Stack과 Queue를 이해한다.

 

 

 

goal

자료구조 Stack과 Queue를 이해한다.

 

 자료구조를 공부하는 이유 "극강의 효율 추구"

---

어떤 언어를 배우던 배열의 개념은 공부하게 되는데, 배열의 개념을 안다는 가정하에 설명을 하겠다.

[1, 2, 3, 4, 5] 처럼 숫자가 저장된 배열이 있다고 생각해보자. 그리고 반복문을 이용해 처음부터 탐색을 시작하여 마지막 요소 값을 찾을 것이다.

앞선 배열의 요소의 개수는 5개이니 반복문에 의해서 배열을 총 5번을 탐색하여 마지막 요소를 찾는다.
만약 배열의 요소가 1만개가 되는 상황이면 어떨까? 반복문은 1만번을 탐색하게 될 것이다.

우리의 목적은 마지막 요소를 찾는 것이 목표인데 <마지막 요소를 찾기 위해 1만번을 탐색한다>는 것은 참 아이러니하면서 눈살이 찌풀어지지 않는가? 이러한 예시가 비효율적인 프로그램이라고 할 수 있으며 같은 문제를 조금 더 효율적인 방법으로 처리하기 위해서 우리는 자료구조를 배워야한다.

 

 

 

1. 자료구조 관점에서의 Stack과 Queue

---

[1] 자료구조 관점 Stack

---

 

 

 

1. 개념

---

이미지 : [자료구조][Javascript] Stack 이란?

 

• LIFO( List in first out )의 구조이다.
• 즉, 마지막에 들어온 데이터가 가장 먼저 출력이 되는 형태를 가진 자료구조이다.
• Stack에서 데이터를 넣는 과정을 push라하며 데이터를 빼는 것을 pop이라고 한다.

 

 

 

2. 특징

---

• 1번의 개념과 중복되는 내용이긴 하나, Stack에 빨리 들어온 데이터가 나중에 들어온 데이터보다 아래 쌓이게된다.

 

 

 

3. 사용의 예시

---

• 웹 브라우저 방문기록 저장
• 실행취소
• 문자열 역순으로 만들기
• 수식의 괄호 검사

 

 

 

[2] 자료구조 관점 Queue

---

 

 

1. 개념

---

이미지 : 자료구조][Javascript] Queue 란?

• FIFO(First in first out) 구조이다.
• 즉, 먼저 들어온 데이터가 가장 먼저 출력되는 자료구조이다.
• 입력과 출력의 통로가 따로 존재한다.
• 데이터가 들어오는 부분을 enqueue라 하고 데이터가 나가는 부분을 dequeue라한다.
• Queue의 데이터 입력부의 첫 부분을 가리켜 back(또는 tail)이라고하고
• Queue의 데이터 출력부의 첫 부분을 가리켜 front(또는 head)라고 한다.

 

 

 

2. 특징

---

• Queue는 한 번에 입/출력 중 하나의 작업만 수행한다.
• 두 개의 입출력 방향을 가지고 있다.

 

 

 

3. 사용의 예시

---

• 프린트의 출력
• 유튜브 스트리밍 서비스

 

 

 

4. 추가적으로 알면 좋은 내용

---

프린터를 예로 들자면, 컴퓨터와 프린터가 서로 소통하는 것이다.

컴퓨터의 CPU는 매우 빠른 속도로 작업을 처리하고 일정한 작업처리 시간을 가진다.

하지만 프린터는 상대적으로 컴퓨터의 작업속도보다 느리다. (많이 느리다.)

이처럼 컴퓨터-프린터의 속도차이 및 시간 차이를 극복하기 위해 임시기억장치를 사용하게 되는데,

컴퓨터가 작업처리한(프린트 요청) 임시 기억장치의 Queue에 들어가게 되고 프린터는 Queue에 들어온 작업순서대로 작업을 처리하게 된다. 임시 기억장치의 Queue는 데이터를 한 곳(컴퓨터)에서 다른 한 곳(프린터)으로 전송하는 하나의 임시 데이터 집합소가 되며 이를 버퍼(Buffer)라고한다.

버퍼링(Buffering)이란 데이터를 활용하는 방식 또는 데이터를 채우는 동작을 말한다.

 

 

 

 

결론, Queue는 버블티이론이고 뿜으면 Stack이다.