What is a Stack in programming?
A stack is a linear data structure that allows to access and store values in order LIFO (Last In First Out) or FILO (First In Last Out).
The way this structure behaves in programming is similar to that of a stack of objects in the real world, for example, a stack of plates or stones, as you can see in the following figure:
A stack has at least three basic operations, all of them with a complexity of O(1):
- PUSH
- POP
- PEEK
Some other operations usually accompany these:
- Check if the stack is empty
- Initialize the stack
- Show (or print) the stack
- Search a value in the stack
- Get the size of the stack
Some examples of stacks in software are undo/redo operations that you can find in many programs or syntax highlighting in text editors, among others.
How to code a stack in C
There are several ways you can program a stack in C, the most common being by using arrays and linked lists. In this article, I will show you how to do it using arrays, while in the second part, I will show you how to create a C stack using linked lists.
The structure of a stack in the C language is the following:
struct Stack{
int top;
int capacity;
int* array;
};We will add some other auxiliary functions to this structure to instantiate it and check when it is full/empty.
struct Stack* createStack(int capacity){
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); //Reserve memory block
stack->capacity = capacity; //Assign the size of the stack
stack->top = -1; // Initialize the value at the top of the stack
stack->array = (int*)malloc(stack->capacity*sizeof(int)); //Define an array that will store the data
return stack;
}
int isFull(struct Stack* stack){
return stack->top == stack->capacity-1;
}
int isEmpty (struct Stack* stack){
return stack->top == -1;
}Next, we will define the stack’s main functions, which will allow us to add and remove elements to it.
Basic Stack Operations
PUSH
As shown in the figure at the beginning of the article, the PUSH function consists of placing an element at the top of the stack.
We can perform this operation by placing the value received by the function at the end of the array.
void PUSH(struct Stack* stack, int element){
if (isFull(stack))
return;
stack->array[++stack->top] = element;
}POP
To implement the unstacking function, or POP, we only need to do the opposite of the PUSH function. That is, subtracting 1 to the stack stop and return the value of the popped element.
int POP(struct Stack* stack){
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}PEEK
The PEEK function allows us to know which element is at the top of the stack. We can easily implement it by unstacking the top of the stack and storing its value in a variable, restacking the element immediately afterward, and returning the stored value:
int PEEK(struct Stack* stack){
int val = POP(stack);
PUSH(stack, val);
return val;
}Additional Stack Operations
After implementing PUSH(), POP() and PEEK(), and the corresponding functions to know the state of the stack (full or empty) and the necessary functions to create new stacks, we still have to implement the following functions:
- Print the content of the stack
- Search for a value within the stack
-
See the size of the stack
To print the stack’s contents, we have to go through the array that makes up the stack and print the value stored in each index. Finding a value within the stack follows the same principle but we have to return the current index when the searched value is found.
Returning the stored value of the “top” variable is enough to know the stack’s size.void print(struct Stack* stack){for (int i = 0; i <= stack->top; i++)
printf("%i\n", stack->array[i]);
}
int search(struct Stack stack, int value){
for (int i = 0; i <= stack->top; i++)
if (stack->array[i] == value)
return i;
return -1;
}
int numElements(struct Stack stack){
return stack->top+1;
}
Here is an example of the use of the implemented functions:
int main(){
struct Stack* stack = createStack(5); ////Create the stack with 5 slots
PUSH(stack, 100); // [100,-,-,-,-]
PUSH(stack, 200); // [100, 200, -,-,-]
PUSH(stack, 300); // [100, 200, 300, ,- ,-]
PUSH(stack, 400); // [100, 200, 300, 400, -]
PUSH(stack, 500); // [100, 200, 300, 400, 500]
POP(stack); // [100, 200, 300, 400,-]
POP(stack); // [100, 200, 300, -, -]
PUSH(stack, 600); // [100, 200, 300, 600]
PUSH(stack, 700) // [100, 200, 300, 600, 700]
print(stack);
printf("The stack has %i elementos\n",numElements(stack));
if (isFull(stack))
printf("The stack is full");
}Using arrays is a simple way to create a stack in C and implement this data structure in this language. However, it has some disadvantages compared to creating a stack using a linked list, being one of them its defined size. In the next part of this article, I will show you how to create a stack and its basic operations using pointers and linked nodes.