Queue

ํ(Queue)

ํ•œ์ชฝ ๋์—์„œ๋งŒ ์ž๋ฃŒ๋ฅผ ๋„ฃ๊ณ  ๋‹ค๋ฅธ ํ•œ์ชฝ ๋์—์„œ๋งŒ ๋บ„ ์ˆ˜ ์žˆ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค.

  • FIFO(First In First Out)๋จผ์ € ๋„ฃ์€ ๊ฒƒ์ด ๊ฐ€์žฅ ๋จผ์ € ๋‚˜์˜จ๋‹ค.

    • ์‹œ๋ฎฌ๋ ˆ์ด์…˜์˜ ๋Œ€๊ธฐ์—ด(๊ณตํ•ญ์—์„œ ๋น„ํ–‰๊ธฐ, ์€ํ–‰์—์„œ์˜ ๋Œ€๊ธฐ์—ด)

    • ํ†ต์‹ ์—์„œ์˜ ๋ฐ์ดํ„ฐ ํŒจํ‚ท๋“ค์˜ ๋ชจ๋ธ๋ง

    • ํ”„๋ฆฐํ„ฐ์™€ ์ปดํ“จํ„ฐ ์‚ฌ์ด์˜ ๋ฒ„ํผ๋ง

์—ฐ์‚ฐ

์„ค๋ช…

push / enQueue

ํ์— ์ž๋ฃŒ๋ฅผ ๋„ฃ๋Š” ์—ฐ์‚ฐ

pop / deQueue

ํ์—์„œ ์ž๋ฃŒ๋ฅผ ๋นผ๋Š” ์—ฐ์‚ฐ

front

ํ์˜ ๊ฐ€์žฅ ์•ž์— ์žˆ๋Š” ์ž๋ฃŒ๋ฅผ ๋ณด๋Š” ์—ฐ์‚ฐ

back / rear

ํ์˜ ๊ฐ€์žฅ ๋’ค์— ์žˆ๋Š” ์ž๋ฃŒ๋ฅผ ๋ณด๋Š” ์—ฐ์‚ฐ

empty

ํ๊ฐ€ ๋น„์–ด์žˆ๋Š”์ง€ ์•„๋‹Œ์ง€๋ฅผ ์•Œ์•„๋ณด๋Š” ์—ฐ์‚ฐ

size

ํ์— ์ €์žฅ๋˜์–ด์žˆ๋Š” ์ž๋ฃŒ์˜ ๊ฐœ์ˆ˜๋ฅผ ์•Œ์•„๋ณด๋Š” ์—ฐ์‚ฐ

๋ฐฐ์—ด

์„ ํ˜• ํ

  • 1์ฐจ์› ๋ฐฐ์—ด๋กœ ๊ตฌํ˜„์ด ์‰ฝ์ง€๋งŒ, ์‚ฝ์ž… ์‹œ ์ž๋ฃŒ์˜ ์ด๋™์ด ๋งŽ๋‹ค.

  • ์ƒํƒœ ์ธ์‹์˜ ์˜ค๋ฅ˜๊ฐ€ ๋ฐœ์ƒํ•˜๊ณ  ๋น„ํšจ์œจ์ ์ด๋‹ค. ๊ฑฐ์˜ ์‚ฌ์šฉํ•˜์ง€ ์•Š๋Š”๋‹ค.

์ข…๋ฅ˜

์‚ฝ์ž… ์œ„์น˜

์‚ญ์ œ ์œ„์น˜

์ˆœ์ฐจ ํ

rear = rear+1

front = front+1

  • ์ดˆ๊ธฐ์ƒํƒœ : front = rear = -1

  • ๊ณต๋ฐฑ์ƒํƒœ : front = rear

  • ํฌํ™”์ƒํƒœ : rear = n-1

์ˆœ์ฐจ ํ๋Š” ๋‚˜์ค‘์— ๊ณต๊ฐ„์ด ๋น„์–ด์žˆ๋Š”๋ฐ ์‚ฌ์šฉํ•˜์ง€ ๋ชปํ•˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค.

#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

  • ์ดˆ๊ธฐ ๊ณต๋ฐฑ ์ƒํƒœ : front = rear = 0

  • ํฌํ™”์ƒํƒœ : ๋‚˜๋จธ์ง€ ์—ฐ์‚ฐ์ž๋ฅผ ์ด์šฉํ•ด์„œ ๊ตฌํ•œ๋‹ค.

    • (rear+1)%n = front

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];
}

์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ

[04. List]์˜ ๋‹จ์ˆœ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ์ฐธ๊ณ ํ•˜์—ฌ ๊ตฌํ˜„ํ•˜๋ฉด๋œ๋‹ค.

//  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 */
//  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> ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ

#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๋ช…์˜ ์‚ฌ๋žŒ์ด ๋ชจ๋‘ ์ œ๊ฑฐ๋  ๋•Œ๊นŒ์ง€ ๊ณ„์†ํ•œ๋‹ค.

#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)

์–‘ ๋์—์„œ๋งŒ ์ž๋ฃŒ๋ฅผ ๋„ฃ๊ณ  ์–‘ ๋์—์„œ ๋บ„ ์ˆ˜ ์žˆ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. Double-ended queue์˜ ์•ฝ์ž์ด๋‹ค.

์—ฐ์‚ฐ

์„ค๋ช…

push_front

๋ฑ์˜ ์•ž์— ์ž๋ฃŒ๋ฅผ ๋„ฃ๋Š” ์—ฐ์‚ฐ

push_back

๋ฑ์˜ ๋’ค์— ์ž๋ฃŒ๋ฅผ ๋„ฃ๋Š” ์—ฐ์‚ฐ

pop_front

๋ฑ์˜ ์•ž์—์„œ ์ž๋ฃŒ๋ฅผ ๋นผ๋Š” ์—ฐ์‚ฐ

pop_back

๋ฑ์˜ ๋’ค์—์„œ ์ž๋ฃŒ๋ฅผ ๋นผ๋Š” ์—ฐ์‚ฐ

front

ํ์˜ ๊ฐ€์žฅ ์•ž์— ์žˆ๋Š” ์ž๋ฃŒ๋ฅผ ๋ณด๋Š” ์—ฐ์‚ฐ

back

ํ์˜ ๊ฐ€์žฅ ๋’ค์— ์žˆ๋Š” ์ž๋ฃŒ๋ฅผ ๋ณด๋Š” ์—ฐ์‚ฐ

empty

ํ๊ฐ€ ๋น„์–ด์žˆ๋Š”์ง€ ์•„๋‹Œ์ง€๋ฅผ ์•Œ์•„๋ณด๋Š” ์—ฐ์‚ฐ

size

ํ์— ์ €์žฅ๋˜์–ด์žˆ๋Š” ์ž๋ฃŒ์˜ ๊ฐœ์ˆ˜๋ฅผ ์•Œ์•„๋ณด๋Š” ์—ฐ์‚ฐ

์ด์ค‘ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ

์–‘์ชฝ์—์„œ ์‚ฝ์ž…, ์‚ญ์ œ๊ฐ€ ๊ฐ€๋Šฅํ•˜์—ฌ์•ผ ํ•˜๋ฏ€๋กœ ์ผ๋ฐ˜์ ์œผ๋กœ ์ด์ค‘ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.

[04. List]์˜ ์ด์ค‘์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ์ฐธ๊ณ ํ•˜์—ฌ ๊ตฌํ˜„ํ•˜๋ฉด๋œ๋‹ค.

<deque> ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ

#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";
            }
        }
    }
}
from collections import deque

# python์—์„œ depue๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ์‚ฌ์šฉํ•ด Queue ๊ตฌํ˜„ ๊ฐ€๋Šฅ
queue = deque()

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

ํŒŒ์ด์ฌ์œผ๋กœ ํ๋ฅผ ๊ตฌํ˜„ํ•  ๋•Œ๋Š” collections ๋ชจ๋“ˆ์—์„œ ์ œ๊ณตํ•˜๋Š” deque์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ํ™œ์šฉํ•˜๋Š” ๊ฒƒ์ด ์ข‹๋‹ค. ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๊ณ  ๋นผ๋Š” ์†๋„๊ฐ€ ๋ฆฌ์ŠคํŠธ ์ž๋ฃŒํ˜•์— ๋น„ํ•ด ํšจ์œจ์ ์ด๋ฉฐ, queue๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์ด์šฉํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค ๋” ๊ฐ„๋‹จํ•˜๋‹ค.

Last updated

Was this helpful?