commit 2fc17de3be18c7bcd3cedd7ced5b73e6478367f5
parent c19790552906e5d4eb92a755e708771f6494608f
Author: mjkloeckner <martin.cachari@gmail.com>
Date: Tue, 31 Jan 2023 20:52:39 -0300
added queue data structure
new data structure impelemented: queues
the implementation uses linked lists
Diffstat:
| M | Makefile | | | 2 | +- |
| M | main.c | | | 21 | +++++++++++---------- |
| A | queue.c | | | 64 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | queue.h | | | 29 | +++++++++++++++++++++++++++++ |
4 files changed, 105 insertions(+), 11 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,5 +1,5 @@
CC := gcc
-CFLAGS := -Wall -Wshadow -pedantic -ansi -std=c99 -O3
+CFLAGS := -Wall -Wshadow -pedantic -ansi -std=c99 -g
SRCS := $(wildcard *.c)
OBJS := $(SRCS:.c=.o)
diff --git a/main.c b/main.c
@@ -1,21 +1,22 @@
#include <stdio.h>
-#include "stack.h"
+#include "queue.h"
int main (void) {
- Stack *S;
- int x;
+ Queue *Q;
- stack_new(&S, sizeof(int));
+ queue_new(&Q, sizeof(int));
- for(size_t i = 0; i < 100; ++i)
- stack_push(S, &i);
+ size_t i;
+ int x;
+ for(i = x = 0, x = i; i < 10; ++i, x = i)
+ queue_enqueue(Q, &x);
- while(S->len) {
- stack_pop(S, &x);
- printf("%5d%s", x, S->len % 10 ? " " : "\n");
+ while(queue_is_empty(Q)) {
+ queue_dequeue(Q, &x);
+ printf("%5d\n", (int)x);
}
- stack_destroy(S);
+ queue_destroy(Q);
return 0;
}
diff --git a/queue.c b/queue.c
@@ -0,0 +1,64 @@
+#include "queue.h"
+
+/* FIFO: First In First Out */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+void queue_new(Queue **Q, size_t type_size) {
+ (*Q) = malloc(sizeof(Queue));
+ (*Q)->first = NULL;
+ (*Q)->end = NULL;
+ (*Q)->type_size = type_size;
+}
+
+void queue_enqueue(Queue *Q, void *data) {
+ Node *new = malloc(sizeof(Node));
+ new->data = malloc(Q->type_size);
+ memcpy(new->data, data, Q->type_size);
+
+ if(!Q->first) Q->first = new;
+
+ if(!Q->end) Q->end = new;
+ else Q->end->next = new;
+
+ new->prev = Q->end;
+ new->next = NULL;
+ Q->end = new;
+}
+
+void queue_dequeue(Queue *Q, void *data) {
+ assert(Q->first);
+ assert(Q->end);
+
+ memcpy(data, Q->first->data, Q->type_size);
+
+ Q->first->prev = Q->first;
+ Q->first = Q->first->next;
+ if(Q->first == NULL) return;
+
+ free(Q->first->prev->data);
+ free(Q->first->prev);
+ Q->first->prev = NULL;
+}
+
+bool queue_is_empty(Queue *Q) {
+ return Q->first;
+}
+
+void queue_destroy(Queue *Q) {
+ for(Node *n = Q->first; n; n = n->next)
+ free(n->prev);
+
+ if(Q->end)
+ free(Q->end->data);
+
+ free(Q->end);
+ if(Q->first)
+ free(Q->first->data);
+
+ free(Q->first);
+ free(Q);
+}
diff --git a/queue.h b/queue.h
@@ -0,0 +1,29 @@
+#ifndef QUEUE_H_
+#define QUEUE_H_
+
+#include <stddef.h>
+#include <stdbool.h>
+
+typedef struct Node Node;
+typedef struct Queue Queue;
+
+struct Node {
+ void *data;
+ Node *next;
+ Node *prev;
+};
+
+struct Queue {
+ size_t type_size;
+ Node *first;
+ Node *end;
+};
+
+void queue_new(Queue **Q, size_t type_size);
+void queue_enqueue(Queue *Q, void *data);
+void queue_dequeue(Queue *Q, void *data);
+void queue_destroy(Queue *Q);
+
+bool queue_is_empty(Queue *Q);
+
+#endif
