큐(Queue) / 덱(Deque)

큐(Queue)

큐는 스택과 다르게 FIFO (First In First Out)의 성격을 지닌다. 맨 처음 들어온 자료가 제일 처음 나가고, 맨 마지막에 들어온 자료가 마지막에 나간다. 즉, 들어가는 입구 나가는 출구가 따로 존재한다는 것이다. 큐는 순서가 의미가 있는 문제에서 자주 활용되는 자료구조이다.

대표적인 큐의 기능

• push : 큐에 자료를 넣는다.
• pop : 큐의 자료를 뺀다.
• front : 큐의 가장 처음 자료를 가르킨다.
• back : 큐의 가장 마지막 자료를 가르킨다.
• empty : 큐가 비어있는지 여부를 알려준다.
• size : 큐의 크기를 알려준다.

push

pop

QUEUE구현 & 라이브러리

C언어에서는 STACK과 마찬가지로 큐를 직접 구현하여 사용한다.
python같은 경우는 collections.deque를 사용하거나 직접 구현하여 사용한다.
반면에 C++이나 Java와 같은 경우, 큐 라이브러리가 존재하기 때문에 라이브러리를 사용하는것이 일반적이다.

C에서의 큐

#include<stdio.h>

int queue[99999];
int begin = 0;
int end = 0;

void push(int data){
    queue[end] = data;
    end++;
    }

void pop(){
    queue[begin] = 0;
    begin++;
    }

int front(){
    return queue[begin - 1];
    }

int back(){
    return queue[end - 1];
    }

bool empty(){
    if(begin == end)
    	return true;
    return false;
    }

int size(){
    return end - begin;
    }

C++에서의 큐

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int main(){
    queue<int> q;
    q.push(1);
    q.push(3);
    q.push(5);
    q.pop;
    
    return 0;
}

큐를 사용한 문제

1. 순서가 의미 있는 문제.
2. 주로 BFS에서 이용된다.

덱(Deque)

Deque는 Double-ended queue의 약자이다.
덱은 출구와 입구가 2개인데 양끝에서 자유롭게 자료를 빼고 넣을 수 있다.
덱은 큐와 스택의 성질을 모두 가지고 있다. 따라서 덱은 상황에 따라서 스택도 될 수 있고, 큐도 될 수 있다.

대표적인 덱의 기능

• push_front: 덱의 앞에 자료를 넣는다.
• push_back: 덱의 뒤에 자료를 넣는다.
• pop_front: 덱의 앞에서 자료를 뺀다.
• pop_back: 덱의 뒤에서 자료를 뺀다.
• front: 덱의 가장 처음에 있는 자료를 본다.
• back: 덱의 가장 마지막에 있는 자료를 본다.

push and pop

문제

요세푸스 문제