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

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

  • 2018-08-27

Queue 란 무엇인가?

Queue(큐) 란 컴퓨터의 기본적인 자료 구조 중 하나로 항상 또 다른 구조 스택과 비교가 되는 자료 구조 중 하나이다. 일단 Quese 는 FIFO 라고 표현 한다. FIFO 란 First 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
    
})();

현재 이커머스회사에서 frontend 개발자로 업무를 진행하고 있는 Martin 입니다. 글을 읽으시고 궁금한 점은 댓글 혹은 메일(hoons0131@gmail.com)로 연락해주시면 빠른 회신 드리도록 하겠습니다. 이 외에도 네트워킹에 대해서는 언제나 환영입니다.：Martin（https://github.com/martinYounghoonKim）
Reflow 와 Repaint
S3를 이용한 웹 어플리케이션 올리기