libds

commit d8140d231e8f3c5613948e71cbb146680d8cd6c1
parent 154d420b780ecfb36a410a9ad538294a3c44414c
Author: Naveen Narayanan <zerous@nocebo.space>
Date:   Mon, 24 Aug 2026 18:22:18 +0200

Add stack/queue(linked-list)

Diffstat:
A
queue.c
 | 
108
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
stack.c
 | 
114
++++++++++++++++++++++++++++++++++++++++++++-----------------------------------

2 files changed, 172 insertions(+), 50 deletions(-)
diff --git a/queue.c b/queue.c
@@ -0,0 +1,108 @@
+/* queue implementation based on linked list */
+#include <assert.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+typedef struct node node;
+struct node {
+	node *list;
+	void *data;
+};
+
+typedef struct queue queue;
+struct queue {
+	node *head;
+	node *tail;
+	long long sz;
+};
+
+queue *
+queueinit(void)
+{
+	queue *q = malloc(sizeof(queue));
+	q->sz = 0;
+	q->head = q->tail = NULL;
+	return q;
+}
+
+void
+queueput(queue *q, void *d)
+{
+	node *np;
+
+	np = malloc(sizeof(node));
+	np->data = d;
+	np->list = NULL;
+	if(q->head)
+		q->head->list = np;
+	q->head = np;
+
+	if(!q->sz)
+		q->tail = q->head;
+	q->sz++;
+}
+
+void *
+queuepeek(queue *q)
+{
+	return q->tail->data;
+}
+
+long long
+queuesz(queue *q)
+{
+	return q->sz;
+}
+
+void *
+queueget(queue *q)
+{
+	void *r;
+	node *np;
+
+	if(!q->sz)
+		return NULL;
+
+	np = q->tail;
+	q->tail = q->tail->list;
+	q->sz--;
+	if(!q->sz)
+		q->head = NULL;
+	r = np->data;
+	free(np);
+	return r;
+}
+
+int
+main(int argc, char **argv)
+{
+	(void)argc;
+	(void)argv;
+
+	int a[] = {
+		1, 2, 3, 4, 5,
+		6, 7, 8, 9, 10
+		};
+
+	queue *q;
+	int n;
+
+	q = queueinit();
+	for(int i=0; i<10; i++)
+		queueput(q, &a[i]);
+
+	for(int i=0; i<10; i++){;
+		assert(queuesz(q) == 10-i);
+		n = *(int *)queuepeek(q);
+		assert(n == i+1);
+		n = *(int *)queueget(q);
+		printf("%d\n", n);
+		assert(n == i+1);
+	}
+	assert(queuesz(q) == 0);
+
+	free(q);
+
+	return 0;
+}
diff --git a/stack.c b/stack.c
@@ -1,80 +1,94 @@
+/* stack implementation based on linked list */
+#include <assert.h>
+#include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 
-struct stacknode {
+typedef struct node node;
+struct node {
 	void *data;
-	struct stacknode *next;
+	node *next;
+	node *prev;
 };
 
+typedef struct stack stack;
 struct stack {
-	struct stacknode *top;
+	node *head;
 	size_t sz;
 };
 
-struct stack *
-stack_init(void)
+void
+stackinit(stack *s)
 {
-	struct stack *s;
-
-	s = malloc(sizeof(*s));
-	if (!s)
-		return NULL;
-	s->top = NULL;
+	s->head = NULL;
 	s->sz = 0;
-	return s;
 }
 
-void
-stack_free(struct stack *s)
+size_t
+stacksz(stack *s)
 {
-	struct stacknode *n, *tmp;
-
-	n = s->top;
-	while (n) {
-		tmp = n->next;
-		free(tmp);
-		n = tmp;
-	}
-	free(s);
+	return s->sz;
 }
 
-void *
-stack_push(struct stack *s, void *data)
+void
+stackpush(stack *s, void *a)
 {
-	struct stacknode *n;
-
-	n = malloc(sizeof(*n));
-	if (!n)
-		return NULL;
-	n->data = data;
-	n->next = s->top;
-	s->top = n;
 	s->sz++;
-	return data;
+	if(s->head == NULL){
+		s->head = malloc(sizeof(node));
+		s->head->data = a;
+		s->head->next = malloc(sizeof(node));
+		s->head->next->prev = s->head;
+		s->head->prev = NULL;
+		s->head = s->head->next;
+		return;
+	}
+
+	s->head->data = a;
+	s->head->next = malloc(sizeof(node));
+	s->head->next->prev = s->head;
+	s->head = s->head->next;
 }
 
 void *
-stack_pop(struct stack *s)
+stackpop(stack *s)
 {
-	void *data;
+	void *r;
+	node *np;
 
-	if (!s->top)
+	if(s->head->prev == NULL)
 		return NULL;
-	data = s->top->data;
-	s->top = s->top->next;
+
+	r = s->head->prev->data;
+	np = s->head;
+	s->head = s->head->prev;
+	free(np);
 	s->sz--;
-	return data;
+	return r;
 }
 
-void *
-stack_peek(struct stack *s)
+int
+main(int argc, char **argv)
 {
-	if (!s->top)
-		return NULL;
-	return s->top->data;
-}
+	int a[] = {
+		1, 2, 3, 4, 5,
+		6, 7, 8, 9, 10
+		};
 
-size_t
-stack_size(struct stack *s)
-{
-	return s->sz;
+	stack s;
+
+	stackinit(&s);
+	for(int i=0; i<10; i++){
+		stackpush(&s, &a[i]);
+		assert(stacksz(&s) == i+1);
+	}
+
+	for(int i=0; i<10; i++){
+		assert(stacksz(&s) == 10-i);
+		assert(*(int *)stackpop(&s) == a[9-i]);
+	}
+
+	assert(NULL == stackpop(&s));
+
+	return 0;
 }