관련 알고리즘 문제

Python으로 구현

Python에서는 List로 Queue를 구현한다. queue모듈이 있기는 하지만 멀티 쓰레드에 사용되는 것 같다. 나중에 필요하면 공부하자.

queue = []

# push
queue.append(1)
# pop
queue.pop(0)
# size
len(queue)
# empty
if queue:
    ...
# front
queue[0]

C로 구현

배열로 구현

C에서는 배열로 Queue를 구현할 수 있다. 아래의 함수를 구현했다.

#include <stdio.h>
#define MAX 1000

int queue[MAX];
int front;
int rear;

void init() {
    front = 0;
    rear = 0;
}

int push(int data) {
    queue[rear] = data;
    rear = (rear + 1) % MAX;
}

int pop() {
    int ret = queue[front];
    front = (front + 1) % MAX;
    return ret;
}

int size() {
    if (front > rear) {
        return MAX + rear - front;
    } else
        return rear - front;
}

int empty() {
    return front == rear;
}

int main() {
    push(1);
    push(2);
    push(3);
    printf("%d\\n", pop());
    printf("%d\\n", pop());
    printf("size = %d\\n", size());
    printf("emtpy? %s\\n", empty() ? "true" : "false");

    return 0;
}

Linked List로 구현

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

#define qtype int

typedef struct _node {
    qtype data;
    struct _node *next;
} node;

typedef struct _linkedQueue {
    node *front, *rear;
    int len;
} queue;

queue q;

void init() {
    q.front = q.rear = NULL;
    q.len = 0;
}

void push(qtype data) {
    node *n = (node *)malloc(sizeof(node));
    n->data = data;
    n->next = NULL;
    if (!q.len) {
        q.front = q.rear = n;
    } else {
        q.rear->next = n;
        q.rear = q.rear->next;
    }
    q.len++;
}

qtype pop() {
    if (!q.len) {
        printf("- empty -\\n");
        exit(1);
    }
    node *del = q.front;
    qtype ret = q.front->data;
    q.front = q.front->next;
    free(del);
    q.len--;
    return ret;
}

int main() {
    push(1);
    push(2);
    printf("%d %d", pop(), pop());
    pop();
}

C++에서 STL로 구현

STL에서 queue를 지원한다.

추가 및 삭제

조회