Concept
한 쪽에서 Insertion, 다른 한 쪽에서 Deletion이 발생하는 First in first out 자료구조
Time Complexity
Worst Case
Access : 마지막 원소의 경우 노드를 n번 거쳐야 함 - O(n)
Search : 마지막 원소를 찾을 경우 노드를 n번 검색해야 함 - O(n)
Insertion : 바로 삽입 가능 - O(1)
Deletion : 바로 삭제 가능 - O(1)
Average Case
Access : Theta(n)
Search : Theta(n)
Insertion : Theta(1)
Deletion : Theta(1)
Space Complexity
Worst Case
O(n)
Example
#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
struct _node *prev;
struct _node *next;
int value;
} Node;
typedef struct _queue {
Node *front;
Node *rear;
} Queue;
Queue *createQueue() {
Queue *queue = (Queue *) malloc(sizeof(Queue));
queue->front = NULL;
queue->rear = NULL;
return queue;
}
void enqueue(Queue *queue, int input) {
Node *new = (Node *) malloc(sizeof(Node));
if(!new) {
printf("Out of memory\n");
exit(1);
}
new->value = input;
new->prev = queue->rear;
new->next = NULL;
if (queue->rear) queue->rear->next = new;
queue->rear = new;
if (!queue->front) queue->front = new;
}
int dequeue(Queue *queue) {
if(!queue->front) {
printf("Queue underflow\n");
exit(1);
}
Node *old = queue->front;
int value = old->value;
queue->front = old->next;
if (queue->front) queue->front->prev = NULL;
free(old);
return value;
}
void print(Queue *queue) {
if(!queue->front) return;
Node *current = queue->front;
while (current) {
printf("%d ", current->value);
current = current->next;
}
printf("\n");
}
Remark
범용적으로 Example 코드 개선 필요