Linked-List-Based Stacks in C

Introduction

As a quick recap, stacks operate on a last in, first out basis, and are usually made from either arrays or linked lists. This guide will be looking at the latter in greater detail.

If you haven't read my post on array-based stacks, you might consider giving that a read before jumping into the linked-list variation!

Linked-List-Based Stacks

Unlike with queues which used doubly-linked lists, stacks are implemented using singly-linked lists.

Why?

Simply because to enqueue a queue, we needed to keep track of the rear of the linked list, and to dequeue, we needed to keep track of the front.

With stacks, we only need to track the rear of the list, which is used for both pushing and popping elements (so we never need to go backwards in our stack, only forwards).

// struct for each node in stack
typedef struct Node
{
	int data;
	struct Node* next;
} node;

// struct for storing the most recent node in stack
// made up of nodes
typedef struct Stack
{
	node* front;
} stack;

Now to initialize a stack.

stack s = (stack*) malloc(sizeof(stack));
s.front = NULL;

With the basic structure out of the way, we can start writing functions that will perform operations on our stack.

Pushing

For pushing a new node to the front (top) of the stack...

// adds a new element (node) to the front of the stack
void push(stack* s, int val)
{
	// mallocs space for new node
	node* newNode = (node*) malloc(sizeof(node));
	if (newNode == NULL)
		return;

	// fills node with data
	// changes next field to old front of list
	newNode->data = val;
	newNode->next = s->front;
	
	// move old front to newNode
	s->front = newNode;
}

Popping

To pop the top node off of the stack...

// remove most recent element in the list
int pop(stack* s)
{
	// if list is empty, return -1
	if (s->front == NULL)
		return -1;

	// creates temp variable to ensure that we don't sever connection
	// to the old top of the list when we move front over
	node* tmp = s->front;
	int val = tmp->data;

	// moves front to the next node
	s->front = s->front->next;

	free(tmp);
	return val;
}

In both of these operations, you may have noticed that we passed a pointer to the stack instead of the stack itself. This is because we want to ensure that our stack is directly getting modified; not a copy of it!

Final Thoughts

That's all for linked-list-based stacks. Thanks for reading!