Stack&Quque

Stack

스택이란 무엇일까? 스택은 주변에서 택배상자 등 위쪽으로만 물건을 집어넣고 할수 있는 것들이 해당된다.

택배상자라던지, 젠가 상자 등등…

이보다 더 확실한 것이 있는데, 바로 하노이의 타워이다.

하노이의 타워는 사진에서 보이듯이 하나의 기둥에 여러 원반이 꽂혀있는 형태이다. 한쪽의 타워에서 다른쪽의 타워로 모든 원반들을 옮겨야 하며, 이때 크기가 작은 원반위에 큰 원반이 위치할 수 없다.

또한 맨 아래의 원반은 모든 원반이 제거되어야만 비로소 다른 막대로 옮길수 있다.

여기서 스택의 특징이 두드러진다.

스택은 하노이의 타워처럼 아래에 존재하는 요소들은 위의 요소가 전부 제거되어야만 제거될수 있다.

그렇기때문에 가장 처음에 입력된 요소는 가장 마지막에 스택에서 제거된다. 이러한 습성을 FILO라고 한다.

메서드

이런 스택을 구현한다면 가지게 될 메서드는 무엇이 있을까?

1. push - 스택 최상위에 하나의 요소를 집어넣는다.
2. pop - 스택 최상의 요소 하나를 제거하고 해당요소를 리턴한다.
3. size - 스택의 크기를 리턴한다.
4. at - i번째 요소가 무엇인지 리턴한다. 이정도 있을듯 하다.

사용처

스택은 실생활 어디에서 사용되고 있을까? 단순하게 생각하면, 비커와같은 구조를 가진다면 거진 다 비슷하지 않을까 싶다. 음..

1. 하노이의 타워
2. 택배상자
3. 메모리(스택)

이정도가 있을듯 하다.

Queue

큐는 주위에서 흔하게 볼 수 있다. 큐는 놀이공원, 음식점 등등에서 볼수 있는 대기열과 같은 구조를 가지고 있다.

다만 가끔 특이한 방식으로 우선순위를 기반으로 동작하기도 하며, 원형의 구조를 가지기도 한다.

이런 큐의 특징은 다음과 같다. 처음 들어온 요소는 대부분 맨 처음에 제거된다. 일반적으로 FiFO 구조라고 한다.

대부분이라고 작성한 까닭은 일반적인 큐는 맨 처음의 요소가 제거되지만, 우선큐(Priority Queue)는 그렇지 않기 때문이다.

우선큐는 나중에 작성하고 우선 큐 자체에 대해서 정리해보자.

메서드

큐를 직접 구현한다면 무슨 메서드가 필요할까?

1. enqueue - 큐의 맨 뒤에 요소를 추가한다.
2. dequeue - 큐의 맨 앞 요소를 제거하고, 해당 요소를 리턴한다.
3. size - 큐의 사이즈를 리턴한다.

이정도가 될것이다.

특수형태

큐에는 특수한 형태가 존재한다.

그종류들중 알고 있는것은 다음과 같다.

1. 환형큐
2. 우선큐

환형큐는 큐가 원형처럼 되어있으며, 큐의 끝부분의 다음이 자연스럽게 큐의 시작부분으로 연결된것을 말한다.

기억하기로는 네트워크에서 링버스였나… 그 형식이 사용하는걸로 알고 있긴한데.. 다시 봐야겠다. 암튼 작동 방식은 다음그림을 살펴보면 된다.

원형큐인만큼 큐가 비어있다는걸 확인하기 위해 두개의 포인터가 존재한다. 하나는 큐의 첫번째 요소를 가리키고 있으며, 다른 하나는 큐의 마지막 원소를 가리키고 있다.

두개의 포인터가 같은 위치라면 큐가 비어있는것이고, 리드 포인터 뒤에 라이트 포인터가 있다면, 큐가 꽉 차있는것이다.

이런 요소를 구현하기 위해서는 아래와 같은 로직이 필요하다.

//js
let rear = (rear+1)%Queue.length-1

이런 로직이 있다면, 큐의 끝에서 데이터를 추가했을때 자동으로 포인터가 0으로 바뀌게 된다.

---

우선큐는 큐다. 하지만 특징이 있다.

요소들에게 우선순위를 주어 가장 큰 우선순위가 먼저 제거되어야 한다 따라서 기본적인 큐에서 매번 새로운 요소가 들어올때마다 우선순위에따른 내림차순 정렬이 필요하다.

이런 우선큐는 컴퓨터에서 볼수 있다. 간단히 컴퓨터를 켜놓고 있다가 전원버튼을 꾹눌러 컴퓨터를 종료해 보도록 하자.

원래 큐에 다른 작업이 있었지만, 인터럽트가 걸려 원래 있던 작업이 종료되고, 시스템 종료가 최우선 작업으로 지정되고, 작업 큐에서 최우선으로 실행되어 컴퓨터가 종료되는 것이다.

사용처

이런 큐(일반큐)는 실생활 곳곳에서 볼수 있다.

1. 대기열
2. 편의점(선입 선출)
3. 컴퓨터
4. 인터넷 브라우저

인터넷 브라우저에서는 콜백 큐라는것이 존재한다. (크롬기준) 이 콜백 큐는 서버에 데이터를요청 등등의 비동기 작업이 있다면 사용된다.

우선 비동기 작업이란 파일 읽기, 서버 요청 등 시간이 오래걸리는 일들이 해당된다. 이러한 작업들은 완료되기까지 기다리는것은 매우 비효율적이다. 따라서 자바스크립트 엔진은 해당 작업을 요청하고 모든 작업이 끝난이후 요청이 완료된 작업을 실행한다.

이때 요청된 작업이 마무리되었을때 해당 작업들이 대기하는곳이 콜백 큐이다.

모든 작업이 완료된 이후, 자바스크립트 엔진은 콜백 큐에서 완료된 작업을 하나 가져와서 처리한다. 다시 모든 작업이 완료된이후 (정확히는 브라우저의 콜스택이 비워진 이후) 콜백 큐에 남은 작업이 있으면 다시 해당 작업을 가져와서 처리한다.

해당 과정을 콜스택이 전부 비워지고, 모든 작업이 완료될때 까지 반복하게 된다.

---

좀 날림으로 작성하긴 했지만, 브라우저의 특성을 설명해 보았다. 해당과정은 나중에 기회가 있다면, 이벤트 루프와 콜백 큐라는 이름으로 다시 블로깅을 진행해야겠다.