Data Structure — Queue

BOJ #10845 queue: https://www.acmicpc.net/problem/10845

---

What is a queue?

A queue is one of the computer's basic data structures — a storage format that is FIFO (First In First Out), where the data put in first comes out first. It's the exact opposite concept of a stack, where the data put in later comes out first.

Queue operations

There are several, but these are commonly used.

• empty(): checks whether the queue is empty.
• front(): returns the frontmost data.
• pop(): deletes the front data of the queue.
• push(item): adds item to the queue.
• size(): returns the current size of the queue.
• swap(q1, q2): swaps the contents of two queues.
• back(): returns the very last data.

Example uses of a queue

A queue is mainly used in situations where data needs to be processed in the order it was input.

• Reservations for jobs of equal priority
• Bank tasks
• Process management
• Breadth-First Search (BFS)
• Cache

Implementing a queue

BOJ #10845 queue problem

See more

#include <stdio.h>
#include <string.h>

int queue[10001];
int queue_size=0;

void push(int push_data){
    queue[queue_size] = push_data;
    queue_size += 1;
}

int empty(){
    if(queue_size == 0){
        return 1;
    }
    return 0;
}

int pop(){
    if(empty()){
        return -1;
    }
    queue_size -= 1;
    return queue[0];
}

int front(){
    if(empty()){
        return -1;
    }
    return queue[queue_size-queue_size];
}

int back(){
    if(empty()){
        return -1;
    }
    return queue[queue_size-1];
}

void setting(){
    for (int i=0;i<queue_size;i++)
    {
        queue[i]=queue[i+1];
    }
}

int main(){

    int N = 0, push_data = 0;
    char command[5] = {0,};

    scanf("%d",&N);

    for(int i=0;i<N;i++){

        scanf("%s",command);

        if(!strcmp(command,"push")){
            scanf("%d",&push_data);
            push(push_data);
        }
        else if(!strcmp(command,"pop")){
            printf("%d\n",pop());
            setting();
        }
        else if(!strcmp(command,"empty")){
            printf("%d\n",empty());
        }
        else if(!strcmp(command,"size")){
            printf("%d\n",queue_size);
        }
        else if(!strcmp(command,"front")){
            printf("%d\n",front());
        }
        else if(!strcmp(command,"back")){
            printf("%d\n",back());
        }

    }

    return 0;
}

Like the stack, C++ also has a header called queue.

Let's look at how to use it.

How to use the STL queue

// declare the queue header file
#include <queue>

// create int-type and char-type queues
queue<int> q1;
queue<char> q2;

// add a number to the int-type queue q1
q1.push(1);
q1.push(2);
q1.push(3);

// remove an element from the int-type queue q1
q1.pop();

queue's functions

Based on queue<int> Queue

• Queue.push(n): adds n to the queue
• Queue.pop(): removes one element from the queue
• Queue.top(): returns the top element
• Queue.size(): returns the size of the queue
• Queue.empty(): checks whether it's empty

Reference:

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=justkukaro&logNo=220510730704

https://life-with-coding.tistory.com/408

https://mygumi.tistory.com/357

https://coding-factory.tistory.com/598

---

Original (Korean): tistory — published 2021-06-03, migrated to this blog. This translation was generated with the help of AI.