Understanding Stack Data Structure and Implementing it using Arrays and Linked Lists in C

QuantumO0O
10 Oct, 2022

There are certain situations in which we need to insert and remove an item from the beginning or end of the list. Stack is a linear structure in which an item may be inserted or removed only at one end, is called "Top of the Stack".

Ex: Depicted a stack of dishes 

stack data structure

A Stack of dishes


We can see that any item or dish may be inserted or removed only at the top of the Stack. It concludes the Item that was inserted last will be removed first. therefore, stacks are also called LIFO(Last In First Out) or FILO(First In Last Out) 

Generally, two approaches use in Stack named Push & Pop.

  1. Push is used to insert an item at the top
  2. Pop is used to delete an item at the top
Now we see the Push & Pop Operation 
  1. stack is empty
  2. a list of elements to be inserted in the stack
  3. A variable top helps us to keep track of the location at which insertion or deletion of items may be done.

Push Operation

Push Operation 



Pop Operation

Pop Operation



Abstract Data Type-Stack

Implementation of Stock with array

Stacks may be represented in the computer in various ways, it may represent by a one-way list or a linear array. for implementation of Push operation, the Algorithm is:-

Step 1:    [Check the stack overflow]
                            if tos>=MAXSTACK (tos pointer use to denote the position of top most item)
                            (MAXSTACK represents the maximum possible no.of elements in stock)
                            print "Stack overflow" and exit
Step 2:    [Increment the pointer value by one]
                            tos=tos+1
Step 3:    [Insert Item]
                            arr[tos]=value (Stock represent by arr[])
Step 4:    Exit
        
For the implementation of the Pop operation, the algorithm is:-

Step 1:    [Check whether the stack is empty]
                            if tos=0
                            print "Stock underflow" and exit
Step 2:    [Remove the top most item]
                            value = arr[tos]
                            tos=tos-1
Step 3:    [Return the item of the stack]
                            return(value)


CODE : Implementation of Stock with Array


#include<stdio.h>

int choice, stack[10], top, element;

void menu();

void push();

void pop();

void showelement();

void main() {

    choice = element = 1;

    top = 0;

    menu();

}

/* define the menu function*/

void menu() {

    printf("Enter the one of the following option\n");

    printf("PUSH 1\nPOP 2\nShowElement 3\nExit 4\n");

    scanf("%d", & choice);

    if (choice == 1) {

        push();

        menu();

    }

    if (choice == 2) {

        pop();

        menu();

    }

    if (choice == 3) {

        showelement();

        menu();

    }

    if (choice == 4) {

    }

}

void push() {

    if (top <= 9)

    {

        printf("Enter the element to be push in the stack:\n");

        scanf("%d", & element);

        stack[top] = element;

        ++top;

    } else {

        printf("Stack is full\n");

    }

}

void pop() {

    if (top > 0) {

        --top;

        element = stack[top];

        printf("Poped element %d\n", element);

    } else {

        printf("Stack is empty\n");

    }

    return;

}

void showelement() {

    if (top <= 0) {

        printf("Stack is empty \n");

    } else {

        for (int i = 0; i < top; ++i) {

            printf("%d\n", stack[i]);

        }

    }

}

Output


Enter the one of the following option
PUSH 1
POP 2
ShowElement 3
Exit 4
1
Enter the element to be push in the stack:
1
Enter the one of the following option
PUSH 1
POP 2
ShowElement 3
Exit 4
1
Enter the element to be push in the stack:
2
Enter the one of the following option
PUSH 1
POP 2
ShowElement 3
Exit 4
3
1
2
Enter the one of the following option
PUSH 1
POP 2
ShowElement 3
Exit 4
2
Poped element 2
Enter the one of the following option
PUSH 1
POP 2
ShowElement 3
Exit 4
3
1
Enter the one of the following option
PUSH 1
POP 2
ShowElement 3
Exit 4
4
 

Implementation of Stock with Linked List

When a Stack is implemented by using an array, it suffers from the basic limitation of an array, that is size cannot be increased or decreased once it is declarer. This problem can be overcome if we implement a stack using a Linked List. In the case of Linked Stack, we can Push and Pop nodes at the one end of a Linked List. Each node in the Linked List contains the data and pointer that gives the location of the next node in the List. 

CODE: Implementation of Stock with Linked List

Algorithm:-


Step 1:     [defineLinked List Struct with next and pre pointer]
  •                   next pointer for address of next node
  •                   pre node for address of previous node 
Step 2:     [Create Manu] Choose the option
Step 3:     [Push Linked list node]   
  •                  check sufficient Memory Space  
  •                  add the data in data pointer
  •                  allocate memory space to next pointer and copy node address
  •                  move next node and paste previous node address in pre pointer
  •                  return to Step 2
Step 4:      [Pop Linked list node]
  •                   check, is node empty
  •                   read the pop data
  •                   remover last node
  •                   return to Step 2  
Step 5:      [display the stack]
  •                   check, is node empty
  •                   move the previous node for print data until pre pointer ==NULL

Code

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define NULL 0
 
 /* Definition of the structure node */
typedef struct node
{
    int data;
    struct node *next;
    struct node *pre;
} node;
 
 /* Definition of push function */
node * push(node *tos,int item)
{
    node *temp;
    temp=(node*)malloc(sizeof(node)); /* create a new node dynamically */
    if(temp==NULL) /* If sufficient amount of memory is */
    {               /* not available, the function malloc will */
        printf("\nError: Insufficient Memory Space"); /* return NULL to temp */
        getch();
        return;
    }
    else /* otherwise*/
    {
        tos->data=item;/* put the item in the data portion of node*/
        temp->pre=tos;/* save the current node add. in the temp->next ponter*/
        tos->next=(node*)malloc(sizeof(node)); /*insert new tos->next node for next node*/
        tos->next->pre=temp->pre;/*copy to current node add. into
         next node tos->next->pre pointer*/
        tos=tos->next;/*move to next node last node data always NULL*/
        return(tos);
    }
}
 
/* Definition of pop function */
node * pop(node *tos)
{
    node *temp;
    int item;
    if(tos->pre==NULL)
        return(NULL);
    else
    {
         /* To pop an element from stack, remove the front*/
        item=tos->pre->data; /*get data of Last Node */
        temp=tos->pre;/*copy new last node add. */
        tos=tos->pre;/* remove last node and set new last node */
        /* in stock Last in First Out */
        if(item!=NULL);
            printf("\n Detected item is%d",item);
        return (tos);
 }
}
 
 
/* Definition of display function */
void display(node *tos)
{
    
    if(tos->pre==NULL) /* Check whether the stack is empty*/
    {
        printf("\nStack is empty");
        return;
    }
    else
    {   
        
        while(tos->pre!=NULL)
        {
        
            tos=tos->pre;
            printf("\n%d",tos->data); /* display all the values of the stack*/
             /* from the front node to the last node*/
        }
    }
} /*end of function display*/
 
 
/* Definition of main function */
void main()
{
    int item, ch;
    int choice=1;
    node *p;
    
    do
    {
        //clrscr();
        printf("\t\t\t\t*****MENU*****"); 
        printf("\n\t\t\t1. To PUSH an element");
        printf("\n\t\t\t2. To POP an element");
        printf("\n\t\t\t3. To DISPLAY the elements of stack");
        printf("\n\t\t\t4. Exit");
        printf("\n\n\n\t\t\tEnter your choice:-");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1:
            printf("\n Enter an element which you want to push ");
            scanf("%d",&item);
            p=push(p,item);
            break;
            case 2:
            p=pop(p);
            
            break;
            case 3:
            printf("\nThe elements of stack are");
            display(p);
            break;
            case 4:
            exit(0);
        } /*switch closed */
      
    } while(choice==1);
}

Output

                           *****MENU*****
                        1. To PUSH an element
                        2. To POP an element
                        3. To DISPLAY the elements of stack
                        4. Exit


                        Enter your choice:-1

 Enter an element which you want to push 5


                         *****MENU*****
                        1. To PUSH an element
                        2. To POP an element
                        3. To DISPLAY the elements of stack
                        4. Exit


                        Enter your choice:-3

The elements of stack are
5
4
3
2
1
1

                            *****MENU*****
                        1. To PUSH an element
                        2. To POP an element
                        3. To DISPLAY the elements of stack
                        4. Exit


                        Enter your choice:-2

 Detected item is5

                                              *****MENU*****
                        1. To PUSH an element
                        2. To POP an element
                        3. To DISPLAY the elements of stack
                        4. Exit


                        Enter your choice:-4 

 

Next Post Previous Post
No Comment
Add Comment
comment url