자료구조, 큐(Queue) 와 스택(Stack)

Queue 란 무엇인가?

Queue(큐) 란 컴퓨터의 기본적인 자료 구조 중 하나로 항상 또 다른 구조 스택과 비교가 되는 자료 구조 중 하나이다. 일단 Quese 는 FIFO 라고 표현 한다. FIFOFirst in first out 이다. 말 그대로 먼저 들어온 것이 먼저 나간다.

Queue 의 사전적 의미로는 1. (무엇을 기다리는 사람자동차 등의) 줄 2. 대기 행렬 3. 줄을 서서 기다리다 등이 있다.

우리가 일상생활에서 흔히 볼 수 있는 놀이 동산이나 은행에서 먼저 들어온 사람이 먼저 창구나 입장을 하는 것과 같다고 보면 된다. Javascript 를 이용해서 보면 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
(function Queue () {
var queue = [];

function enqueue (item) {
queue.push(item);
}

function dequeue () {
if (queue.length === 0) {
return undefined;
}
return queue.shift();
}
function peek () {
return queue.length === 0 ? null : queue[0];
}

enqueue(1);
console.log(queue); // [1]
console.log(peek()); // 1
enqueue(3);
console.log(queue); // [1 ,3]
console.log(peek()); // 1
enqueue(5);
console.log(queue); // [1,3,5]
console.log(peek()); // 1
dequeue();
console.log(queue); // [3,5]
console.log(peek()); // 3
dequeue();
console.log(queue); // [5]
console.log(peek()); // 5
dequeue();
console.log(queue); // []
console.log(peek()); // null
dequeue();
console.log(queue); // []
console.log(peek()); // null

})();

우리가 흔히 사용하는 array 메소드인 push 와 shift 를 이용하면 간단하게나마 queue 에 대한 예제를 이해볼 수 있다.

Stack 이란 무엇인가?

Stack 은 Queue 와는 반대의 개념이라고 생각하면 된다. LIFO 로 표현이 되며 이는 Last in first out 으로서, 나중에 들어온 것이 먼저 나간다 라는 뜻이다.

Stack 의 사전적 의미로는 (보통 깔끔하게 정돈된) 무더기 이다.

우리의 일상과 대입해서 본다고 한다면 우리가 흔히 하는 ctrl + z 혹은 command + z 와 같이 실행 취소 혹은 책을 쌓아 두고 치우는 형태라고 보면 이해 하기가 편하다. 만약 우리가 엑셀을 켜두고 1. 표 삽입, 2. 글 쓰기, 3. 링크 삽입 순으로 작업을 했다고 가정했을 때 실행 취소(ctrl + z 혹은 command + z) 을 눌렀을 때 우리가 실행한 액션의 거꾸로인 3. 링크 삽입, 2. 글 쓰기, 1. 테이블 삽입 순으로 취소 될 것이다. 이와 같이 stack 은 나중에 들어온 것이 먼저 나간다라고 생각하면 된다.

Stack 을 자바스크립트 코드로 작성한다면 다음과 같을 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
(function Stack () {
var stack = [];

function push (item) {
stack.push(item);
}

function pop () {
if (stack.length === 0) {
return undefined;
}
return stack.pop();
}
function peek () {
return stack.length === 0 ? null : stack[0];
}

push(1);
console.log(stack); // [1]
console.log(peek()); // 1
push(3);
console.log(stack); // [1 ,3]
console.log(peek()); // 1
push(5);
console.log(stack); // [1,3,5]
console.log(peek()); // 1
pop();
console.log(stack); // [1, 3]
console.log(peek()); // 1
pop();
console.log(stack); // [1]
console.log(peek()); // 1
pop();
console.log(stack); // []
console.log(peek()); // null
pop();
console.log(stack); // []
console.log(peek()); // null

})();

Thanks for your reading, this article is provided by Martin If reproduced, please indicate the source:Martin(https://github.com/martinYounghoonKim
Reflow 와 Repaint
S3를 이용한 웹 어플리케이션 올리기