Stack is a way we can store information. It follows the simple process of Last In, First Out or LIFO. Adding an item to the top of the stack is called a “push” operation. Removing an item from the top of a stack is called a “pop” operation. Another operation is “top”. Top simply returns the latest item that has been pushed the stack. Depending on the application, sometimes the pop operation can also be used as a top by returning what has been removed to the caller. These operations have a constant time or a time complexity of O(1).
We can implement a stack using arrays or a linked list. In array implementation, you can push a stack only until you reach the size of an array. We can have a situation where we consume the array and we cannot push anymore. This is what we call a stack overflow. There a few ways to avoid a stack overflow:
1. Add a semantic check before you push a new item to the stack
2. We can create a new large array and copy the contents of the older filled up array. The cost of copy is O(n) where n is the size of the filled up array. Simple strategy of deciding the size of the new array is doubling n
Here is a simple example of a stack implementation in C
#include <stdio.h> #define STACK_CAPACITY 10 //A int stack data Structure struct Stack { int list[STACK_CAPACITY]; int size; }; typedef struct Stack Stack; //Initialize stack void initStack(Stack *s) { s->size = 0; } //Return the top of stack int top(Stack *s) { if (s->size == 0) { printf("Error: stack empty\n"); return -1; } return s->list[s->size-1]; } //Returning the current size of a stack int size(Stack *s) { return s->size; } //Push an item to the stack void push(Stack *s, int item) { if (s->size < STACK_CAPACITY) s->list[s->size++] = item; else printf("Error: stack full\n"); } //Pop an item to the stack void pop(Stack *S) { if (S->size == 0) printf("Error: stack empty\n"); else S->size--; } int main() { //Create local variables int item=-1, currentSize = -1; //Create a stack strucuture Stack s; //Initialize stack initStack(&s); //Get the current size of a stack currentSize = size(&s); printf("Current size of a stack %d\n", currentSize); //Push three items to a stack item = 2; push(&s, item); item = 1996; push(&s, item); item = 203; push(&s, item); //Get the current size of a stack currentSize = size(&s); printf("Current size of a stack %d\n", currentSize); //Get the current top item of the stack item = -1; item = top(&s); printf("Current top item of the stack %d\n", item); //Use the pop operations couple of times pop(&s); //pop 203 pop(&s); //pop 1996 //Get the current size of a stack currentSize = size(&s); printf("Current size of a stack %d\n", currentSize); //Get the current top item of the stack item = -1; item = top(&s); //returns 2 printf("Current top item of the stack %d\n", item); item = 0; //Try to overlow the stack by push "0" ten times for(int i=0; i < STACK_CAPACITY; i++) { push(&s, item); } //Get the current size of a stack currentSize = size(&s); printf("Current size of a stack %d\n", currentSize); //Try to empty the stack for(int i=0; i < STACK_CAPACITY; i++) { pop(&s); } //Get the current size of a stack currentSize = size(&s); printf("Current size of a stack %d\n", currentSize); //Empty the stack while it is empty pop(&s); return 0; }
Here is an output of our simple C program:
Some of the applications of a stack data structure in Computer Science are:
1. Stack Memory Management
2. Text Parsing
3. Expression Evaluation
4. Backtracking Algorithms
For more resources on the applications of the stack data structure see the following: Stack Applications
