스택과 큐

스택(stack)

스택은 자료 구조의 일종으로, 마지막에 삽입된 항목만을 제거하고 접근할 수 있다.

후입선출LIFO, last in first out

속도가 빠르다는 점이 장점. 찾기와 삽입이 상수 시간인 O(1)

자바스크립트에서 배열에는 스택 클래스를 정의한 pop과 push라는 메소드가 있다.

 

기본 뼈대 코드

function Stack(array) {
    this.array = [];
    if (array) this.array = array;
}

Stack.prototype.getBuffer = function() {
    return this.array.slice();
}

Stack.prototype.isEmpty = function() {
    return this.array.length == 0;
}

//instance of the stack class
var stack1 = new Stack();

console.log(stack1); // {array: []}

 

들여다보기

Stack.prototype.peek = function() {
    return this.array[this.array.length - 1];
}
stack1.push(10);
console.log(stack1.peek()); // 10
stack1.push(5);
console.log(stack1.peek()); // 5

 

삽입

Stack.prototype.push = function(value) {
    this.array.push(value);
}

stack1.push(1);
stack1.push(2);
stack1.push(3);
console.log(stack1); // {array: [1,2,3]}

 

삭제

Stack.prototype.pop = function() {
    return this.array.pop();
};

stack1.pop(1);
stack1.pop(2);
stack1.pop(3);

console.log(stack1); // {array: []}

 

접근

function stackAccessNthTopNode(stack, n) {
    if (n <= 0) throw 'error'
    
    var bufferArray = stack.getBuffer();
    var bufferStack = new Stack(bufferArray);

    while (--n !== 0) {
        bufferStack.pop();
    }
    return bufferStack.pop();
}

var stack2 = new Stack();
stack2.push(1);
stack2.push(2);
stack2.push(3);
stackAccessNthTopNode(stack2, 2); // 2

 

검색

function stackSearch(stack, element){
    var bufferArray = stack.getBuffer();

    var bufferStack = new Stack(bufferArray);

    while(!bufferStack.isEmpty()){
        if(bufferStack.pop()==element){
            return true;
        }
    }
    return false;
}
var stack3 = new Stack();
stack3.push(1);
stack3.push(2);
stack3.push(3);
stackSearch(stack3,3); // true

큐

 

function Queue(array) {
    this.array = [];
    if (array) this.array = array;
}

Queue.prototype.getBuffer = function() {
    return this.array.slice();
}

Queue.prototype.isEmpty = function() {
    return this.array.length == 0;
}

//instance of the queue class
var queue1 = new Queue();

console.log(queue1); // { array: [] }

 

들여다보기

Queue.prototype.peek = function() {
    return this.array[0];
}

 

삽입

Queue.prototype.enqueue = function(value) {
    return this.array.push(value);
}

 

삭제

Queue.prototype.dequeue = function() {
    return this.array.shift();
};

var queue1 = new Queue();

queue1.enqueue(1);
queue1.enqueue(2);
queue1.enqueue(3);

console.log(queue1); // {array: [1,2,3]}

queue1.dequeue();
console.log(queue1); // {array: [2,3]}

queue1.dequeue();
console.log(queue1); // {array: [3]}

 

접근

function queueAccessNthTopNode(queue, n) {
    if (n <= 0) throw 'error'

    var bufferArray = queue.getBuffer();
    var bufferQueue = new Queue(bufferArray);

    while (--n !== 0) {
        bufferQueue.dequeue();
    }
    return bufferQueue.dequeue();
}

 

검색

function queueSearch(queue, element) {
    var bufferArray = queue.getBuffer();

    var bufferQueue = new Queue(bufferArray);

    while (!bufferQueue.isEmpty()) {
        if (bufferQueue.dequeue() == element) {
            return true;
        }
    }
    return false;
}