큐(queue)

백준 10845번 큐 : https://www.acmicpc.net/problem/10845

---

큐(queue)란?

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과 정반대의 개념이다.

큐의 기능

여러 가지가 있지만 많이 사용되는 것들이다.

• empty() : 큐가 비어있는지 확인합니다.
• front() : 제일 최상위 데이터를 반환합니다.
• pop() : 큐의 front 데이터를 삭제합니다.
• push(item) : item을 큐에 추가합니다.
• size() : 현재 큐의 사이즈를 반환합니다.
• swap(q1, q2) : 두 큐의 내용을 바꿉니다. 
• back() : 제일 마지막의 데이터를 반환합니다.

 

큐의 활용 예시

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 우선순위가 같은 직업 예약
• 은행 업무
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search)
• 캐시(Cache)

 

스택의 구현

백준 10845번 큐문제

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

이것도 스택과 마찬가지로 c++에 queue라는 헤더가 존재합니다. 

이것의 사용방법을 알아봅시다.

 

STL 큐 사용법

// queue 헤더파일을 선언
#include <queue>

// int형, char형 큐를 생성
queue<int> q1;
queue<char> q2;

// int형 큐 q1에 숫자를 추가
q1.push(1);
q1.push(2);
q1.push(3);

// int형 큐 q1에 원소를 삭제
q1.pop();

queue의 함수들

queue<int> Queue를 기준으로 하여

 

• Queue.push(n) : 큐에 n를 추가
• Queue.pop() : 큐의 원소 하나를 제거
• Queue.top() : 맨 위의 원소 리턴
• Queue.size() : 큐의 크기를 반환
• Queue.empty() : 비어있는지 확인

 

 

 

참조 :

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