자료구조 스택/큐 개념과 구현 (with javaScript)

 

스택(Stack)과 큐(Queue)

 

 

스택과 큐는 기초적인 자료구조로 꼭 CS를 공부하지 않았어도 개발 공부를 하다 보면 한 번씩 들어보는 자료구조입니다.

실제 개발을 하면서 구현을 하기도 하며, 실 생활에서도 볼 수 있는 자료구조입니다. 많이 활용되고 유명하단 말이겠죠?

그리고 둘은 선형 데이터 구조로 선형구조는 데이터들이 일렬로 저장되어 있는 형태를 말합니다. 비슷한 점도 가지고 있지만

차이점도 있습니다. 스택과 큐의 개념과 몇 가지 대표적인 특성에 대해 알아보고 구현해보면서 비교해 보겠습니다.

 

Stack, Queue

스택(Stack)

---

특징

 

 

마지막에 들어온 게 먼저 나가는 Last In First Out 후입선출 구조를 가지고 있습니다. 데이터를 삽입하는 것을 Push,

삭제하는 것을 Pop이라 합니다. 스택에서 top이라는 포인터를 사용하는데 이는 마지막 요소를 추적하는데 쓰입니다.

 

간단하게 실 생활에서 예시를 들어보면 접시 스택을 생각해보면 됩니다. 접시를 닦고 하나씩 놓을 때 접시를 중간에 배치하지 않고

맨 위에다 추가(Push)합니다. 그리고 접시를 뺄 때는 가장 아래 거 먼저 빼지는 않죠. 맨 위에 있는 접시를 먼저 삭제(Pop)할 것입니다.

맨 위 접시를 삭제하면 포인터는 그다음 접시로 이동하게 됩니다. 이는 LIFO방식이며 몇 가지 활용 예시를 더 알아보겠습니다.

 

2를 가리키고 있는 포인터

 

활용

 

•   웹 브라우저 기록, 뒤로 가기나 앞으로 이동할 때 Push, Pop
•   Undo 실행 취소
•   데이터의 역순
•   재귀함수

 

구현 

 

JavaScript로 구현한 스택입니다. 메서드인 Push와 Pop을 이용하면 간단히 구현할 수 있습니다.

 

class Stack { // 스택 클래스 선언
  constructor() {
    this.arr = []; // 생성자 함수 선언 빈 스택
  }
  push(item) {
    this.arr.push(item); // 삽입
  }
  pop() {
    return this.arr.pop(); // 삭제
  }
  pointer() {
    return `Pointer :${this.arr[this.arr.length - 1]}`; // head의 위치 반환
  }
}

const stack = new Stack();
stack.push(1); // 1삽입
stack.push(2); // 2삽입
stack.push(3); // 3삽입
stack.pop(); // 3삭제
console.log(stack); // 1, 2
stack.push(4); // 4삽입
console.log(stack); // 1, 2 , 4
console.log(stack.pointer()); //  4를 가리키는 포인터

 

 

큐(Queue)

---

특징

 

먼저 들어온 게 먼저 나가는 First In First Out 선입선출 구조를 가지고 있습니다. 데이터를 집어넣는 enqueue, 삭제하는

dequeue 작업이 가능합니다. 스택처럼 큐에서도 핵심이 되는 포인터가 있는데 front와 rear입니다. 큐에서 가장 처음 원소를

가리키는 포인터인 front, 가장 마지막 원소를 가리키는 포인터 rear입니다.

 

front, rear

 

스택과는 다르게 먼저 들어온 게 먼저 빠져나가는 구조라, 서로 상반되는 구조를 가집니다. 그래서 일상에서 쉽게 접할 수 있습니다.

예로 대기열로 제일 먼저 도착한 사람이 제일 먼저 서비스를 받을 수 있습니다. 이는 FIFO방식이며 몇 가지 활용 예시를 더 알아보겠습니다.

 

활용

 

•   대기열(은행, 서비스 센터, 음식점, 전화 상담)
•   마트, 편의점, 유통업체에서 선입선출 (유통기한)
•   우선순위 같은 작업 (프린터 대기열)
•   스케줄링 알고리즘(FCFS.. )

 

구현

 

JavaScript로 구현한 큐입니다. 메서드인 Push와 Shift를 이용하면 간단히 구현할 수 있습니다. 여기서 스택과 차이점은

Pop이 아니라 Shift를 사용하여 데이터를 삭제하는데 Shift는 배열의 맨 앞에 있는 값을 제거합니다.

 

class Queue {
  // 클래스 선언
  constructor() {
    // 생성자 함수 선언
    this.arr = [];
  }
  enqueue(item) {
    //삽입
    this.arr.push(item);
  }
  dequeue() {
    //삭제
    return this.arr.shift();
  }
}

const queue = new Queue();
queue.enqueue(1); // 1삽입
queue.enqueue(2); // 2삽입
queue.enqueue(3); // 3삽입
queue.dequeue(); // 1

console.log(queue); // 2 , 3