[JS Deep Dive] 27장 - 배열 (3)-스택, 큐 자료구조

1. 스택구조

• push 메서드와 pop 메서드를 통해 쉽게 구현 가능
• 스택은 한 방향으로 데이터를 넣고 뺄 수 있는 자료구조
• 먼저 들어간 자료가 나중에 나오는 후입선출 자료구조로, LIFO(Last In First Out) 방식
• 언제나 가장 마지막에 밀어넣은 최신 데이터를 먼저 취득한다. 
• 스택은 top에 바로 접근 가능하기 때문에 삽입, 삭제의 시간 복잡도는 O(1). 
• top은 가장 끝쪽에 위치한 데이터를 가리키며 push는 top에 새로운 데이터를 추가하고, pop은 top을 추출

📌 스택 활용 예시
후입선출 특징으로 여러 분야에서 활용

웹 브라우저 방문기록(뒤로가기)
실행 취소(undo)
역순 문자열 만들기
후위 표기법 계산

이미지 출처:https://velog.io/@nomadhash/Data-Structure-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EB%A1%9C-%EC%8A%A4%ED%83%9D-Stack-%ED%81%90Queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

 

//생성자함수
const Stack = (function () {
  function Stack(array = []) {
    if (!Array.isArray(array)) {
      throw new TypeError(`${array} is not an array.`);
    }
    this.array = array;
  }
  Stack.prototype = {
    constructor: Stack,
    // 스택의 가장 마지막에 데이터를 밀어 넣는다.
    push(value) {
      return this.array.push(value);
    },
    // 스택의 가장 마지막 데이터, 즉 가장 나중에 밀어 넣은 최신 데이터를 꺼낸다.
    pop() {
      return this.array.pop();
    },
    // 스택의 복사본 배열을 반환한다.
    entries() {
      return [...this.array];
    },
  };
  return Stack;
})();

const stack =new Stack([1,2]);
console.log(stack.entries()); //[1,2]

stack.push(3);
console.log(stack.entries()); //[1,2,3]

stack.pop();
console.log(stack.entries()); //[1,2]

 

 

//클래스
class Stack {
    constructor() {
        this.stackArr = [];
        this.top = 0;
    }
    push(value) {
        this.stackArr[this.top] = value;
        this.top += 1;
        return value;
    }
    pop() {
        if(this.top === 0) {
            console.log('배열이 비었습니다');
            return null;
        }
        this.top -= 1;
        return this.stackArr.pop();
    }
    getsize() {
        return this.stackArr.length;
    }
}

const stack = new Stack;
stack.push(1);
stack.push(2);
console.log(stack.stackArr); //[1,2]
console.log(stack.getsize()); //2
stack.pop();
console.log(stack.stackArr); //[1]
stack.pop();
console.log(stack.stackArr); //[]
stack.pop(); //배열이 비었습니다.
console.log(stack.getsize()); //0

 

---

2. 큐 구조

• shift 메서드와 push 메서드를 사용하여 쉽게 구현 가능
• 데이터를 마지막에 밀어넣고 처음 데이터, 즉 가장 먼저 밀어넣은 데이터를 먼저 꺼내는 선입선출(FIFO-first in first out) 방식
• 큐는 한쪽 방향으로 데이터를 넣고 다른 한쪽 방향으로 데이터를 뺄 수 있음

📌큐 활용 예시
선입선출 특징으로 순서대로 처리해야 하는 경우 활용

프린터의 인쇄 대기열
은행 업무
너비 우선 탐색(BFS)
콜센터 고객 대기 시간
캐시(Cache) 구현
선입선출이 필요한 대기열 (티켓 카운터)

이미지 출처: https://velog.io/@nomadhash/Data-Structure-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EB%A1%9C-%EC%8A%A4%ED%83%9D-Stack-%ED%81%90Queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

//생성자함수
const Queue= (function (){
    function Queue(array=[]){
        if(!Array.isArray(array)){
            throw new TypeError(`${array} is not an array.`);
        }
        this.array=array;
    }

    Queue.prototype={
        constructor:Queue,
        //큐의 가장 마지막에 데이터를 밀어 넣는다.
        enqueue(value){
            return this.array.push(value);
        },
        //큐의 가장 처음 데이터, 즉 가장 먼저 밀어 넣은 데이터를 꺼낸다.
        dequeue(){
            return this.array.shift();
        },
        //큐의 복사본 배열을 반환한다.
        entries(){
            return [...this.array];
        }
    }
return Queue;
}());

const queue=new Queue([1,2]);
console.log(queue.entries()); // [1,2]

queue.enqueue(3);
console.log(queue.entries()); // [1,2,3]

queue.dequeue();
console.log(queue.entries()); // [2,3]

 

//클래스
class Que {
    constructor() {
        this.head = 0;
        this.tail = 0;
        this.queArr = [];
    }
    isEmpty() {
        return this.tail === this.head;
    }
    front() {
        if(this.isEmpty()) {
            console.log('큐가 비어있습니다');
            return null;
        } 
        return this.queArr[this.head];
    }
    back() {
        if(this.isEmpty()) {
            console.log('큐가 비어있습니다');
            return null;
        }
        return this.queArr[this.tail-1];
    }
    enque(value) {
        this.queArr[this.tail] = value;
        this.tail++;
    }
    deque() {
        if(this.isEmpty()){
            console.log('큐가 비어있습니다');
            return null;
        }
        const dequeValue = this.queArr[this.head];
        this.head++;
        return dequeValue;
    }
    getsize() {
        return this.tail-this.head;
    }
}

const que = new Que;
que.enque(2)
que.enque(1)
console.log(que.getsize()); //2
console.log(que.deque()); //2
// {head:1 tail:2}
console.log(que.getsize()); //1
console.log(que.deque()); //1
// {head:2 tail:2}
console.log(que.getsize()); //0
console.log(que.deque()); //큐가 비었습니다. null

 

 

reference

https://velog.io/@hichulog/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-JS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8A%A4%ED%83%9D-%ED%81%90