A stack is non-primitive linear data structure with predefined capacity. Additionally, it is an ordered list which allows the insertion of new data items and deletion of existing data items from one end only, known as top of stack (TOS). A stack is said to be empty or underflow if there are not any data items in the stack, whereas if the stack is full it is said to be overflow.

## Basic Feature of Stack Data Structure

- Stack is an Abstract Data Type (ADT).
- It is also called Last-In-First-Out (LIFO) since the last item added in the stack (which is in the top) is removed at first from the top.
- To insert a data item in stack we use the “push” function. Likewise, to delete a data item we use the “pop” function.
- We cannot access data items randomly in stack due to restriction.

## Basic Operations

- PUSH operation: The “PUSH” operation inserts new data items in stack. In this case, the data item most recently pushed/added is at the Top.
- POP operation: The “POP” operation deletes the data item which is at the top of the stack.
- createStack operation: This operation creates a new empty stack.
- isFull Operation: This operation checks if the stack is full or not (i.e. stack overflow).
- isEmpty Operation: This operation checks if the stack is empty or not (i.e. stack underflow).
- Peek operation: This operation returns the top data item of the stack without removing it.

## Applications of Stack Data Structure

Stack data structure are used in computer in various ways. Some of them are:

- String Reversal: Stack can be used in reversal of string. Firstly, we push every character of the string in the stack and then pop them one by one to reverse a string.
- Expression Evaluation and Conversion: We can evaluate the prefix, postfix and infix expressions using stacks. Also, they can be helpful to convert one form of expression to another form (like infix to postfix, postfix to prefix, etc.).
- Syntax Parsing: Parsing of program blocks, syntax of expressions, etc. can be done using stack. If you want to read more about syntax parsing and parsers you can read it in Wikipedia.
- Parenthesis Checking: Compilers can use the stack to check the correct opening and closing of parenthesis.
- Recursion: Stack is used to store and restore the recursive function and their arguments.

** Also Read:** Introduction to Data Structure and Algorithm

## Implementation of Stack

There are two ways to implement stack. They are:

- Array Implementation of stack: This is also called static implementation because they are limited in size. They are quick because there is no overhead to allocate, link, unlink and deallocate the storage blocks.
- Linked List implementation of stack: This is also called dynamic implementation because the size of stack is not limited. However, there is storage block allocation, linking, unlinking and deallocation overhead in this implementation. Due to which linked lists are inefficient than array implementation.

### Static (Array) implementation of stack data structure in C

Static or array implementation of stack data structure in C uses a one dimensional array to store the data. Also, we use a variable “top” to keep track of the top position of the stack. We increment top by 1 every time we add any data and decrement by 1 every time we delete any item. Generally, in this implementation we set the value of top to -1 (top = -1) to indicate the empty stack.

We will be using structure to store data here. However, we can use array and “top” variables individually.

#define size 50 struct Stack { int items[size]; int top; }; typedef struct Stack STACK;

#### Creating empty stack:

In C implementation, the value of top = -1 shows the stack is empty.

void createStack(STACK *s) { s->top = -1; }

#### Stack Underflow:

Stack Underflow means that there aren’t any data items in the stack. That means the value of top will be -1 (top = -1). The following function returns 1 if the stack is empty else returns 0.

int isEmpty(STACK *s) { if(s->top == -1) return 1; else return 0; }

#### Stack Overflow:

Stack Overflow means that we cannot push data items any more in the stack. In this case, the top lies in the highest location (top = size – 1) of the stack. The following function returns 1 if the stack is full else returns 0.

int isFull(STACK *s) { if(s->top == size - 10) return 1; else return 0; }

#### Algorithm for PUSH operation

This algorithm is used for insertion of an item at the top of the stack.

Step 1: Check for the stack overflow (i.e. if the stack is full or not). Step 2: If there is overflow, then print the error and exit. Step 3: If there isn't overflow, then increment the value of top by 1 and add the item.

#### Algorithm for POP operation

This algorithm deletes or removes an item from top of the stack and assigns it to a variable.

Step 1: Check for the stack underflow (i.e if the stack is empty or not). Step 2: If there is underflow, then print the error and exit. Step 3: If there isn’t underflow, then assign the top value to variable and decrement the top by 1.

#### Value of top variable

Value of top | Status of Stack |

-1 | Underflow |

-1 < top < (size – 1) | Data item can be inserted or removed |

size – 1 | Stack is full |

size | Overflow |

#### Program to implement Stack Data Structure in C

#include<stdio.h> #include<conio.h> /* size gives the maximum size of the stack */ #define size 50 struct Stack { int items[size]; int top; }; /* defines "struct Stack" as "STACK" */ typedef struct Stack STACK; /* This function creates a empty stack */ void createStack(STACK *s) { s->top = -1; } /* This function returns 1 if the stack is empty else returns 0 */ int isEmpty(STACK *s) { if(s->top == -1) return 1; else return 0; } /* This function returns 1 if the stack is full else returns 0 */ int isFull(STACK *s) { if(s->top == size - 1) return 1; else return 0; } /* This function push the data item in the stack */ void push(STACK *s, int data) { if(isFull(s) == 1) { printf("Stack overflow"); exit(1); } else { s->top++; s->items[s->top] = data; } } /* This function removes the top data item and returns it. */ int pop(STACK *s) { int value; if(isEmpty(s) == 1) { printf("Stack Underflow"); exit(1); return 0; } else { value = s->items[s->top]; s->top--; return value; } } /* This function returns the top data item of the stack. */ int peek(STACK *s) { if(isEmpty(s) == 1) { printf("Underflow"); exit(1); return 0; } else { return s->items[s->top]; } } /* This function prints all the data items in the stack. */ void printStack(STACK *s) { int i; if(isEmpty(s) == 1) { printf("\nStack is Empty."); } else { for(i=0; i<=s->top; i++) { printf("\n%d", s->items[i]); } } } int main(){ int item, choice; int flag=1; STACK st; STACK *s; s = &st; clrscr(); createStack(s); do { /* Showing the menu items */ printf("\n\n______ Menu _______"); printf("\n1. Push the data item."); printf("\n2. Pop the data item."); printf("\n3. Check the top item."); printf("\n4. Display all data items."); printf("\n5. Exit."); /* Taking choice */ printf("\n\nEnter your choice:"); scanf("%d", &choice); /* Switching according to the choice */ switch(choice) { case 1: printf("\nEnter the number to be pushed: "); scanf("%d", &item); push(s, item); break; case 2: item = pop(s); printf("\nPopped item is %d.", item); break; case 3: item = peek(s); printf("\nTop item is %d", item); break; case 4: printf("All the data items in stack are: "); printStack(s); break; case 5: flag = 0; break; default: printf("Invalid Choice!!!"); } } while(flag == 1); return 0; }

##### Output

_______ Menu _______ 1. Push the data item. 2. Pop the data item. 3. Check the top item. 4. Display all data items. 5. Exit. Enter your choice: 1 Enter the number to be pushed: 5 _______ Menu _______ 1. Push the data item. 2. Pop the data item. 3. Check the top item. 4. Display all data items. 5. Exit. Enter your choice: 2 Popped item is 5. and so on until you exit or any error occurs (like underflow or overflow or other errors).