자료구조 Stack 과 Queue (2)

Queue 란?

Queue도 Stack과 비슷한 자료구조이지만 다른점이 있다.
Queue는 Stack과 다르게 먼저 들어간 것이 먼저 나오는 FIFO (First In First Out) 방식이다.
음 Stack과 연관 지어 말한다면 프링글스통 아랫부문이 뚫려있다고 생각하면 비슷하려나?

아래가 뚤려있으니 아래부터 꺼낼수 있다

다시 본론으로 들어가면

실생활에서 비슷한 사례로 대기줄을 생각해보면 이해가 쉬울 것 같습니다. 먼저 줄을 선사람이 먼저 서비스를 취하지 않나요?

큐의 뜻을 그대로 직역한다면 차례를 기다리는 사람이나 승용차의 열로 나오는 것을 알 수 있습니다.
위처럼 자료구조 큐도 먼저 들어간 데이터가 먼저 나오는 방식의 구조를 가지고 있습니다.

Queue 슈도코드

뒷포인터 = 0 , 앞포인터 = 0

1.enqueue
1.1. storage[뒷포인터] = 값을 넣어준다.
1.2. 뒷포인터 + 1

2.dequeue
2.1. storage[앞포인터] 값을 변수에 저장하고
2.2. storage[앞포인터] 를 삭제한다.
2.3. 앞포인터 + 1
2.4. 삭제값을 저장한 변수 반환

3. Size
3.1뒷포인터 - 앞포인터

자바스크립트에서 구현한 Queue

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.rear - this.front
  }

  enqueue(element) {
    this.storage[this.rear] = element
    this.rear++
  }

  dequeue() {
    let targetel = ''
        targetel = this.storage[this.front]

    if(this.front in this.storage){  
      delete this.storage[this.front]
    this.front++
     }
    return targetel
  }
}

배열로 어떻게 구현해야할지 생각이 잘안나 그냥 객체로 넣게 되었습니다... 나중에 익숙해지면 배열로 고쳐 놓겠습니다!

큐는 스택과 다르게 포인터가 front와 rear 두개로 나눠져 있는 것을 확인할 수 있다.

그림으로 설명한다면 위에 첫번째 포인터가 front 두번째 포인터가 rear을 나타낸다.
만약 enqueue로 B를 추가한다면

front 포인터는 그대로 있고 rear만 움진인 것을 확인할 수 있다.

만약 6개가 들어온 상태에서 dequeue() 를 실행한다면

front 포인트가 가르기는 처음으로 들어온 A가 제거되고 front 포인터가 한칸 이동 한것을 확인 할 수 있다!

코드를 실행시켰을 때로 본다면

Queue.enqueue('a')
Queue.enqueue('b')
Queue.enqueue('c')
console.log(Queue.storage) // {0 : 'a', 1 : 'b', 2 : 'c'}
stack.dequeue() // 'a'
console.log(Queue.storage) // {1 :'a', 2 : 'b'}

이와 같이 확인 할 수 있을 것 같다!