스택과 큐(Stack, Queue)

 

집어 넣은 데이터에서

처음에 넣은 것을 가져가느냐

마지막에 넣은 것을 가져가느냐

 

두가지의 경우에 따라서 자료구조가 달라집니다.

 

 

Stack (마지막)

쌓여있는 접시에서 가장 위에 있는 접시를 먼저 닦아야 하듯이 마지막 요소를 먼저 가져옵니다.

 

Queue (처음)

놀이기구를 타기위해 가장 먼저 온 첫 손님이 가장 먼저 놀이기구를 타듯이 첫 요소를 먼저 가져옵니다.

 

 

 

In Javascript

자바 스크립트에서 어떻게 구현될 수 있을까요.

 

Stack

push 메서드로 요소들이 객체 형태로 storage에 들어갑니다. storage에 들어가는 객체의 key 는 숫자, value 는 요소입니다. 객체 key의 숫자는 데이터의 크기를 알 수 있는 top 을 참조합니다. 만약에 요소가 push 를 통해서 추가된다면, top 의 값이 증가하고 동시에 값이 요소의 key 가 됩니다. 또한, pop 메서드로 요소를 가져온다면, top의 값과 같은 key 값을 가진 요소를 리턴하며 top 의 값이 감소합니다.

class Stack {
  constructor() {
    //요소들을 담을 객체
    this.storage = {};
    //가장 위에 있는 요소의 인덱스
    this.top = 0;
  }

  //저장된 데이터의 크기를 반환
  size() {
    return this.top;
  }

  //요소(element)를 객체형태로 저장
  push(element) {
    this.top += 1; 
    this.storage[this.top] = element;
  }
     
  //가장 최근에 추가한 요소를 리턴
  pop() {
    if (this.top !== 0) {
      let deleted = this.storage[this.top];
      delete this.storage[this.top];
      this.top -= 1;
      return deleted;
    }
  }
}

let stackIt = new Stack;

 

push 메서드를 통해서 요소들이 순차적인 key 를 가지고 저장됩니다. pop 메서드를 통해서 출력되는 값을 보면 마지막에 들어간 요소인 것을 볼 수 있습니다. 

stackIt.push('A');
stackIt.push('B');
stackIt.push('C');
stackIt.storage	 //{1: 'A', 2: 'B', 3: 'C'}

stackIt.pop();	 // 'C'
stackIt.pop();	 // 'B'
stackIt.storage	 //{1: 'A'}

 

---

 

 

Queue

enqueue 메서드로 요소들이 객체 형태로 storage 에 들어갑니다. storage 에 들어가는 객체의 key 는 숫자, value 는 요소입니다. 객체 key의 숫자는 가장 뒤에 있는 요소의 인덱스를 알 수 있는 rear 를 참조합니다. 만약에 요소가 enqueue 를 통해서 추가된다면, rear 값을 key 로 가진 요소가 저장되고 rear의 값이 증가합니다. 만약에, dequeue 메서드로 요소를 가져온다면, front 값을 가진 요소를 반환하며 front 값이 증가하여 가장 앞에 있는 요소의 key 를 나타내어 줍니다. 

class Queue {
  constructor() {
    //요소들을 담을 객체
    this.storage = {};
    //가장 앞의 인덱스
    this.front = 0;
    //가장 뒤의 인덱스
    this.rear = 0;
  }

  //저장된 데이터의 크기를 반환
  size() {
    return (this.rear - this.front);
  }

  //요소(element)를 객체형태로 저장
  enqueue(element) {
    //삽입
    //this.storage의 key는 this.rear+1, value는 element
    this.storage[this.rear] = element;
    this.rear += 1;
  }

  //가장 먼저 추가한 요소를 반환
  dequeue() {
    if(this.size() !== 0){
      let deleted = this.storage[this.front];
      this.storage[this.front] = undefined;
      this.front += 1;
      return deleted;
    }
  }
}

let queue = new Queue;

 

enqueue 메서드를 통해서 요소들이 순차적인 key 를 가지고 저장됩니다. dequeue 메서드를 통해서 출력되는 값을 보면 처음에 들어간 요소인 것을 볼 수 있습니다. 

queue.enqueue('A');
queue.enqueue('B');
queue.enqueue('C');
queue.storage	  //{1: 'A', 2: 'B', 3: 'C'}

queue.dequeue();  // 'A'
queue.dequeue();  // 'B'
queue.storage	  //{1: undefined, 2: undefined, 3: 'C'}

 

dequeue 메서드로 값을 반환받은 후에 storage 를 확인하면 앞에 빈공간이 보입니다. 만약에 저장하는 요소의 수와 반환받은 요소의 수가 늘어간다면 빈 공간도 늘어가게 됩니다. 이 문제를 해결한 자료구조가 원형 큐 (Circular Queue) 입니다.

 

 

Circular Queue