Stack & Queue ( 스택 & 큐)

 

 

Q1. Stack(스택)란?

-LIFO: 후입선출

 

 

 

- 삽입(push), 삭제(pop), 탐색(top) 3가지의 함수 모두 O(1)의 시간 복잡도

 

스택의 활용 예시

- 웹 브라우저 방문기록: 가장 나중에 열린 페이지부터 다시 보여준다

-역순 문자열 만들기: 가장 나중에 입력된 문자부터 출력한다

등이 있다 

 

 

이제 스택을 직접 구현해보자

코드는 자바스크립트로 구현하려고 한다

배열을 이용하려고 한다

class Stack {
    arr = [];

    push(value){
        return this.arr.push(value);
        //push 후 length값 리턴
    }

    pop(){
        return this.arr.pop();
        //pop 후 length값 리턴
    }
    
    top(){
        //return this.arr[this.arr.length-1];
        return this.arr.at(-1);
        //array.at() : 배열에서 해당 인덱스에 위치한 요소를 반환
    }

    get length(){
        return this.arr.length;
    }
}

 

실행 시켜보면...

const stack = new Stack();
stack.push(1); //[1]
stack.push(3); //[1,3]
stack.push(5); //[1,3,5]
stack.push(2); //[1,3,5,2]
stack.push(4); //[1,3,5,2,4]
console.log(stack.length); //5
console.log(stack.pop()); //4 [1,3,5,2]
console.log(stack.top()); //2 [1,3,5,2]

 

Q2. Queue(큐)란?

-FIFO: 선입선출

 

 

- 삽입(Enqueue), 삭제(Dequeue), 탐색(peek) 3가지 모두 O(1)의 시간 복잡도

-큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

 

이제 큐를 직접 구현해보자

마찬가지로 코드는 자바스크립트로 구현하려고 한다

이것도 마찬가지로 배열을 이용하였다

class Queue {
    arr = [];

    enqueue(value){
        return this.arr.push(value);
    }

    dequque(){
        return this.arr.shift();
    }

    peek(){
        return this.arr[0];
    }

    get length(){
        return this.arr.length;
    }
}

 

실행 시켜보면...

const queue = new Queue();
queue.enqueue(1); //[1]
queue.enqueue(3); //[1,3]
queue.enqueue(5); //[1,3,5]
queue.enqueue(2); //[1,3,5,2]
queue.enqueue(4); //[1,3,5,2,4]
console.log(queue.length); //5
console.log(queue.dequque()); //1 [3,5,2,4]
console.log(queue.peek()); //3 [3,5,2,4]