Stack in Data Structure

What is a Stack?

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end, whereas the Queue has two ends (front and rear). It contains only one pointer top pointer pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In other words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack. 

Working of Stack :-

  • Stack works on the LIFO pattern.
  • As we can observe in the below figure there are five memory blocks in the stack; therefore, the size of the stack is 5.
  • Suppose we want to store the elements in a stack and let's assume that stack is empty. We have taken the stack of size 5 as shown below in which we are pushing the elements one by one until the stack becomes full. 

Standard Stack Operations:- 
  • push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs.
  • pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state. 
  • isEmpty(): It determines whether the stack is empty or not.  
  • isFull(): It determines whether  the stack is full or not.' 
  • display(): It prints all the elements available in the stack.
Push operation :-
The steps involved in the PUSH operation are given below: 
  • Before inserting an element in a stack, we check whether the stack is full.  
  • If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs. 
  • When we initialize a stack, we set the value of top as -1 to check that the stack is empty.  
  • When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top. 
  • The elements will be inserted until we reach the max size of the stack. 

POP operation :- 
The steps involved in the POP operation are given below:  
  • Before deleting the element from the stack, we check whether the stack is empty. 
  • If we try to delete the element from the empty stack, then the underflow condition occurs. 
  • If the stack is not empty, we first access the element which is pointed by the top  
  • Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.  

Operations Performed on the Stack :-

1. Adding an element onto the stack (push operation) :- 
  • Push operation involves following two steps. 
  1. Increment the variable Top so that it can now refer to the next memory location. 
  2. Add element at the position of incremented top. This is referred to as adding new element at the top of the stack.
Algorithm :-
  1. begin  
  2. if top = n then stack full 
  3. top = top + 1 
  4. stack (top) : = item; 
  5. end
2. Deleting an element from a stack (POP operation) :- 
Deletion of an element from the top of the stack is called pop operation. The value of the variable top will be decremented by 1 whenever an item is deleted from the stack. The top most element of the stack is stored in an another variable and then the top is decremented by 1 the operation returns the deleted value that was stored in another variable as the result.

Algorithm :-
  1. begin 
  2. if top = 0 then stack empty; 
  3. item := stack(top);  
  4. top = top - 1; 
  5. end;  
3. Visiting Each element from a stack (Peek operation) :- 
Peek operation involves returning the element which is present at the top of the stack without deleting it. Underflow condition can occur if we try to return the top element in an already empty stack.  

Algorithm :-
  1. Begin 
  2. if top = -1 then stack empty 
  3. item = stack[top]  
  4. return item 
  5. End 
STACK PROGRAM :-
 
1.Implementation of stack using Array :-

CODE : 

#include <stdio.h>
#include <stdlib.h>

int stack[100];
int size;
int top = -1;

void push()
{
    if (top == size - 1)
        printf("\nStack is overflow.");
    else
    {
        top++;
        printf("Enter stack element : ");
        scanf("%d", &stack[top]);
    }
}

void pop()
{
    int temp;
    if (top == -1)
        printf("\nStack is underflow.");
    else
    {
        temp = stack[top];
        top--;
        printf("\nDeleted element : %d", temp);
    }
}

void topofthestack()
{
    if (top == -1)
        printf("\nStack is empty.");
    else
        printf("\nTop of the stack : %d", stack[top]);
}

void isempty()
{
    if (top == -1)
        printf("\nStack is empty.");
    else
        printf("\nStack is not empty.");
}

void display()
{
    int i;
    if (top == -1)
        printf("\nStack is empty.");
    else
    {
        printf("\nStack elements : ");
        for (i = 0; i <= top; i++)
            printf("%d ", stack[i]);
    }
}

int main()
{
    int opt;
    printf("Enter size of the stack : ");
    scanf("%d", &size);

    printf("\n1.Push  2.Pop  3.Top of the stack  4.isEmpty  5.Display ");

    while (1)
    {
        printf("\nEnter your option : ");
        scanf("%d", &opt);

        switch (opt)
        {
        case 1:
            push();
            break;
        case 2:
            pop();
            break;
        case 3:
            topofthestack();
            break;
        case 4:
            isempty();
            break;
        case 5:
            display();
            break;
        default:
            printf("\nInvalid option.");
        }
    }
    return 0;
}

Output  :



2.Implementation of stack using Linked List :-
CODE : 

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int data;
    struct Node *next;
};

struct Node *top = NULL;

/* Push Operation */
void push(int x)
{
    struct Node *newNode;
    newNode = (struct Node*)malloc(sizeof(struct Node));

    if (newNode == NULL)
        printf("Stack Overflow\n");
    else
    {
        newNode->data = x;
        newNode->next = top;
        top = newNode;
        printf("Inserted: %d\n", x);
    }
}

/* Pop Operation */
void pop()
{
    struct Node *temp;

    if (top == NULL)
        printf("Stack Underflow\n");
    else
    {
        temp = top;
        printf("Deleted element: %d\n", temp->data);
        top = top->next;
        free(temp);
    }
}

/* Peek Operation */
void peek()
{
    if (top == NULL)
        printf("Stack is Empty\n");
    else
        printf("Top element: %d\n", top->data);
}

/* isEmpty Operation */
void isEmpty()
{
    if (top == NULL)
        printf("Stack is Empty\n");
    else
        printf("Stack is Not Empty\n");
}

/* Display Stack */
void display()
{
    struct Node *temp;

    if (top == NULL)
        printf("Stack is Empty\n");
    else
    {
        temp = top;
        printf("Stack elements: ");
        while (temp != NULL)
        {
            printf("%d ", temp->data);
            temp = temp->next;
        }
        printf("\n");
    }
}

/* Main Function */
int main()
{
    int choice, value;

    while (1)
    {
        printf("\n--- Stack Using Linked List ---");
        printf("\n1. Push");
        printf("\n2. Pop");
        printf("\n3. Peek");
        printf("\n4. isEmpty");
        printf("\n5. Display");
        printf("\n6. Exit");
        printf("\nEnter your choice: ");
        scanf("%d", &choice);

        switch (choice)
        {
        case 1:
            printf("Enter value: ");
            scanf("%d", &value);
            push(value);
            break;

        case 2:
            pop();
            break;

        case 3:
            peek();
            break;

        case 4:
            isEmpty();
            break;

        case 5:
            display();
            break;

        case 6:
            exit(0);

        default:
            printf("Invalid choice\n");
        }
    }

    return 0;
}


Output  :