IT,프로그래밍/알고리즘

[자료구조] 큐(Queue)란?

자료구조에서 스택과 함께 가장 많이 볼수있는 선형구조 입니다.

스택이 한쪽이 막혀있는 프링글스를 생각하신다면, 큐는 놀이동산에서 기다리는 줄을 생각하시면 이해하기가 수월합니다.

 

혹시 스택에 관하여 개념이 헷갈리시는분은 전에 써놓은 스택에 대한 글을 읽어보시는걸 추천드립니다

https://burning-camp.tistory.com/66

 

큐는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 혹은 선입선출이라고 합니다.

즉, 스택이랑 다르게 먼저 들어간게 먼저 나오는 구조입니다.

 

큐에는 몇가지 대표적인 행동(함수)가 있습니다

  • Enqueue : 큐의 맨뒤에 data를 넣는다 (대기줄 맨끝에서 기다린다)
  • Dequeue : 큐의 맨앞에 data를 뺴낸다 (대기줄 맨 앞에서 입장한다)
  • peek : 큐의 맨위의 data 를 조회한다 (대기줄 맨 앞을 살펴본다)

이해를 돕기 위해 아래의 이미지를 보시면 좋습니다!

 

이제 큐를 실제로 구현해 보도록 하겠습니다

 

큐는 2개의 스택을 이용해서 구현할수 있는데 먼저 아래의 코드를 보겠습니다.

 

class Queue {
  constructor(items) {
    if (items) {
      this.inbox = new Stack(items);
    } else {
      this.inbox = new Stack();
    }
    this.outbox = new Stack();
  }

  enqueue(item) {
    this.inbox.push(item);
    return true;
  }
  dequeue() {
    const inboxSize = this.inbox.size();
    for (let i = 0; i < inboxSize; i++) {
      this.outbox.push(this.inbox.pop());
    }
    const firstItem = this.outbox.pop();
    for (let i = 0; i < inboxSize - 1; i++) {
      this.inbox.push(this.outbox.pop());
    }
    return firstItem;
  }
  peek() {
    return this.inbox.peek();
  }
 }    

 

Queue는 2개의 스택으로 만들어진다고 말씀드렸는데 아래와 같은 용도로 쓰여집니다.

 

  • Inbox(오리지널) - 실제 데이터가 들어가 있는 스택
  • Outbox(임시) - Dequeue에서 쓰일 임시 스택

 

큐는 선입선출, 즉 Inbox 스택의 맨앞(프링글스통 맨아래의 감자칩)의 데이터를 뽑아내야하는데(Dequeue) 이것을 구현하기 위해서 입니다.

 

  1. Indox = [1,2,3,4]의 스택이 들어있습니다. -> Inbox = [1,2,3,4] | Outbox = []
  2. Inbox의 데이터 수만큼 pop해서 Outbox에 넣습니다. -> Inbox = [] | Outbox = [4,3,2,1]
  3. 이때 Outbox는 Inbox의 데이터가 역순으로 들어가게 됩니다.
  4. Outbox에서 pop을 합니다. 이 pop을 한 데이터가 큐의 가장 맨앞의 데이터 입니다 -> Inbox = [] | Outbox = [4,3,2] | data : 1
  5. 그리고 Outbox의 데이터 수만큼 pop해서 Inbox에 넣습니다. -> Inbox = [2,3,4] | Outbox = [] | data : 1
  6. 이때 원래의 데이터에서 맨앞의 데이터만 없는 형태가 됩니다.
  7. Dequeue 성공!

 

상상을 해보면 좀더 이해가 쉽습니다.

 

꽉차있는 프링글스 통의 맨 밑의 감자칩이 먹고 싶다면 비어있는 프링글스통을 하나 더 준비합니다.

이후 꽉차있는 프링글스 통에 있는 감자칩을 꺼꾸로 비어있는 통에다 전부다 붓습니다.

이후 부어진 감자칩의 맨위에걸 하나 집어먹고 다시 반대로 원래 있던 통에 쏟아 넣으면 맨앞의 감자칩만 없게됩니다

 

 

한번 직접 구현해 보신다면 이해가 훨씬 쉬울테니 겁먹지 마세요 ㅎㅎ