Stack is one of the basic data-structures and is widely used. Elements in a stack are stored in LIFO (last-in-first-out) approach. Lets try to visualize a stack by using the example of 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 of the stack.
Let us define the data-structure Stack as ADT (Abstract data type). As we know any ADT comes with a set of operations. Operations available with stack are as defined below.
push(): Adding an element to the stack pop(): Taking an element out of the stack is_stack_empty(): Returns true if the stack is empty else returns false 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 show how the stack looks after an element is popped out. At step 3, we push (add) an 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 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: Stack: Push at the top and also pop from the top of stack.
Implementation can be done using both a linked list and an array. On this page, we discuss the implementation using a linked list. The advantage of using a linked list versus array is that the linked list can grow as much as we want. If you would like to enhance your understanding of Linked-list, please take a look at the linked-list section in our data-structures data-structures module before going any further: Linked-Lists.
One more thing. If you would like to see an implementation of Stack using arrays, then you can visit our page here: Implementation of Stack using Arrays. With arrays, we do not have the overhead of having a pointer (next or prev) to connect two elements in the linked list. But, when we run out of the space in the array, we would need to reallocate it to a new bigger size.
Our implementation supports storing any type of data in the stack. Second, the new implementation comes in the form of a header file, an implementation file, and a main file that calls the APIs defined in the header file. This makes the implementation generic enough that we can simply take the implementation file and the header file and use it as a library.
With that, let us begin with the header file.
#ifndef __STACK_H__
#define __STACK_H__
#define STACK_ERRNO_SUCCESS 1
#define STACK_ERRNO_EMPTY -1
#include <stdbool.h>
typedef struct stack_elem_ {
struct stack_elem_ *next;
void *data; /* Holds the data */
} stack_elem;
/* Representation of the Stack */
typedef struct stack_{
stack_elem *top;
int size;
} stack;
/* Initializes the stack. */
void stack_init(stack *s);
/* Adds to the top of the stack. */
void push(stack *s, void *data);
/* Removes from the head. If err is STACK_ERRNO_EMPTY, then stack is empty. */
void *pop(stack *s, int *err);
/* Returns true if stack is empty. */
bool is_stack_empty(stack *s);
/* Returns element at top of the stack, if stack is not empty. */
void *get_top_stack(stack *s, int *err);
/* Returns the size of the stack. */
int stack_get_size(const stack *s);
#endif /* __STACK_H__ */
The above header file begins by publishing the data-structures for the stack and the stack element (stack_elem). Structure stack contains a member, size, that holds the total number of elements present in the stack. The "data" member is of type "void *" . This makes the implementation generic and so the application using this stack can define any custom data-structure and store it as a void pointer. In terms of API, the header file publishes a handful of functions: the stack_init(), the push(), and the pop(). The header also publishes an API, the stack_get_size() that returns the total number of elements present in the queue.
With that, let us provide the actual implementation of the above APIs.
#include <stdio.h>
#include "stack.h"
#include <stdlib.h>
#include <strings.h>
/* Initializes the stack. */
void stack_init (stack *s) {
bzero((void *)s, sizeof(stack));
return;
}
/* Returns the size of the stack. */
int stack_get_size (const stack *s) {
if (!s) {
return -1;
} else {
return (s->size);
}
}
/* Returns element at top of the stack, if stack is not empty. */
void *get_top_stack (stack *s, int *err) {
stack_elem *st_top = NULL;
void *retData;
if (!s || !s->top) {
/* stack is NULL or top points to NULL. Nothing to return */
*err = STACK_ERRNO_EMPTY;
return NULL;
}
/* This is the top and we need to return data associated with that */
st_top = s->top;
retData = st_top->data;
*err = STACK_ERRNO_SUCCESS;
return retData;
}
/* Adds to the top of the stack. */
void push (stack *s, void *data) {
stack_elem *elem = NULL;
/* Build the element that needs to be inserted */
elem = (stack_elem *) malloc(sizeof(stack_elem));
if (!elem) {
fprintf(stderr, "Malloc failed.\n");
return;
}
elem->next = NULL;
elem->data = data;
/* If this elem is the first one, then make top point to it */
if (s->top == NULL) {
s->top = elem;
} else {
elem->next = s->top;
s->top = elem;
}
/* Increase the size. */
s->size += 1;
}
/* Removes from the top of the stack. */
void *pop (stack *s, int *err) {
stack_elem *st_top = NULL;
void *retData;
if (!s || !s->top) {
/* stack is NULL or top points to NULL. Nothing to return */
*err = STACK_ERRNO_EMPTY;
return NULL;
}
/* This is the top and we need to return data associated with that */
st_top = s->top;
retData = st_top->data;
/* Update the top of the stack */
s->top = st_top->next;
/* Free the previous top */
free(st_top);
/* Decrease the size. */
s->size -= 1;
*err = STACK_ERRNO_SUCCESS;
return retData;
}
/* Returns true if stack is empty. */
bool is_stack_empty (stack *s) {
if (!s || !s->top) {
/* stack is NULL or top points to NULL. Stack is empty */
return true;
} else {
return false;
}
}
The stack is initialized by calling stack_init(); this function initializes the passed stack pointer to NULL. The push() function mallocs a new stack element and then assigns the pass data of type "void *" to the data field of the element. Along with that, it also increases the stack size. The pop() retrieves the element from the top of the stack and decreases the stack size. More importantly, if the stack size is empty, then it sets the passed error number variable to indicate the same. Callers of the pop() function should check the returned errno value first.
With the above header file (let us call it "stack.h") and the C file that implements those APIs (let us call it "stack.c"), we are all set to write an application that uses them. So, we write the following application that does exactly the same; we call this file "main_stack.c" since it contains the main() routine.
#include <stdio.h>
#include "stack.h"
void print_stack_for_me (stack *s) {
stack_elem *elem = NULL;
printf("Printing stack (size: %d): ", stack_get_size(s));
for (elem = s->top; elem != NULL; elem = elem->next) {
printf("%d ", *(int *)(elem->data));
}
printf("\n");
}
int main (int argc, char *argv[]) {
stack s;
int *retVal;
int error_no;
int x1 = 280, x2 = 480, x3 = 680, x4 = 880;
stack_init(&s);
print_stack_for_me(&s);
/* Try popping when the stack is empty.
* Check if the stack is empty first */
if (is_stack_empty(&s)) {
printf("Stack is Empty, Nothing to pop \n");
} else {
retVal = (int *)pop(&s, &error_no);
if (error_no != STACK_ERRNO_EMPTY) {
printf("Popped %d\n", *retVal);
}
}
/* push few values to the stack. */
push(&s, (void *)&x1);
printf("Pushed: %d\n", x1);
push(&s, (void *)&x2);
printf("Pushed: %d\n", x2);
push(&s, (void *)&x3);
printf("Pushed: %d\n", x3);
print_stack_for_me(&s);
retVal = (int *)get_top_stack(&s, &error_no);
if (error_no != STACK_ERRNO_EMPTY) {
printf("Element at top of the stack %d\n", *retVal);
} else {
printf("Stack is Empty\n");
}
/* pop one and push one. */
retVal = (int *)pop(&s, &error_no);
if (error_no != STACK_ERRNO_EMPTY) {
printf("Popped %d\n", *retVal);
} else {
printf("Stack is Empty\n");
}
print_stack_for_me(&s);
push(&s, (void *)&x4);
printf("Pushed: %d\n", x4);
print_stack_for_me(&s);
/* Do some more pop's! */
retVal = (int *)pop(&s, &error_no);
if (error_no != STACK_ERRNO_EMPTY) {
printf("Popped %d\n", *retVal);
} else {
printf("Stack is Empty\n");
}
retVal = (int *)pop(&s, &error_no);
if (error_no != STACK_ERRNO_EMPTY) {
printf("Popped %d\n", *retVal);
} else {
printf("Stack is Empty\n");
}
print_stack_for_me(&s);
return 0;
}
In the above implementation, the main() function defines a stack (s), uses stack_init() to initialize it, and then calls the push()/pop() operations. The file also contains a function (print_stack_for_me()) that prints various elements of the stack.
To run the above file, we use "gcc" for compiling this function along with the "stack.c". Here is the output.
user@codingbison$ gcc stack.c main_stack.c -o stack user@codingbison$ ./stack Printing stack (size: 0): Stack is Empty, Nothing to pop Pushed: 280 Pushed: 480 Pushed: 680 Printing stack (size: 3): 680 480 280 Element at top of the stack 680 Popped 680 Printing stack (size: 2): 480 280 Pushed: 880 Printing stack (size: 3): 880 480 280 Popped 880 Popped 480 Printing stack (size: 1): 280