[BOJ/C] 10845번 큐

https://www.acmicpc.net/problem/10845

10845번: 큐

 

- 큐(queue)

: 작업들이 처리되기 전에 대기하고 있는 선형 리스트 자료 구조.

원소들이 FIFO(First In First Out) 구조로 추가되거나 삭제됨.

파이썬의 경우 리스트를 통해, C언어의 경우 배열을 통해 구현 가능.

 

1) 선형 큐(linear queue)

- 큐의 시작과 끝이 서로 분리되어 있음

 

- 선형 큐 구현 코드(python)

class Queue:
    def __init__(self, size):
        self.front = -1
        self.rear = -1
        self.queue = []
        self.size = size

    def isEmpty(self):
        return len(self.queue) == 0

    def isFull(self):
        return len(self.queue) == self.size

    def push(self, item):
        if not self.isFull():
            self.rear += 1
            self.queue.append(item)
            self.show_queue()

        else:
            print("Queue Full")

    def pop(self):
        if not self.isEmpty():
            self.front += 1
            return self.queue.pop(0)

        else:
            print("Queue Empty")

    def show_queue(self):
        print(self.queue)

q = Queue(5)
for item in [3, 4, 5, 6, 7, 8]:
    q.push(item)

for i in range(6):
    q.pop()
    q.show_queue()

- 실행 결과

[3]
[3, 4]
[3, 4, 5]
[3, 4, 5, 6]
[3, 4, 5, 6, 7]
Queue Full
[4, 5, 6, 7]
[5, 6, 7]
[6, 7]
[7]
[]
Queue Empty

- 코드 실행 시 큐의 상태와 출력 값

연산	[0 1 2 3 4]	front/rear	결과/반환 값
초기상태		-1/-1
push(3)	3	0/0
push(4)	3 4	0/1
push(5)	3 4 5	0/2
push(6)	3 4 5 6	0/3
push(7)	3 4 5 6 7	0/4
push(8)	3 4 5 6 7	0/4	queue full
pop()	4 5 6 7	0/3	3
pop()	5 6 7	0/2	4
pop()	6 7	0/1	5
pop()	7	0/0	6
pop()		-1/-1	7
pop()		-1/-1	queue empty

 

2) 순환 큐(circular queue)

: 큐의 양쪽 끝을 서로 연결하여 원소의 이동 작업 없이 전체 공간을 모두 사용할 수 있다.

self.rear = (self.rear + 1) % self.size
self.front = (self.front + 1) % self.size

마지막 공간과 첫 번째 공간이 연결되어 있으므로 변수 값을 변경할 때 해당 코드를 사용하면 됨.

 

2-1) 순환 데크(circular deque)

데크 : 큐의 앞과 뒤 모두에서 원소의 추가와 삭제가 가능한 큐 기존 선형 큐의 모든 함수 이외에 데크 앞에 원소를 추가하는 함수와 뒤에서 삭제하는 함수가 필요함.

 

 

#include <stdio.h>

// '정수'를 저장하는 queue
int queue[10001];

// 큐의 인덱스 변수
int front = 0, rear = -1;
int count = 0;

// '정수' X를 큐에 넣는 함수
// return 값이 없기 때문에 void 함수로 설정
void push(int data){
    // 넣고자 하는 값 대입 후 인덱스 1 증가
    queue[front] = data;
    rear += 1;
    count += 1;
}

// 출력 값이 정수 값이므로 int 함수
// 반드시 들어가야 하는 매개변수 없음
int pop(){
    if (count != 0){
        count -= 1;
        queue[front] = 0;
        front += 1;
        return queue[front-1];
    }
    else return -1;
}


int size(){
    return count;
}

int empty(){
    if (count != 0) return 0;
    else return 1;
}

int Checkfront(){
    if (empty() == 1) return -1;
    else return queue[front];
}

int back(){
    if (empty() == 1) return -1;
    else return queue[rear];
}

int main(){
    
    // 명령의 수 입력 받기
    int N;
    scanf("%d", &N);
    
    int data;
    char cmd;
    
    for (int i=0; i<N; i++){
        
        scanf("%s", &cmd);
        
        if (cmd == "push"){
            scanf("%d", &data);
            push(data);
        }
        
        else if (cmd == "pop"){
            printf("%d", pop());
        }
        
        else if (cmd == "size"){
            printf("%d", size());
        }
        
        else if (cmd == "empty"){
            printf("%d", empty());
        }
        
        else if (cmd == "front"){
            printf("%d", Checkfront());
        }
        
        else if (cmd == "back"){
            printf("%d", back());
        }
    }
}

: 시간 초과 뜸

 

- strcmp(s1, s2)

: 비교할 두 문자열을 넣어주면 결과를 정수로 반환

 

ASCII 코드 기준으로 s2가 클 때 : return -1;

ASCII 코드 기준으로 두 문자열이 같을 때 : return 0;

ASCII 코드 기준으로 s1이 클 때 : return 1;

 

- Segmentation Fault

: 할당하지 않은 메모리 영역에 접근하는 경우 발생

 

문자열은 문자열 길이만큼의 데이터를 저장한 뒤 맨 뒤에 NULL문자 ('\0')를 붙여 저장하기 때문에

문자열 저장 시 문자열의 길이보다 1 더 큰 배열이 필요.

 

 

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

// '정수'를 저장하는 queue
int queue[10001];

// 큐의 인덱스 변수
int front = 0, rear = 0;
int count = 0;

// '정수' X를 큐에 넣는 함수
// return 값이 없기 때문에 void 함수로 설정
void push(int data){
    // 넣고자 하는 값 대입 후 인덱스 1 증가
    queue[rear] = data;
    rear += 1;
    count += 1;
}

// 출력 값이 정수 값이므로 int 함수
// 반드시 들어가야 하는 매개변수 없음
int pop(){
    
    int a;
    
    if (count != 0){
        // 큐에 들어있는 정수의 개수 하나 감소
        count -= 1;
        
        // 가장 앞 정수 삭제 전 리턴값을 위해 저장
        a = queue[front];
        
        // 가장 앞에 있는 정수 삭제
        queue[front] = 0;
        
        // 가장 앞에 있는 정수의 인덱스 1 증가
        front += 1;
        
        return a;
    }
    else return -1;
}


int size(){
    return count;
}

int empty(){
    if (count != 0) return 0;
    else return 1;
}

int Checkfront(){
    if (empty() == 1) return -1;
    else return queue[front];
}

int back(){
    if (empty() == 1) return -1;
    else return queue[rear-1];
}

int main(){
    
    // 명령의 수 입력 받기
    int N;
    scanf("%d", &N);
    
    int data;
    char cmd[6];
    
    for (int i=0; i<N; i++){
        
        scanf("%s", &cmd);
        
        if (!strcmp(cmd, "push")){
            scanf("%d", &data);
            push(data);
        }
        
        else if (!strcmp(cmd, "pop")){
            printf("%d\n", pop());
        }
        
        else if (strcmp(cmd,"size") == 0){
            printf("%d\n", size());
        }
        
        else if (strcmp(cmd, "empty") == 0){
            printf("%d\n", empty());
        }
        
        else if (strcmp(cmd, "front") == 0){
            printf("%d\n", Checkfront());
        }
        
        else if (strcmp(cmd, "back") == 0){
            printf("%d\n", back());
        }
    }
}