[자료구조/JS] 스택(Stack)과 큐(Queue)

기본적이고 가장많이 사용되는 자료구조,
선형과 비선형 중 선형구조인 스택과 큐부터 알아본다.

1. 스택(Stack)이란?

스택(Stack)은 사전적으로는 '쌓다' 라는 의미를 가지며, 아래가 막힌 저금통처럼 하나의 입구만 가지고 있다.

• 가장 최근에 들어간 데이터가 먼저 나오는 선형(liner)자료구조이다.
• LIFO(Last In, First Out) 또는 FILO(First In, Last Out) 데이터 관리방식을 따른다.

1-1. 주요기능

• push() : 데이터를 스택에 넣기

• pop() : 데이터를 스택에서 꺼내기
  
  

1-2. 사용되는 경우

• 서로 관계가 있는 여러작업들을 연달아 수행하며 이전의 작업내용을 저장해 둘 필요가 있는 경우
• 대표적인 스택의 활용 : 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
  
  

1-3. JS 구현

class Stack {
  constructor() {
    this.arr = [];
  }
  push(item) {
    this.arr.push(item);
  }
  pop() {
    return this.arr.pop();
  }
  peek() {
    return this.arr[this.arr.length - 1];
  }
  clear() {
    this.arr = [];
  }
}


const stack = new Stack;

//데이터 삽입
stack.push(1);
stack.push(2);
stack.push(5);
stack.push(10);
console.log(stack); // Stack{ arr: [1, 2, 5, 10] }


// 데이터 추출
stack.pop(); // 10
console.log(stack); // Stack{ arr: [1, 2, 5] }


// 다음에 추출될 데이터 조회 (현재 입구에 가장 가까운 데이터)
stack.peek(); // 5
console.log(stack); // Stack{ arr: [1, 2, 5] }


// 스택 초기화
stack.clear();
console.log(stack); // Stack{ arr: [] }

1-4. 스택(Stack)의 시간복잡도

1-5. 스택(Stack) 관련 알고리즘 문제 풀어보기

[백준]스택(Stack) 관련 알고리즘 문제들 : https://www.acmicpc.net/step/11

참조
https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D
https://helloworldjavascript.net/pages/282-data-structures.html
https://khwan.kr/blog/javascript/2020-03-14-queue-stack
https://overcome-the-limits.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-with-JavaScript

2. 큐(Queue)란?

• 먼저 들어간 데이터부터 차례대로 나오는 선형(liner)자료구조이다.
• FIFO(First In, First Out) 또는 LILO(Last In, Last Out) 데이터 관리방식을 따른다.

큐(Queue)는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 뜻하기도 한다. 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.
출입구가 하나인 스택(Stack)과는 반대로 한쪽 끝 입구에서 데이터가 삽입되고 그 반대쪽 끝 출구에서 데이터가 삭제된다.

이렇게 새치기하면 안❌돼❌요!

2-1. 주요기능

• push() : 데이터를 큐에 넣기 (enqueue)
• shift() : 데이터를 큐에서 꺼내기 (dequeue)

2-2. 사용되는 경우

• 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로서 많이 사용된다.

2-3. JS 구현

class Queue {
  constructor() {
    this.arr = [];
  }
  enqueue(item) { 
    this.arr.push(item);
  }
  dequeue() {
    return this.arr.shift();
  }
  peek() {
    return this.arr[0];
  }
  clear() {
    this.arr = [];
  }
}

const queue = new Queue();

// 데이터 삽입
queue.enqueue(1);
queue.enqueue(3);
queue.enqueue(7);
console.log(queue); // Queue{ arr: [1, 3, 7] }

// 데이터 추출
queue.dequeue(); // 7
console.log(queue); // Queue{ arr: [1, 3,} }


// 다음에 추출될 데이터 조회 (현재 출구에 가장 가까운 데이터)
queue.peek(); // 1
console.log(queue); // Queue{ arr: [1, 3] }


// 큐 초기화
queue.clear();
console.log(stack); // Queue{ arr: [] }

2-4. 큐(Queue)의 시간복잡도

2-5. 큐(Queue) 관련 알고리즘 문제 풀어보기

참조 https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)
https://overcome-the-limits.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90-with-JavaScript