Stack using doubly linked list

Question

I have implemented my stack based on a doubly linked list. The code is tested and works; however, I am interested in any improvement ideas.

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
 int data;
 struct Node* prev;
 struct Node* next;
} Node;
//---------------------Stack---------------------
typedef struct Stack {
 int size;
 Node* head;
 Node* tail;
 int top;
} Stack;
const Stack stack_init = { .size = 0, .head = NULL, .tail = NULL, .top = -1 };
Node* create_node(int elm) {
 Node* node = malloc(sizeof * node);
 if (!node) return node;
 node->data = elm;
 node->prev = NULL;
 node->next = NULL;
 return node;
}
int is_empty_s(Stack *s) {
 return s->tail == NULL;
}
void push(Stack *s, int elm) {
 Node* updated_head = create_node(elm);
 if (!s->head) {
 s->head = updated_head;
 s->tail = s->head;
 } else {
 updated_head->next = s->head;
 s->head->prev = updated_head;
 s->head = updated_head;
 }
 s->size++;
 s->top = s->head->data;
}
int pop(Stack *s) {
 if (!is_empty_s(s)) {
 Node* node = s->head;
 int elm = node->data;
 s->head = s->head->next;
 if (s->head) {
 s->head->prev = NULL;
 s->top = s->head->data;
 }
 else {
 s->tail = NULL;
 s->top = -1;
 }
 s->size--;
 free(node);
 return elm;
 }
 return -111; //assuming it -111 won't be in the stack
}
int top(Stack *s) {
 return s->top;
}
void clear_s(Stack *s) {
 while (s->tail)
 pop(s);
}
void reverse_s(Stack *s) { //iterative
 Stack *s2 = malloc(sizeof *s2);
 *s2 = stack_init;
 while (s->tail)
 push(s2, pop(s));
 s->head = s2->head;
}
void print_s(Stack *s) {
 for(Node* trav = s->head; trav != NULL; trav = trav->next)
 printf("%d ", trav->data); 
 printf("\n");
}
int main() {
 
 Stack s1 = stack_init;
 push(&s1, 5);
 push(&s1, 4);
 print_s(&s1);
 reverse_s(&s1);
 print_s(&s1);
 return 0;
}

• Sᴀᴍ Onᴇᴌᴀ: I have rolled back Rev 3 ➡️ 2. Please see What to do when someone answers.
• greybeard: What does Valgrind have to say about reverse_s(Stack *s)?

Answer 1

Why use a doubly-linked list? All the work of a stack is at one end, so a singly-linked list will save you space and time (both coding time and execution time).

---

We're failing to account for null pointer return here:

Node* updated_head = create_node(elm);
if (!s->head) {
 ⋮
} else {
 updated_head->next = s->head;

And here:

Stack *s2 = malloc(sizeof *s2);
*s2 = stack_init;

Compiling with gcc -fanalyzer reveals these, and running under Valgrind shows failure to free the latter.

---

I've never, ever, needed to reverse the elements in a stack. Unless you have a compelling use case, drop that function. If you do have such a use, document why it's needed in a comment, so that when it's no longer needed it can be removed.

---

It's good practice to make all function declarations declare the acceptable arguments:

int main(void)

---

Please use braces consistent for all control structures (if, for, while, do). It makes your code clearer and more resilient to editing.

Answer 2

If you look closely at the code, you will see that the struct member size is never used, it is only updated. This indicates that you don't need the size member. You also don't need an integer top variable. The top should be a pointer. The integer top and size variables only matter if you are implementing a stack using arrays.

Since a stack is a LIFO (Last In First Out) data structure proper implementation of a stack only needs a pointer to the top. Pushing an item onto the stack means that what top points to become the value of the next pointer. You don't really need a doubly linked list for a stack, it does help when in implement a queue.

• Toby Speight: I don't think a queue really benefits from double-linking either - perhaps you're thinking of a deque?

Answer 3

Consider a uniform name space

Code such as this is not used in isolation, but with other code. The names chosen readily collide (like top) with existing code and do no indicate their common origin.

Suggest dllist as a prefix.

typedef ... dllist_node;
typedef ... dllist_stack;
dllist_node* dllist_create_node(int elm);
int dllist_top(dllist_stack *s);
...
void dllist_print(const dllist_stack *s);

const

Functions that do not modify refenced data should use const

// int is_empty_s(Stack *s) {
int is_empty_s(const Stack *s) {

• Self-documents function's use.

• Allows user to call with a const Stack *s.

• Allows some weaker compilers to optimize code better.

Poor magic number choice

Avoid naked magic numbers. INT_MIN is a better choice.

#define DATA_INVALID INT_MIN
...
 // return -111; //assuming it -111 won't be in the stack
 return DATA_INVALID;

Even better, re-design interface and allow all int.

// int pop(Stack *s) {
// Return success
bool pop(Stack *s, int *val) {

Use bool for true/false data

#include <stdbool.h>
// int is_empty_s(Stack *s) {
bool is_empty_s(Stack *s) {

Answer 4

A stack should be a vector (that is, a dynamically-allocated array that remembers its size and capacity). Pop by decrementing the size. Push by reallocating if necessary and incrementing the size.

You will use less time and memory than if you implement with a list.