Stack

Stack is a linear data structure that follows the LIFO (Last In First Out) principle.
It performs insertion and deletion operations on the stack from only one end and that is from the top of the stack.
Stack and queue are ADTs
- Abstract data types (ADTs) are high-level programming concepts that define a set of operations on a particular data structure without specifying the implementation details. In other words, they are a way of defining a data type in terms of its behavior, rather than its implementation.
Inserting a new element on the top of the stack is known as push operation.
Deleting a data element from the top of the stack is known as pop operation.
You can perform the implementation of the stack in memory using two data structures: stack implementation using array and stack implementation using linked-list.
Real life examples of stack:
- Stack of plates.
- Stack of balls.

Stack Implementation using Array

In stack implementation using arrays, it forms the stack using the arrays. All the operations regarding the stack implementation using arrays are done at the end of the array.

Procedure of stack implementation using array

Push operation

Adding an element on the top of the stack is termed as push operation.
Push operation has the following two steps:
1. Increment the top variable of the stack so that it can refer to the next memory location.
2. Add a data element at the increment top position.
Stack data structure states an overflow condition when you try to insert an element into the stack when complete.

Algorithm ↓

                     
PUSH(stack[], top, value)

   1. if (top == MAX -1)
         print Overflow
         Exit
      End of if
   2. increment top by 1
   3. stack[top] = value 
   4. End of else 
   5. End of PUSH

Program code ↓

                                                 
// implementatin of push operation:

void push(int data, int n)
{
   if(top == n-1)
   {
      printf("overflow");
      return;
   }
   top++;
   stack[top] = data;
}

Pop operation

Removing a data element from the stack data structure is called a pop operation.
The pop operation has two following steps:
1. The value of the top variable will decrement by one whenever you delete an item from the stack.
2. The topmost variable of the stack is stored in another variable, and then the value of the top variable will be decremented by one.
3. The pop operation returns the deleted element that was stored in another variable as a result.
Stack data structure states an underflow condition when you try to delete a data element when the stack is already empty.

Algorithm ↓

                                 
   POP(STACK[], top)
1. if (top == -1)
      print Underflow
      Exit 
   End of if
2. val = STACK[top]
3. top = top - 1
4. print val is deleted 
5. End of POP

Program code ↓

                                                  
// implementation of pop operation 

void POP()
{
   int val;
   if(top == -1)
   {
      printf("Underflow condition");
      return;
   }
      val = stack[top];
      top--;
      printf("%d is deleted ", val);
}

Display

Algorithm ↓

                                   
DISPLAY(STACK[], top)
1. if top == -1 
      print Underflow 
      Exit
   End of if
2. i = top 
3. repeat step 4, while i >= 0
4. print STACK[i]
   i = i + i 
5. End of DISPLAY

Program code ↓

                                          
void display()
{
   int i;
   if(top == -1)
   {
      printf("Underflow");
      return;
   }
   for(i = top; i >= 0; i--)
   {
      printf("%d", stack[i]);
   }
}

Programs

                        
#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
// stack declaration
#define MAX 5
int stack[MAX];
int top = -1;

int main()
{
   int choice;
   while (1)
   {
      printf("\n\n**** MENU *****");
      printf("\n1. PUSH");
      printf("\n2. POP");
      printf("\n3. DISPLAY");
      printf("\n4. EXIT");
      printf("\nEnter your choice : ");
      scanf("%d", &choice);

      switch (choice)
      {
      case 1:
         push();
         break;
      case 2:
         pop();
         break;
      case 3:
         display();
         break;
      case 4:
         exit(0);
      default:
         printf("\nEnter a correct choice");
      }
   }
   return 0;
}
void push()
{
   if (top >= MAX -1)
   {
      printf("\n\nStack overflow\n\n");
      return;
   }
   top++;
   printf("\nEnter a value : ");
   scanf("%d", &stack[top]);
   printf("\n\n%d is pushed\n\n", stack[top]);
}

void pop()
{
   int val;
   if (top <= -1)
   {
      printf("\n\nStack underflow\n\n");
      return;
   }
   val = stack[top];
   top--;
   printf("\n\n%d is popped\n\n", val);
}

void display()
{
   int i;
   if (top <= -1)
   {
      printf("\n\nStack underflow\n\n");
      return;
   }
   for (i = top; i >= 0; i--)
   {
      printf("\n%d", stack[i]);
   }
}

                        
#include <stdio.h>
#include <stdlib.h>
int push(int[], int, int);
int pop(int[], int);
void display(int[], int);
int main()
{
   const int MAX = 5;
   int stack[MAX], top = -1, choice;
   while (1)
   {
      printf("\n\n**** MENU *****");
      printf("\n1. PUSH");
      printf("\n2. POP");
      printf("\n3. DISPLAY");
      printf("\n4. EXIT");
      printf("\nEnter your choice : ");
      scanf("%d", &choice);

      switch (choice)
      {
      case 1:
         top = push(stack, top, MAX);
         break;
      case 2:
         top = pop(stack, top);
         break;
      case 3:
         display(stack, top);
         break;
      case 4:
         exit(0);
      default:
         printf("\nEnter a correct choice");
      }
   }
   return 0;
}
int push(int stack[], int top, int MAX)
{
   if (top >= MAX - 1)
   {
      printf("\n\nStack overflow\n\n");
      
   }
   else
   {
      top++;
      printf("\nEnter a value : ");
      scanf("%d", &stack[top]);
      printf("\n\n%d is pushed\n\n", stack[top]);
   }
   return top;
}
int pop(int stack[], int top)
{
   int val;
   if (top <= -1)
      printf("\n\nStack underflow\n\n");
   else
   {
      val = stack[top];
      top--;
      printf("\n\n%d is popped\n\n", val);
   }
   return top;
}
void display(int stack[], int top)
{
   int i;
   if (top <= -1)
   {
      printf("\n\nStack underflow\n\n");
      return;
   }
   for (i = top; i >= 0; i--)
   {
      printf("\n%d", stack[i]);
   }
}

                        
#include <stdio.h>
#include <stdlib.h>
void push(int[], int*, int);
void pop(int[], int*);
void display(int[], int);
int main()
{
   const int MAX = 5;
   int stack[MAX], top = -1, choice;
   while (1)
   {
      printf("\n\n**** MENU *****");
      printf("\n1. PUSH");
      printf("\n2. POP");
      printf("\n3. DISPLAY");
      printf("\n4. EXIT");
      printf("\nEnter your choice : ");
      scanf("%d", &choice);

      switch (choice)
      {
      case 1:
         push(stack, &top, MAX);
         break;
      case 2:
         pop(stack, &top);
         break;
      case 3:
         display(stack, top);
         break;
      case 4:
         exit(0);
      default:
         printf("\nEnter a correct choice");
      }
   }
   return 0;
}
void push(int stack[], int *top, int MAX)
{
   if (*top >= MAX - 1)
   {
      printf("\n\nStack overflow\n\n");
      return;
   }
   (*top)++;
   printf("\nEnter a value : ");
   scanf("%d", &stack[*top]);
   printf("\n\n%d is pushed\n\n", stack[*top]);
}

void pop(int stack[], int *top)
{
   int val;
   if (*top <= -1)
   {
      printf("\n\nStack underflow\n\n");
      return;
   }
   val = stack[*top];
   (*top)--;
   printf("\n\n%d is popped\n\n", val);
}

void display(int stack[], int top)
{
   int i;
   if (*top <= -1)
   {
      printf("\n\nStack underflow\n\n");
      return;
   }
   for (i = top; i >= 0; i--)
   {
      printf("\n%d", stack[i]);
   }
}

Application of stack

Function calling
Browser history: Web browsers use stacks to maintain the user's browsing history. Each time a user visits a new web page, the page is pushed onto the stack, and the user can go back to the previous page by popping it off the stack
Undo and redo functionality: In many software applications, such as text editors or graphics design software, the undo and redo operations rely on a stack data structure. Each time the user performs an action, the application pushes it onto the stack, allowing the user to undo the action by popping it off the stack.
Recursion
Expression evaluation

Notations

Infix → a + b
Prefix → + a b
- Known as polish notation
Postfix → a b +
- Known as reverse polish notation

Remember in pre/post fix expression there is no brackets.

               
Operation Priority ↓
_________________________________
   ^ (power) 

   *, / , %

   +, -
_________________________________
( decreases from top to bottom )

Processor have to convert infix expressions to postfix or prefix because computer doesn't understand infix expression.

Infix to postfix notation

Jenny's lecture ⇗

Steps ↓

Bound the whole expression with brackets if there are no brackets.
- (a + b) / e * f - h → ((a + b) / e * f - h)
Make a table.
- Column 1 = symbols (all the symbols of the infix expression)
- Column 2 = stack (this only contains brackets and operator)
- Column 3 = Postfix expression
Rules ↓
1. Print operands as they arrive.
2. If stack is empty or contains a left paranthesis on top, push the incoming operator onto the stack.
3. If incoming symbol is "(", push it onto stack.
4. If incoming symbol is ")", pop the stack & print the operators until left parenthesis is found.
5. If incoming symbol has higher precedence then the top of the stack, push it on the stack.
6. If incoming symbol has lower precedence then the top of the stack, pop & print the top. Then test the incoming operator against the new top of the stack.
7. If incoming operator has equal precedene with the top of the stack, use associativity rule.
  - associativity L to R then pop & print the top of the stack & then push the incoming operator
  - R to L then push the incoming operator.
8. At the end of the expression, pop & print all operators of stack.

Convert the following infix expressions into postfix expressions and then evaluate:

Program to convert infix expression to postfix expression:

We know the algorithm ↓

Scan the symbols of the expression from left to right and for each symbol, do the following:

If symbol is an operand
- Store the symbol in the postfix array
If the symbol if left parenthesis
- Push it on the stack
If symbol is a right parenthesis
- Pop all the operators from the stack upto the first left parenthesis and store the operators in the postfix array.
- Discard the left and right parenthesis.
If the symbol is an operator
- If the precedence of the operators in the stack are greater than or equal to the current operator, then pop the operators out of the stack and print them onto the screen, and push the current operator onto the stack.
- else
  push the current operator onto the stack.

                        
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
char stack[MAX];
char infix[MAX], postfix[MAX];
int top = -1;

void push(char);
char pop();
int isEmpty();
void inToPost();
int precedence(char);
void print();
int main()
{
   printf("Enter the infix expression : ");
   gets(infix);
   inToPost(); // function that convert infix to postfix expression
   print();
   return 0;
}
void push(char c)
{
   if (top == MAX - 1)
   {
      printf("Stack overflow");
      return;
   }
   top++;
   stack[top] = c;
}
char pop()
{
   char c;
   if (top == -1)
   {
      printf("Stack underflow");
      exit(0);
   }
   c = stack[top];
   top=top-1;
   return c;
}
int isEmpty()
{
   if (top == -1)
      return 1;
   else
      return 0;
}
int space(char c)
{
   // If symbol is a blank space or a tab
   if (c == ' ' || c == '\t')
      return -1;
   else
      return 1;
}
void inToPost()
{
   int i, j = 0;
   char symbol, next;
   // for(i=0;i!='\0';i++)
   for (i = 0; i < strlen(infix); i++)
   {
      symbol = infix[i];
      switch (symbol)
      {
      case '(':
         push(symbol);
         break;
      case ')':
         while ((next = pop()) != '(')
            postfix[j++] = next;
      case '+':
      case '-':
      case '*':
      case '/':
      case '^':
         while (!isEmpty() && precedence(stack[top]) >= precedence(symbol))
            postfix[j++] = pop();
         push(symbol);
         break;
      default:
         postfix[j++] = symbol;
      }
   }
   while (!isEmpty())
      postfix[j++] = pop();
   postfix[j] = '\0';
}
int precedence(char symbol)
{
   switch (symbol)
   {
   // higher value means greater precedence
   case '^':
      return 3;
   case '/':
   case '*':
      return 2;
   case '+':
   case '-':
      return 1;
   default:
      return 0;
   }
}

void print()
{
   int i = 0;
   printf("The equivalent post fix expression is : ");
   while (postfix[i])
   {
      printf("%c", postfix[i++]);
   }
   printf("\n");
}

Infix to prefix notation

First reverse the expression.
Find the postfix of that expression.
Then reverse the postfix expression.

Stack Implementation using linked-list

For creating linked-list we should have knowlegde of structure and pointer to structure.

Structure Recap

Problem with array

So, we need a datatype that is linear but it can be stored in fragmented memories.

Linked list can work in this situation easily.

Introduction to Linked List

Linked lists are stored in non-contiguous memory location.
To add new element, we just have to create a node somewhere in the memory and get it pointed by the previous element and deleting an element is done by not pointing to that particular node.

Structure of a Linked list

Every element in a linked list is called a node and it consists of two parts, the data part, and the pointer part.
The data part stores the value, while the pointer part stores the pointer pointing to the address of the next node.
Both of these structures (arrays and linked lists) are linear data structures.

Why linked lists?

Memory and the capacity of an array remain fixed, while in linked lists, we can keep adding and removing elements without any capacity constraint.
For accessing elements arrays are better and for insertion and deletion linked lists are better.

Drawbacks of linked lists

Extra memory space for pointers is required (for ever node, extra space for a pointer is needed).
Random access is not allowed as elements are stored in non-contiguous memory locations.

Implementation

Linked lists are implemented is C language using a structure.
We know that a node contains data part and pointer so it will be implemented like this ↓

                                     
struct Node
{
      int data;
      struct Node *next; // self referencial structure.
}

Now we will create 3 node and try to connect it with each other.

                   
#include <stdio.h>
struct node
{
   int data;
   struct node *next;
};
int main()
{
   /* Initialize nodes */
   struct node *head;
   struct node *one = NULL;
   struct node *two = NULL;
   struct node *three = NULL;

   /* Allocate memory */
   one = (struct node *) malloc(sizeof(struct node));
   two = (struct node *) malloc(sizeof(struct node));
   three = (struct node *) malloc(sizeof(struct node));

   /* Assign data values */
   one->data = 1;
   two->data = 2;
   three->data = 3;

   /* Connect nodes */
   one->next = two;
   two->next = three;
   three->next = NULL;

   /* Save address of first node in head */
   head = one;
   return 0;
}

Now we have created a linear data structure like this ↓

Finally stack implementation using linked-list

Here also a node will have a data part and pointer part.
As in stack all operation occurs from top, so we will create a top pointer which will always point to the topmost element.

                     
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
      int data;
      struct node *next;
} node;
node *top = NULL;
void push();
void pop();
void display();

int main()
{
      int choice;
      while (1)
      {
         printf("\n\n-!-!-!-!-!- MENU -!-!-!-!-!-");
         printf("\n1. PUSH");
         printf("\n2. POP");
         printf("\n3. DISPLAY");
         printf("\n4. EXIT");
         printf("\n Enter your choice : ");
         scanf("%d", &choice);
         switch (choice)
         {
         case 1:
            push();
            break;
         case 2:
            pop();
            break;
         case 3:
            display();
            break;
         case 4:
            exit(0);
         default:
            printf("\nEnter a correct choice : ");
         } 
      }
      return 0;
}

void push()
{
      node *temp = (node *)malloc(sizeof(node));
      if (temp == NULL)
      {
         printf("\nOverflow");
         return;
      }
      printf("\nEnter a digit : ");
      scanf("%d", &temp->data);
      temp->next = top;
      top = temp;
}

void pop()
{
      if (top == NULL)
      {
         printf("\nUnderflow");
         return;
      }
      node *temp = top;
      top = top->next;
      printf("\n%d is deleted", temp->data);
      free(temp);
}

void display()
{
      if (top == NULL)
      {
         printf("\nUnderflow");
         return;
      }
      node *temp = top;
      while (temp != NULL)
      {
         printf("%d ", temp->data);
         temp = temp->next;
      }
}