🥑 큐 (Queue), 스택(Stack)

🥑 스택 (Stack)

 

스택(Stack)이란 "쌓다"라는 뜻을 갖고 있습니다.

말 그대로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다.

Stack

스택의 가장 큰 특징은 LIFO (Last In First Out) , 후입선출 구조입니다.

가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 갖고 있죠.

 

그릇을 쌓아 놓는 것을 스택의 예시로 보면 쉬울 것 같습니다.

 

또한 스택은 정해진 방향으로만 쌓을 수 있으면, top으로 정한 곳을 통해서만 접근 가능합니다. 

새로 삽입되는 자료는 top을 통해 쌓이게 되며 (Push), 자료를 삭제할 때도 top을 통해 삭제가 가능합니다. (Pop)

 

스택의 사용 사례

 

▶ 웹 브라우저 방문 기록 ( 뒤로 가기 ) 

▶ 실행 취소 ( ctrl + z )

▶ 후위 표기법 계산

 

💻 스택 (Stack) JavaScript 구현

 

스택은 사실 자바스크립트에서 구현이 쉽습니다. pop(), push() 메서드가 있기 때문이죠.

그래도 저희는 원리를 공부하기 위해! 기능을 구현한 코드를 공부해보도록 해요.

 

top은 스택이 공백 상태일 때, -1입니다. Push를 하게 되면, top 에 1을 더해주고, 그 자리에 data를 넣어줍니다.

top 인덱스 값의 data를 반환하고 null로 바꿔주며, top에서 1을 빼줍니다.

top의 인덱스 값이 스택의 마지막 인덱스 값과 같다면 스택은 포화 상태입니다!

var Stack = function (stackSize) {
    // Array 객체 생성
    this.stack = [];
    // Top (데이터 삽입, 삭제)
    this.top = -1;
    // 스택의 크기
    this.stackSize = stackSize;
    // 스택 초기화
    for (var index = 0; index < stackSize; index++) {
        this.stack.push(null);
    }
    // Push
    this.push = function (data) {
        var result = true;
        if (this.isFull()) {
            console.log("Stack Full");
            result = false;
        } else {
            this.top++;
            this.stack[this.top] = data;
        }
        return result;
    }
    // Pop
    this.pop = function () {
        var result = null;
        if (this.isEmpty()) {
            console.log("Stack Empty");
        } else {
            result = this.stack[this.top];
            this.stack[this.top] = null;
            this.top--;
        }
        return result;
    }
    // 스택에 데이터가 공백 상태인지 확인하는 함수
    this.isEmpty = function () {
        return (this.top == -1);
    }
    // 스택에 데이터가 포화 상태인지 확인하는 함수
    this.isFull = function () {
        return (this.top == this.stackSize - 1);
    }
    // 스택 정보 출력 함수
    this.consoleLog = function () {
        console.log(this.stack);
        console.log("top: " + this.top);
    }
}
//출처 : 눈으로 개발하는 블로그

스택의 길이 만큼 null을 배열에 삽입해주고 초기화해줍니다.

 

▶ this.push(data) 

: isFull()를 통해 스택이 포화 상태면 "Stack  Full" 이라는 알림과 함께 false를 반환해줍니다.

포화 상태가 아니면, top에 1을 더해주고, 그 자리에 data를 넣어줍니다. 그리고 true를 반환합니다.

 

▶ this.pop() 

: isEmpty() 함수를 통해 스택이 공백 상태인지 확인하고 공백상태라면, "Stack Empty" 알림과 함께 null을 반환합니다.

공백 상태가 아니라면, top에 있는 data를 반환하고, 그 자리를 null로 바꿔주며, top에서 1을 빼줍니다.

 

▶ this.isEmpty() 

: 스택이 공백 상태인지 확인해주는 함수입니다. top의 인덱스 값이 -1이라면, true를 반환합니다. 

 

▶ this.isFull() 

: 스택이 포화상태인지 확인해주는 함수입니다. 스택의 마지막 인덱스 값과 top의 인덱스 값이 같다면 true를 반환합니다.

 

 

⌚ 스택 Stack 시간복잡도 (Big O notation)

• Push(삽입) O(1)
• Pop(삭제) O(1)
• Search(검색) O(n)

 

 

 

------------------------------------------------------------------------------------------------------------------

 

🥑 큐 (Queue)

Queue

큐 (Queue)는 스택과 다르게 한쪽 방향에서 삽입이 이루어지고, 다른 쪽 방향에서 삭제가 이루어지는 자료구조입니다.

선입선출, FIFO(First In First Out) 의 구조를 갖고 있습니다.

 

은행 창구에서 번호표를 뽑아서 대기하는 것을 예시로 들면 좋겠네요.

 

삭제 연산이 수행되는 곳이 Front (Head), 삽입 연산이 이루어지는 곳이 Rear (Tail) 입니다.

그리고, Rear에서 이루어지는 삽입 연산을 인큐 (Enqueue)라고 부르며,

Front에서 이루어지는 삭제 연산을 디큐(Dequeue)라고 부릅니다.

 

큐의 사용 사례

 

▶ 은행 업무

▶ 대기열 순서와 같은 우선 순위의 작업 예약

▶ 프로세스 관리

 

💻 큐 (Queue) JavaScript 구현

 

Queue도 마찬가지로 자바스크립트에서는 기능 구현이 쉽습니다.

let queue = [];

queue.push(1);
queue.push(2); // Enqueue

let n = queue.shift(); // Dequeue

그러나 원리를 좀 더 정확히 이해하기 위해 기능을 직접 함수를 사용하여 구현해보겠습니다.

 

 

파란색 화살표가 Front, 주황색 화살이 Rear 입니다. 

데이터를 삽입하는 위치를 Rear로 설정하고, 데이터를 삭제하는 위치를 Front로 설정합니다.

데이터를 넣는 함수를 Enqueue, 데이터를 출력하는 함수를 Dequeue 라고 할게요. 

 

 

 

var Queue = function (queueSize) {
    // Array 객체 생성
    this.queue = [];
    // Front (데이터 삽입)
    this.front = -1;
    // Rear (데이터 삭제)
    this.rear = -1;
    // 큐의 크기
    this.queueSize = queueSize;
    // 큐 초기화
    for (var index = 0; index < queueSize; index++) {
        this.queue.push(null);
    }
    // Enqueue
    this.enqueue = function (data) {
        var result = true;
        if (this.isFull()) {
            console.log("Queue Full");
            result = false;
        } else {
            this.rear++;
            this.queue[this.rear] = data;
        }
        return result;
    }
    // Dequeue
    this.dequeue = function () {
        var result = null;
        if (this.isEmpty()) {
            console.log("Queue Empty");
        } else {
            this.front++;
            result = this.queue[this.front];
            this.queue[this.front] = null;
            if (this.isEmpty()) {
                // 위치 초기화
                this.front = -1;
                this.rear = -1;
            }
        }
        return result;
    }
    // 큐에 데이터가 공백 상태인지 확인하는 함수
    this.isEmpty = function () {
        return (this.front == this.rear);
    }
    // 큐에 데이터가 포화 상태인지 확인하는 함수
    this.isFull = function () {
        return (this.rear == this.queueSize - 1);
    }
    // 큐 정보 출력 함수
    this.consoleLog = function () {
        console.log(this.queue);
        console.log("front: " + this.front + ", rear: " + this.rear);
    }
}
//출처 :  눈으로 개발하는 블로그

큐가 처음 생성될 때, Front 와 Rear의 위치가 둘 다 -1 입니다. 데이터를 추가하면 Rear의 위치에 1이 더해지고 데이터를 출력하면 Front의 위치에 1이 더해집니다. 

 

큐의 사이즈를 인수로 받고 큐를 초기화 해줍니다! (반복문을 통해 null을 삽입)

 

▶ this.enqueue(data) 

: isFull() 함수를 통해 큐가 포화 상태면 "Queue Full" 알림과 함께 false를 반환합니다.

 포화 상태가 아니면 rear에 1을 더해주고 그 인덱스 값에 data를 삽입합니다. 그리고 true 를 반환합니다.

 

▶ this.dequeue()

: isEmpty() 함수를 통해 큐가 공백 상태면 "Queue Empty" 알림과 함께 null을 반환합니다.

공백 상태가 아니면, front에 1을 더해주고 그 인덱스 값을 result로 반환하고, 그 자리에 null을 삽입합니다.

그후, 큐가 공백 상태면 다시 초기화 해줍니다. (front와 rear을 -1로 초기화)

 

▶ this.isEmpty()

: 만약 front와 rear의 값이 같다면 true를 반환해줍니다.

 

▶ this.isFull()

: 만약 큐의 마지막 인덱스 값이 rear와 같다면 true를 반환해줍니다.

 

 

⌚ 큐 Queue 시간복잡도 (Big O notation)

• Enqueue(삽입) O(1)
• Dequeue(삭제) O(1)
• Search(검색) O(n)