Stack is one of the basic data-structures that is widely used. Elements in a stack are stored in last-in-first-out (LIFO) approach. An easy way to understand stack is to visualize a stack of plates in a restaurant -- here, one gets to pick a plate from the top. As the stack shrinks, new plates are added to the top of the stack. So, the elements are added (pushed) to the top of the stack and also removed (popped) from the top.
Let us define the data-structure Stack as ADT (Abstract data type). As we know any ADT comes with a set of operations. For a stack, the two common operations available are: push() and pop(). The push() is used for adding an element to the stack and the pop() is used for taking (removing) an element out of the stack. In addition, we also provide two more operations: is_stack_empty() and top_of_stack(). The is_stack_empty() returns true if the stack is empty else returns false. The top_of_stack() returns the element at the top of the stack.
Let us understand the push and pop operations for a stack using a simple figure (provided below). At step 1, we start with a stack that has certain elements. At step 2, we pop() an element out of stack and the figure at step-2 shows how the stack looks after an element is popped out. At step 3, we push (add) a new element to the top of the stack.
Step 1: Push 3 elements into the stack.
push(280) --> | 280 | <-- top_of_stack
push(480) --> | 480 |
push(680) --> | 680 |
Stack
Step 2: Lets pop() (remove) an element out of the stack.
top_of_stack --> | 280 | pop() ( Element at the top of the stack is removed.)
| 480 | --------------> | 480 | --->top_of_stack()
| 680 | | 680 |
Stack Stack
Step 3: Lets push() (add) an element to the stack.
top_of_stack --> | 480 | push(880) ( Element is added to the top the stack.)
| 680 | --------------> | 880 | --->top_of_stack()
Stack | 480 |
| 680 |
Stack
Figure: Push and Pop Operations in a Stack
We can implement a stack using both a linked list and an array. The advantage of using a linked list versus array is that the linked list can grow as much as we want. However, with an array, we would need to re-allocate the array, whenever we go beyond the currently allocated size. The cost comes in the form of linked list having to have an additional member that connects two links in the list.
To keep things simple, we use an array-based implementation. If you would like to see our implementation that uses linked-list, then you can find it here: Implementation of Stacks (Using Linked-Lists).
#include<stdio.h>
#include<stdbool.h>
#define STACK_SIZE 10
/* Global Variables */
int stack[STACK_SIZE];
int top = -1;
/* Displays all the elements of the Stack */
void display () {
int i=0;
printf("Printing stack (size %d):",top+1);
for (i = 0; i <= top; i++) {
printf (" %d ", stack[i]);
}
printf(" \n");
}
/* Returns true, if the Stack is empty */
bool is_stack_empty () {
if (top == -1) {
return true;
} else {
return false;
}
}
/* Push ( Add) an element to the top of the Stack */
void push (int val) {
if (top >= STACK_SIZE - 1) {
printf(" Stack is full, cannot add new elements\n");
return;
}
top = top + 1;
stack[top] = val;
printf(" Pushed: %d \n", stack[top]);
}
/* Remove (pop) an element from the top of the Stack */
void pop () {
bool is_empty;
is_empty = is_stack_empty();
if (is_empty == true) {
printf(" Stack is Empty, nothing to pop\n");
return;
} else {
printf(" Popped: %d \n", stack[top]);
stack[top] = -1;
top = top -1;
}
}
/* Returns the element from the top of the Stack. Does not destroy the element. */
int top_of_stack () {
return stack[top];
}
int main (int argc, char *argv[]) {
int stack_top;
bool is_empty;
pop();
push(680);
push(880);
pop();
/* Before calling top_of_stack(), make sure the Stack is not empty */
is_empty = is_stack_empty();
if (is_empty == true) {
printf(" Stack is already empty, no elements to pop\n");
} else {
stack_top = top_of_stack();
printf(" Element at top of the stack is : %d \n", stack_top);
}
push(280);
push(480);
push(237);
display();
pop();
pop();
display();
}
We call push() and pop() functions randomly in the main() function. To demonstrate the operations, the push() function adds an element at the end of array and increases the top variable by one. The pop() function does the opposite -- it removes an element from the end of array and decreases the top variable by one. The display() function prints all the elements of the stack along with their position (index) in the stack (array).
In the end, we compile the above file by passing it to the gcc. Here is the output:
user@codingbison$ gcc stack_array.c -o stack_array user@codingbison$ ./stack_array Stack is Empty, nothing to pop Pushed: 680 Pushed: 880 Popped: 880 Element at top of the stack is : 680 Pushed: 280 Pushed: 480 Pushed: 237 Printing stack (size 4): 680 280 480 237 Popped: 237 Popped: 480 Printing stack (size 2): 680 280
We have kept the above implementation intentionally simple. But, there are various ways in which we can make it more generic and thereby more like a production-software.
First and foremost, the above implementation assumes the elements that goes into the stack would be all integers. A generic implementation should support storage of any data type. Second, a generic infra implementation should be added in the form of a header file, an implementation file, and a main file that calls the APIs defined in the header file. This way, we can simply take the implementation file and the header file and (re)use it for multiple applications.
Here is a library-style implementation that follows these recommendations to make the above implementation more generic: Advanced Implementation of Stacks. Please go through it, if you are comfortable with the stack implementation on this page. Else, feel free to skip it for now.