Queue (큐)

Queue란?

한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조
먼저 들어간 원소가 먼저 나오는 FIFO(First In First Out) 선입선출 자료구조
예) 공항 입국수속 대기줄 / 은행 업무창구 대기줄 등등
특정 위치에서만 원소를 넣거나 뺄 수 있는 Restricted Structure이다.

push & pop (Enqueue & Dequeue)

peek(front & back)

Queue의 성질

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제일 앞/뒤의 원소 확인이 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

Queue 구현 및 기능

배열 및 연결 리스트로 구현 할 수 있다.
Stack과 마찬가지로 배열을 통한 구현이 더 쉬우니 배열로 알아보자.
Queue를 배열로 구현할 때는 원소를 담은 큰 배열 한개와 앞뒤를 가리키는 head, tail 변수가 필요하다.
Queue는 push(삽입), pop(삭제), front(제일 앞 원소 반환), back(제일 뒤 원소 반환) 메서드로 구성되어 있다.

C++ & Java 구현코드

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

void push(int x){
  dat[tail++] = x;
}

void pop(){
  head++;
}

int front(){
  return dat[head];
}

int back(){
  return dat[tail-1];
}

void test(){
  push(10); push(20); push(30);
  cout << front() << '\n'; // 10
  cout << back() << '\n'; // 30
  pop(); pop();
  push(15); push(25);
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 25
}

int main(void) {
  test();  
}

https://github.com/devjun63/basic-algo/commit/00256e09d251cdd0a72c93991168884a32bd4d45

 

정리

• 선형 배열로 구현한 큐의 경우 삭제시 쓸모없는 공간이 생긴다.
  • 앞쪽에 공간이 많음에도 새 원소를 추가할 수 없는 상황이 발생
• 원형 큐는 head와 tail이 다시 앞쪽으로 돌아온다.
  • 때문에 원소의 갯수가 배열의 크기보다 커지지 않는 한 문제가 없다.
• 보통 DFS나 flood fill에 사용된다.