Queue
Linked Queue
typedef struct N{ int data; struct N* next; } node; typedef struct{ node* first; node* rear; } queue;
Enqueue
void enqueue(queue** Q, int num) { node* item = (node*)malloc(sizeof(node)); item->data = num; item->next = null; if (*Q->rear == null) { *Q->first = item; *Q->rear = item; } else { *Q->rear->next = item; *Q->rear = item; } }
Dequeue
int dequeue(queue** Q) { if (*Q->first == null) { printf("already empty\n"); } else if (*Q->first == *Q->rear) { int ret = *Q->first->data; free(*Q->first); *Q->first = null; *Q->rear = null; return ret; } else { int ret = *Q->first-data; node* temp = *Q->first; *Q->first = *Q->first->next; free(*Q->temp); return ret; } }
Circular Queue
#define size 100 typedef struct{ int array[size]; int first; int rear; int count; } queue;
Enqueue
void enqueue(queue** Q, int num) { if (*Q->count >= *Q->size) { printf("already full\n"); } else { *Q->rear = (*Q->rear+1)%(*Q->size); *Q->array[*Q->rear] = num; *Q->count++; } }
Dequeue
int dequeue(queue** Q) { int x = 0; if (*Q->count <= 0) { printf("already empty\n"); } else { x = *Q->array[*Q->first]; *Q->first = (*Q->first+1)%*(Q->size) *Q->count--; } return x; }
Other Solutions
Linked Queue
#include <stdio.h> typedef struct Node{ struct Node *next; int data; } Node; typedef struct { Node *head, *tail; } Queue; void Enqueue(Queue *Q, int item) { Node *new = (Node*)malloc(sizeof(Node)); new->data = item; new->next = NULL; if (Q->tail == NULL) { Q->head = new; Q->tail = new; } else { Q->tail->next = new; Q->tail = new; } } Node* Dequeue(Queue *Q) { Node *p; if (Q->head == NULL) { printf("queue is empty!\n"); return NULL; } else if (Q->head == Q->tail) { p = Q->head; Q->head = Q->tail = NULL; } else { p = Q->head; Q->head = Q->head->next; } return p; }
Circular Queue
typedef struct { int array[100]; int head, tail, cnt; } queue; int enqueue(queue *q, int item) { if (q->cnt == 100) { printf("queue full!\n"); return 0; } q->array[q->tail] = item; q->tail = (q->tail + 1) % 100; q->cnt += 1; return 1; } int dequeue(queue *q, int *item) { if (q->cnt == 0) { printf("queue empty\n"); return 0; } *item = q->array[head]; q->head = (q->head + 1) % 100; q->cnt -= 1; return 1; }
page revision: 14, last edited: 20 May 2010 22:44