Skip to content

Instantly share code, notes, and snippets.

@J16N

J16N/queue.c

Created November 13, 2021 04:53
Show Gist options
  • Save J16N/f1f863e09911b5358fd4e553b80dbf2d to your computer and use it in GitHub Desktop.
Save J16N/f1f863e09911b5358fd4e553b80dbf2d to your computer and use it in GitHub Desktop.
Download ZIP
Queue using dynamic array
Raw
queue.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct {
int *container;
int front, rear, size;
} Queue;
int len(Queue *);
void flush(FILE *);
void destroy(Queue *);
void display(Queue *);
void dequeue(Queue *);
Queue *init_queue(void);
void enqueue(Queue *, int);
int double_container(Queue *);
int main(void)
{
printf("*******************************************\n");
printf("* QUEUE USING DYNAMIC ARRAY *\n");
printf("*******************************************\n");
printf("* <1> Display all elements in the QUEUE. *\n");
printf("* <2> Enqueue element in the QUEUE. *\n");
printf("* <3> Dequeue element from the QUEUE. *\n");
printf("* <4> Get the length of the QUEUE. *\n");
printf("* <0> Quit! *\n");
printf("*******************************************\n");
bool quit = false;
Queue *q = init_queue();
while (!quit) {
int choice;
printf("\nChoice: ");
scanf("%d", &choice);
switch (choice) {
case 0:
quit = true;
break;
case 1:
display(q);
break;
case 2:
{
int data;
printf("Data: ");
scanf("%d", &data);
enqueue(q, data);
break;
}
case 3:
dequeue(q);
break;
case 4:
printf("Total Elements: %d\n", len(q));
break;
default:
printf("Invalid Choice!\n");
break;
}
flush(stdin);
}
destroy(q);
return 0;
}
int len(Queue *q)
{
if (q->container == NULL)
return 0;
int length;
if (q->front <= q->rear)
length = q->rear - q->front + 1;
else
length = q->size - q->front + q->rear + 1;
return length;
}
void flush(FILE *in)
{
int ch;
clearerr(in);
do ch = getc(in);
while (ch != '\n' && ch != EOF);
clearerr(in);
}
void destroy(Queue *q)
{
free(q->container);
free(q);
}
void display(Queue *q)
{
if (q->container == NULL) {
printf("The queue is empty.\n");
return;
}
printf("Elements: ");
if (q->front <= q->rear) {
for (int i = q->front; i <= q->rear; ++i)
printf("%d ", q->container[i]);
}
else {
for (int i = q->front; i < q->size; ++i)
printf("%d ", q->container[i]);
for (int i = 0; i <= q->rear; ++i)
printf("%d ", q->container[i]);
}
printf("\n");
}
void dequeue(Queue *q)
{
if (q->container == NULL) {
printf("!!! QUEUE UNDERFLOW !!!\n");
return;
}
int dequeued;
if (q->front == q->rear) {
dequeued = q->container[q->front];
q->size = 0;
q->rear = -1;
q->front = -1;
free(q->container);
q->container = NULL;
}
else {
dequeued = q->container[q->front++];
q->front = q->front % q->size;
}
printf("Dequeued element: %d\n", dequeued);
}
Queue *init_queue(void)
{
Queue *q = malloc(sizeof(Queue));
q->size = 0;
q->rear = -1;
q->front = -1;
q->container = NULL;
return q;
}
void enqueue(Queue *q, int data)
{
if (q->container == NULL) {
q->container = malloc( sizeof(int) );
q->size++;
q->rear++;
q->front++;
q->container[q->rear] = data;
return;
}
if ((q->front == 0 && q->rear + 1 == q->size) ||
q->rear + 1 == q->front) {
if (double_container(q)) {
printf("!!! QUEUE OVERFLOW !!!\n");
return;
}
}
q->rear = (++q->rear) % q->size;
q->container[q->rear] = data;
}
int double_container(Queue *q)
{
int old_size = q->size;
q->size *= 2;
q->container = realloc(q->container, q->size * sizeof(int));
if (q->container == NULL) return -1;
if (q->front > q->rear) {
int j = 1;
for (int i = old_size - 1; i >= q->front; --i, ++j) {
q->container[q->size - j] = q->container[i];
}
q->front = q->size - j + 1;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment