# Queue

## 큐(Queue)

한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조이다.

* **FIFO**(First In First Out)먼저 넣은 것이 가장 먼저 나온다.
  * 시뮬레이션의 대기열(공항에서 비행기, 은행에서의 대기열)
  * 통신에서의 데이터 패킷들의 모델링
  * 프린터와 컴퓨터 사이의 버퍼링

![](https://mblogthumb-phinf.pstatic.net/20150101_31/javaking75_1420090455748JsXB6_JPEG/%C6%F7%B8%CB%BA%AF%C8%AF_%C5%A5%B1%B8%C1%B6_coolten.jpg?type=w2)

| 연산             | 설명                        |
| -------------- | ------------------------- |
| push / enQueue | 큐에 자료를 넣는 연산              |
| pop / deQueue  | 큐에서 자료를 빼는 연산             |
| front          | 큐의 가장 앞에 있는 자료를 보는 연산     |
| back / rear    | 큐의 가장 뒤에 있는 자료를 보는 연산     |
| empty          | 큐가 비어있는지 아닌지를 알아보는 연산     |
| size           | 큐에 저장되어있는 자료의 개수를 알아보는 연산 |

### 배열

#### 선형 큐

* 1차원 배열로 구현이 쉽지만, 삽입 시 자료의 이동이 많다.
* 상태 인식의 오류가 발생하고 비효율적이다. 거의 사용하지 않는다.

| 종류   | 삽입 위치         | 삭제 위치           |
| ---- | ------------- | --------------- |
| 순차 큐 | rear = rear+1 | front = front+1 |

![](http://cfile28.uf.tistory.com/image/264CB741591C27DF02B25C)

* 초기상태 : front = rear = -1
* 공백상태 : front = rear
* 포화상태 : rear = n-1

순차 큐는 나중에 공간이 비어있는데 사용하지 못하는 경우가 발생한다.

```c
#include <iostream>
#include <string>
using namespace std;
struct Queue {
    int data[10000];
    int begin, end;
    Queue() {
        begin = 0;
        end = 0;
    }
    void push(int num) {
        data[end] = num;
        end += 1;
    }
    bool empty() {
        if (begin == end) {
            return true;
        } else {
            return false;
        }
    }
    int size() {
        return end - begin;
    }
    int front() {
        return data[begin];
    }
    int back() {
        return data[end-1];
    }
    int pop() {
        if (empty()) {
            return -1;
        }
        begin += 1;
        return data[begin-1];
    }
};
int main() {
    int n;
    cin >> n;

    Queue q;

    while (n--) {
        string cmd;
        cin >> cmd;
        if (cmd == "push") {
            int num;
            cin >> num;
            q.push(num);
        } else if (cmd == "pop") {
            if (q.empty()) {
                cout << -1 << '\n';
            } else {
                cout << q.front() << '\n';
                q.pop();
            }
        } else if (cmd == "size") {
            cout << q.size() << '\n';
        } else if (cmd == "empty") {
            cout << q.empty() << '\n';
        } else if (cmd == "front") {
            if (q.empty()) {
                cout << -1 << '\n';
            } else {
                cout << q.front() << '\n';
            }
        } else if (cmd == "back") {
            if (q.empty()) {
                cout << -1 << '\n';
            } else {
                cout << q.back() << '\n';
            }
        }
    }

    return 0;
}
```

#### 원형 큐

* 논리적으로 머리와 꼬리가 연결되어있다고 가정한다.

| 종류  | 삽입 위치                | 삭제 위치                   |
| --- | -------------------- | ----------------------- |
| 원형큐 | rear = (rear+1)mod n | front = (front+1) mod n |

![](http://cfile27.uf.tistory.com/image/2102763B5602C2D42B5384)

* 초기 공백 상태 : front = rear = 0
* 포화상태 : 나머지 연산자를 이용해서 구한다.
  * (rear+1)%n = front

```cpp
void push(int num) {
    data[end] = num;
    end = (end+1)%MAX_QUEUE;
}

bool full() {
    if (begin == (end+1)%MAX_QUEUE) {
        return true;
    } else {
        return false;
    }
}

int pop() {
    if (empty()) {
        return -1;
    }
    begin = (begin+1)%MAX_QUEUE;
    return data[begin-1];
}
```

### 연결리스트

![](http://cfile1.uf.tistory.com/image/264D3C4953490B601EE36D)

\[[04. List](https://dh00023.github.io/algorithm/ds/2018/04/22/algorithm-4/)]의 단순연결리스트를 참고하여 구현하면된다.

```c
//  queue.h

#ifndef queue_h
#define queue_h

#include <stdio.h>
#include <stdlib.h>
#include "position.h"

typedef struct node{
    int data;
    struct que * next;
}QNode;

typedef struct que{
    QNode * front, * rear;
}Queue;

void enQueue(Queue * q,int data);
void deQueue(Queue * q,int data);
int front(Queue *queue);
int rear(Queue *queue);
int is_empty(Queue *queue);
Queue * creat_queue();
QNode * new_node(int data);
#endif /* queue_h */
```

```c
//  queue.c


#include "queue.h"
QNode * new_node(int data){
    QNode * new = (QNode *)malloc(sizeof(QNode));
    new->data = data;
    new->next=NULL;
    return new;
}

Queue * creat_queue(){
    Queue * new = (Queue *)malloc(sizeof(Queue));
    new->front=new->rear=NULL;
    return new;
}

int is_empty(Queue *q){
    return (q->front==NULL && q->rear==NULL);
}

int front(Queue *q){
    if(is_empty(q)) return -1;
    else return q->front->data;
}

int rear(Queue *q){
    if(is_empty(q)) return -1;
    else return q->rear->data;
}



//front 포인터는 삭제,  rear 포인터는 삽입할 때 사용
void enQueue(Queue * q,int data){
    QNode * tmp = new_node(data);

    if(q->rear==NULL){
        q->front = q->rear = tmp;
        return;
    }
    q->rear->next= tmp;
    q->rear=tmp;
}

void deQueue(Queue * q,int data){
    if(q->front==NULL){
        return;
    }
    q->front = q->front->next;
    if(q->front==NULL) q->rear=NULL;
}
```

### `<queue>` 라이브러리

```cpp
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {
    int n;
    cin >> n;

    queue<int> q;

    while (n--) {
        string cmd;
        cin >> cmd;
        if (cmd == "push") {
            int num;
            cin >> num;
            q.push(num);
        } else if (cmd == "pop") {
            if (q.empty()) {
                cout << -1 << '\n';
            } else {
                cout << q.front() << '\n';
                q.pop();
            }
        } else if (cmd == "size") {
            cout << q.size() << '\n';
        } else if (cmd == "empty") {
            cout << q.empty() << '\n';
        } else if (cmd == "front") {
            if (q.empty()) {
                cout << -1 << '\n';
            } else {
                cout << q.front() << '\n';
            }
        } else if (cmd == "back") {
            if (q.empty()) {
                cout << -1 << '\n';
            } else {
                cout << q.back() << '\n';
            }
        }
    }

    return 0;
}
```

## 실습

### 조세퍼스 문제

* 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있는다.
* 양의 정수 M(<=N)이 주어진다.
* 순서대로 M번째 사람을 제거한다.
* 이과정을 N명의 사람이 모두 제거될 때까지 계속한다.

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


int main(){
    int n,m,cnt=0;
    scanf("%d %d",&n,&m);

    queue<int> q;
    for(int i=0;i<n;i++){
        q.push(i+1);
    }

    while(!q.empty()){
        for(int i =0;i<m-1;i++){
            q.push(q.front());
            q.pop();
        }
        cout << q.front();
        q.pop();
    }
}
```

## 덱(Deque) <a href="#deque" id="deque"></a>

양 끝에서만 자료를 넣고 양 끝에서 뺄 수 있는 자료구조이다. Double-ended queue의 약자이다. ![](http://cfile5.uf.tistory.com/image/273851475639BB6510A002)

| 연산          | 설명                        |
| ----------- | ------------------------- |
| push\_front | 덱의 앞에 자료를 넣는 연산           |
| push\_back  | 덱의 뒤에 자료를 넣는 연산           |
| pop\_front  | 덱의 앞에서 자료를 빼는 연산          |
| pop\_back   | 덱의 뒤에서 자료를 빼는 연산          |
| front       | 큐의 가장 앞에 있는 자료를 보는 연산     |
| back        | 큐의 가장 뒤에 있는 자료를 보는 연산     |
| empty       | 큐가 비어있는지 아닌지를 알아보는 연산     |
| size        | 큐에 저장되어있는 자료의 개수를 알아보는 연산 |

### 이중 연결 리스트

양쪽에서 삽입, 삭제가 가능하여야 하므로 일반적으로 이중 연결 리스트를 사용한다.

\[[04. List](https://dh00023.github.io/algorithm/ds/2018/04/22/algorithm-4/)]의 이중연결리스트를 참고하여 구현하면된다.

### `<deque>` 라이브러리

```cpp
#include <iostream>
#include <string>
#include <deque>
using namespace std;


int main(){
    int n;
    cin >> n;
    deque<int> dq;

    while(n--){
        string m;
        cin >> m;
        if(m=="push_front"){
            int x;
            scanf("%d",&x);
            dq.push_front(x);
        }else if(m=="push_back"){
            int x;
            scanf("%d",&x);
            dq.push_back(x);
        }else if(m=="pop_front"){
            if(!dq.empty()){
                cout << dq.front()<<"\n";
                dq.pop_front();
            }else{
                cout << -1<<"\n";
            }
        }else if(m=="pop_back"){
            if(!dq.empty()){
                cout << dq.back()<<"\n";
                dq.pop_back();
            }else{
                cout << -1<<"\n";
            }
        }else if(m=="size"){
            cout << dq.size()<<"\n";
        }else if (m=="empty"){
            cout << dq.empty()<<"\n";
        }else if(m=="front"){
            if(dq.empty()){
                cout << -1<<"\n";
            }else{
                cout << dq.front()<<"\n";
            }
        }else if(m=="back"){
            if(dq.empty()){
                cout << -1<<"\n";
            }else{
                cout << dq.back()<<"\n";
            }
        }
    }
}
```

```python
from collections import deque

# python에서 depue라이브러리 사용해 Queue 구현 가능
queue = deque()

queue.append(5)
queue.append(3)
queue.popleft()
```

파이썬으로 큐를 구현할 때는 `collections` 모듈에서 제공하는 deque자료구조를 활용하는 것이 좋다. 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며, queue라이브러리를 이용하는 것보다 더 간단하다.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dahye-jeong.gitbook.io/til/algorithm/2018-04-25-algorithm-queue.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.