Stack implementation using linked-list

Question

typedef struct Stack { char v; int x; int y; struct Stack* next; } Stack; 

Above is my stack struct.

Stack* helper (char val, int x, int y) { Stack* node = (Stack*)malloc(sizeof(Stack)); node->v = val; node->x = x; node->y = y; return node; } void push (Stack** top,char val,int x,int y) { Stack* node = helper(val,x,y); node->next = *top; *top = node; printf("%c pushed to stack\n",val); } void pop (Stack** top,char *val,int *w,int *h) { if (checkempty(*top)) return; Stack* temp = *top; *top = (*top)->next; *val = temp->v; *w = temp->x; *h = temp->y; free(temp); } int checkempty(Stack* top) { return !top; } 

Above are my push and pop functions. I was wondering if there are better ways to do this ? Or is what I am doing the standard way ?

Answer 1

Stack* helper (char val, int x, int y) { 

Your indentation and whitespace are kind of funky; I recommend looking at what some popular open-source code on GitHub does, and trying to copy them as closely as possible. Or, just run your code through a formatter such as clang-format.

Stack *helper(char val, int x, int y) { 

This function is only ever used in one place, so why do you have it? Right now it's kind of unsafe, because helper returns a Stack * which:

• must be freed by the caller to avoid memory leaks, and

• has uninitialized garbage in its next field.

If you inlined it into push, you'd have a complete unit of work, without either of those dangerous sharp edges.

---

Look into proper library organization. You should have a .h file that defines struct Stack and declares push and pop, and a .c file with the implementations.

You should probably name the functions something like stack_push and stack_pop, since push and pop are likely to be common names; e.g. you might later want to write a struct Queue with a queue_push and queue_pop. This kind of "manual namespacing" is common in C libraries.

---

Of course push shouldn't call printf (there's no "I" in "TEAM" and there's no "printf" in "push data onto a stack").

In pop's argument list, you use w and h where you meant x and y.

pop has interesting behavior on an empty stack: it just returns without initializing *x and *y. This is a problem for the caller, because the caller doesn't have any indication that anything went wrong! You should probably make pop return a bool to indicate whether it was successful.

---

Compare a pointer for null with (top == NULL), not !top. Clarity counts!

---

Here's an idea if you want to push yourself harder: Right now you're passing x, y, and value as individual arguments to push, and retrieving them individually from pop. Package them up into a struct!

Here's the struct definitions and function declarations for a different stack implementation. Can you see how to implement these functions?

struct Data { int x, y, value; }; struct DataStack { struct Data data; struct DataStack *next; } struct DataStack *datastack_push(struct DataStack *, struct Data); struct DataStack *datastack_pop(struct DataStack *); struct Data datastack_top(const struct DataStack *); bool datastack_empty(const struct DataStack *); 

Answer 2

Consider separating the stack from the stack entries. Right now, you have to pass a pointer to a pointer to the stack to your push & pop routines. Quuxplusone’s solution requires the caller to do the work of assigning the return value to the stack pointer. Both of these are harder to use.

Moreover, with Quuxplusone’s solution, you can’t pass an empty stack to another function, and have it fill in entries for the caller.

Separating the stack from the stack entries allows the stack to store additional meta data about the stack. Eg)

typedef struct StackEntry { char v; int x, y; struct StackEntry *next; } StackEntry; typedef struct Stack { StackEntry *top; int num_entries; } Stack; 

Now, push, pop & check_empty would all just take a Stack*, which is easier to remember. Stacks can be passed & shared, even if they are empty, since they wouldn’t just be a null pointer. And you can determine the depth of a stack in \$O(1)\$ time.

Answer 3

Stack* helper (char val, int x, int y) { Stack* node = (Stack*)malloc(sizeof(Stack)); node->v = val; node->x = x; node->y = y; return node; } 

That's not a very descriptive name - something in keeping with the existing scheme might be stack_node_create().

Since malloc() returns a void*, there's no need to scare readers by inserting a cast operator.

We must check that malloc() didn't give us a null pointer before we dereference it.

Fixing those issues gives us:

#include <stdlib.h> /** * Return a newly-created node, or a null pointer on failure. */ Stack *stack_node_create(char val, int x, int y) { Stack *const node = malloc(sizeof *node); if (!node) { return node; } node->v = val; node->x = x; node->y = y; return node; } 

When we call this, we do need to remember that it can return a null pointer, and handle that accordingly.