[Jungol] 정올 1697 큐(Queue)

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=970&sca=2070

Approach

Corner Case없이 자료구조 큐(Queue)를 구현하는 문제입니다.

(※ 명령어 개수(N)이 최대 100개이므로 배열에 들어갈 수 있는 최대 개수 = 100)

    ① "i a": 숫자 a를 큐에 넣는다. (a는 10,000 이하의 자연수)

    ② "o": 큐 dequeue (비어 있는 경우 "empty" 출력)

    ③ "c": 큐 크기(size)

 

▶ [큐] Queue란?

[큐] Queue란?

---

#include <stdio.h>
 
int N, val, que[100 + 5];
char cmd;
int fr, re, qSize;
int main() {
 
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf(" %c", &cmd);
         
        if (cmd == 'i') {
            scanf("%d", &val);
            que[re++] = val;
            qSize++;
        }
        else if (cmd == 'o') {
            if (fr == re) {
                printf("empty\n");
            }
            else {
                printf("%d\n", que[fr++]);
                qSize--;
            }
             
        }
        else {
            printf("%d\n", qSize);
        }
    }
}

 

다른 Version

- head는 가장 최근에 삽입된 원소를 가르키고 있습니다.

- tail은 앞쪽에 위치한 원소를 가르키고 있습니다.

- [push]

    → 비어있을 때 원소가 삽입되는 경우 (*tail 주의)

    → 원소가 존재할 때, 새로운 원소가 삽입되는 경우

- [pop]

    → 비어있을 때, 삭제 시도하는 경우

    → 원소가 한 개 남아있을 때, 삭제하는 경우 (*head 주의)

    → 원소가 2개 이상일 때 삭제하는 경우

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
struct Node {
    int num;
    Node *next, *prev;
    Node* alloc(int num, Node* next) {
        this->num = num;
        this->next = next;
        this->prev = NULL;
        if (next != NULL) next->prev = this;
        return this;
    }
} *head, *tail, buf[100 + 5];
int qSize, bcnt;
 
void push(int num) {
    head = buf[bcnt].alloc(num, head);
    // 비어있는 상태에서 1개 추가되는 경우
    if (qSize == 0) tail = &buf[bcnt];
    bcnt++;
    qSize++;
}
 
void pop() {
    if (qSize == 0) {
        printf("empty\n");
        return;
    }
    printf("%d\n", tail->num);
    
    if(tail->prev != NULL) tail->prev->next = NULL;
    tail = tail->prev;
    // 큐가 한개만 남은 경우 삭제 후 비워집니다.
    if (qSize == 1) {
        head = NULL;
    }
    qSize--;
}
 
int N, val;
char cmd;
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf(" %c", &cmd);
 
        if (cmd == 'i') { // 삽입
            scanf("%d", &val);
            push(val);
        }
        else if (cmd == 'o') 
            pop();
        else 
            printf("%d\n", qSize);
    }
}