An Introduction to Array-Based Stacks in C

Introduction

Whether you notice it or not, we encounter stacks on the daily. At the cafeteria, for instance, the last tray placed is the first out (LIFO).

In the same way, we can organize data such that the last element placed in the stack is the first taken out.

Today, we'll take a closer look at array-based stacks and how to implement them in C.

Operations on Stacks

There are two major operations you can do on a stack:

• push: add an element to the top of the stack

• pop: remove the (most-recent) element at the top of the stack

Array-Based Stacks

// stores an array, in this case 10 elements
// stores the index of the top of the stack

#define MAX 10;

typedef struct Stack
{
	// TYPE arr[SIZE];
	int arr[MAX];
	int top;
} stack;

Let's fill a stack.

// declares a stack
stack s1;
// sets top field to 0
s1.top = 0;

Now, we're ready to implement functions for each of our possible operations!

Pushing

// adds element to the top of the stack
void push(stack* s, int val)
{
	int top = s->top;

	// adding an element where we don't have 
	// enough space would cause a stack overflow
	if (top == MAX)
		return;

	s->arr[top] = val;
	s->top = s->top + 1; 
}

Notice how a pointer to the stack was passed rather than just the stack variable, in order to pass it by reference instead of by value (so the function can actually modify it and not a copy of it).

Let's move on to the pop( ) function...

Popping

// removes element from the top of the stack
int pop(stack* s)
{
	int top = s->top;

	// if array is empty, decreasing top would result in
	// a stack underflow
	if (top == 0)
		return;
	
	// stores former top value
	// decrements top field
	int topVal = s->top;
	s->top = s->top - 1;

	return topVal;
}

That's pretty much it. Much, much simpler than queues that we worked with previously!

Final Thoughts

That's all for array-based stacks! Keep an eye out for another post on stacks (but this time, linked-list-based.)

Thanks for reading!