STACK

-


DATA STRUCTURES: Introduction to Stacks 

"so we all have learned about the concepts of array" but have you heard of stack ?



 In this blog post we will be learning about stack , see the ways in which stack can be implemented and have a thorough introduction to stack data structure using c programming language . The environments used are turbo c++ (discontinued) and Visual studio code .

Before going into stack data structures, you should have good understanding of array , linked list and pointers because without learning these modules we cannot implement the data structures like stack ,queue, tree etc..

What is STACK ?

Stack is linear data structure which follow lifo method (Last In First Out). In stack there is only one end for inserting data and deleting data . Inserting data is called push operation , deleting or removing data is called pop operation. Displaying the stack is called peep operation. 



Stack contains only one pointer variable called top 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 top of 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.

Some key points related to stack :-

  1.  It is known as stack because it resembles the real life stack; meaning piles of books , etc..
  2. A Stack is an abstract data type (ADT) with a pre-defined capacity, which means that it can store the elements of a limited size(Only while using stack by implementing array).
  3. It can be implemented using both (i) Arrays  (ii) Linked lists .
  4. Some general conditions : (i) Overflow (ii) Underflow .
(i) Overflow condition : A condition in which the top variable is top==MAX-1, which means is stack is fully filled ; where max is the maximum number of  space allocated in the array for data entry or maximum number of nodes created in the linked list .

Note : Both in array and linked list the counting begins from 0 and goes up to max-1.  

(ii) Underflow condition : A condition in which the top variable is  top==-1, which means stack is completely empty.

 

Basic Operations on Stack:

The operations are the same as mentioned above :
  1. push operation : add element in the stack with the use of top variable.
  2. pop operation: deletion of element  from the stack with use of top variable .
  3. peep operation : displaying the elements in the stack.
  4. reverse operation : reversing the values present inside the stack.( even thought it is not a basic operation when implementing stack with ARRAY but such operations can be performed when it is implemented using LINKED LIST)

 Working of STACK:-

  • A variable top is keep track of the position of the last value inserted in the stack.

  • At time of initialization the top variable is initialized as -1.

  • Before any value or element is added to be the stack there is checking for overflow condition ,[top==(MAX-1)].

  • Each time a new elements is added in the stack the top variable is incremented by one .

  • Before deleting any value or element in the stack there is checking for underflow condition ,[top= =-1]

  • Each time a element is removed from the top of the stack(LIFO) the top variable is decremented by one .

  • Push Operation in stack :- 

Inserting values or elements in the stack is called push operation. 

Code:-

void push()  // this is the push function
{
    if(top==(MAX-1))  // over flow checking condition            
    {
        printf("OVERFLOW, the stack is fully filled\n");
    }
     else
    {
         top=top+1; // top (pointer) variable getting incremented by 1
         printf("Enter a number\n");
         scanf("%d", &a[top]); // inserting value
    }
}

  • NOTE :- This is can be compiled both in turbo c++ compiler and in visual studio code and in a very common online compiler (online GDB) . If an online compiler or platform ( like code chiefs )is used it is better to use the code with custom input

int push(void)   // void keyword in the parenthesis signify that there are no arguments
{
    if(top==(MAX-1))  // over flow checking condition
    {
        printf("OVERFLOW, the stack is fully filled\n");
    }
    else
    {
        top=top+1;    // top (pointer) variable getting incremented
        printf("Enter a number");
        scanf("%d", &a[top]);  // inserting value
    }
    return 0;
}

  • Pop Operation in stack :-

  Deletion or removal of elements from the stack is called pop operations .

Code :-
void pop()
{
    if(top==-1)        // Under flow checking condition
   {
    printf("UNDERFLOW, the stack is empty\n");
   }
   else
   {
    printf("Deleted element in the stack is: %d\n", a[top]);  // displaying the element
    top=top-1;        //deleting the element
   }
}

Same as above the above mentioned *Note.
other online platform compiler with custom input panel .

int pop()
{
    if(top==-1)     // Under flow checking condition
    {
        printf("UNDERFLOW, the stack is empty\n");
    }
    else
    {
        printf("Deleted element in the stack is: %d\n", a[top]);    // displaying the element
        top=top-1;    //deleting the element
    }
    return 0;
}

  • Peep Operation in stack:-
Peep operation is nothing more than just displaying the elements in the stack but before displaying the elements make sure to do a checking for Underflow because after deleting the last element in the stack it will be hard to understand whether the stack is empty or full.

Code :-

void peep()
{      
    int i;
    if (top==-1)        // Under flow checking condition
    {
         printf("UNDERFLOW , the stack is empty\n");
         printf("either Terminate the program or enter values in the stack");
    }
    printf("displaying the elements in the stack .......\n");
    for (i=0;i<=top;i++)  // using loop statement to print the values inside the stack till top
    {
        printf("%d\t", a[i])
    }
    printf("\n\n");              // spacing after printing  the last element
}

Code for other online compiler with custom input 

int peep(void)
{
    int i;
    if (top==-1)
    {
        printf("UNDERFLOW , the stack is empty\n");
        printf("either Terminate the program or enter values in the stack");
    }
    printf("displaying the elements in the stack .......\n");
    for (i=0;i<=top;i++)
    {
        printf("%d\t", a[i]);
    }
    printf("\n\n");
    return 0;
}

Implementing Stack using array :-

Code :-

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 10
int top=-1,a[MAX];
void push();
void pop();
void peep();
void main()
{
    int ch;
    while(6)
    {
        printf("Enter 1 for push\nEnter 2 for pop\nEnter 3 for peep\nEnter 4 for Exit");
        scanf("%d", &ch);
        switch(ch)
        {
            case 1: push();
                printf("...................................\n");
                break;
            case 2: pop();
                printf("..................................................\n");
                break;
            case 3: peep();
                printf("...............................................\n");
                break;
            case 4: exit(0);
                break;
            default:
                printf("wrong choice\n");
        }
        getch();
    }
}
void push()
{
    if(top==(MAX-1))
    {
        printf("OVERFLOW, the stack is fully filled\n");
    }
    else
    {
        top=top+1;
        printf("Enter a number");
        scanf("%d", &a[top]);
    }
}
void pop()
{
    if(top==-1)
    {
        printf("UNDERFLOW, the stack is empty\n");
    }
    else
    {
    printf("Deleted element in the stack is: %d\n", a[top]);
    top=top-1;
    }
}
void peep()
{      
    int i;
    if (top==-1)
    {
        printf("UNDERFLOW , the stack is empty\n");
        printf("either Terminate the program or enter values in the stack");
    }

    printf("displaying the elements in the stack .......\n");
    for (i=0;i<=top;i++)
    {
        printf("%d\t", a[i]);

    }
    printf("\n\n");
}


Output :-

Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for Exit
1

Enter a number
10
...................................
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for Exit
1

Enter a number
20
...................................
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for Exit
1

Enter a number
30
...................................
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for Exit
3
displaying the elements in the stack .......
10 20 30

...............................................
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for Exit
2
Deleted element in the stack is: 30
..................................................
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for Exit
3
displaying the elements in the stack .......
10 20

............................................
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for Exit

4
......... program finished with exit code 0

To run the above code use this link https://onlinegdb.com/xf1BRnsUr
you can even edit the code and implement some thing that may come to your mind

  • Stack using linked list  :-

Although the above mentioned operations will remain same. The change is that we will be implementing stack using linked list in this program . The variable [top] which was being used like an integer variable will be made into a pointer variable and using the concepts of pointer and structure in c the linked list is implemented , because linked list is a data structure which has data and node. The node part of the linked list contains address of the next node ,thus forming a link when accessed while travesing from one node to another .

Recap:- structure is a user defined data type in c/c++, which means that it is not a homogenous data type like array and can contain different type of primitive data types in it . There are two ways to implement structure that is using struct and union keywords.

Push Operation using Linked list :-

In stack using linked list the elements are added only to one end called the top of the stack.

code :-

void push(int a)
{
    node *New;
    New=(node*)malloc(sizeof(node));
    New->info=a;
    New->next=NULL;
    if (top==NULL)
    {
        New->next=NULL;
        top=New;
        head=top;
    }
    else
    {
         top->next=New;
         top=top->next;

    }

}

A node pointer new is used to make a new node every time the push function is used .
the new node has the value stored in the info part and the address to the next node (if any) in the next part .
The top node pointer is used to keep track of the new node or otherwise know as the top of the stack .

Pop operation using Linked list :

As per the general rules of stack we know that in stack there is only one end the top of the stack the deletion also takes place at the top of stack due to lifo method.

code :-

void pop()
{
    node *tmp,*q=head;
    if (top==NULL)
    {
        printf("under flow, the stack is empty\n");
    }
    else
    {
        if(q->next==NULL)
        {
            tmp=q;
            printf("The deleted value is %d\n", top->info);
            top=NULL;
            q=top;
            head=q;
            free(tmp);
        }
        else
        {
             while(q->next->next!=NULL)
            {
                q=q->next;
            }
            printf("The deleted value is %d\n", top->info);
            tmp=top;
            top=q;
            top->next=NULL;
            free(tmp);
        }
    }
}

This is the code of the pop function of STACK using linked list.
There are two node pointers tmp and q which are  used to delete the elements present in the stack.

Peep Operation in stack using linked list  :

Displaying the elements in the stack using linked list .

code:-

void peep()
{
    node *q=head;
    if (top==NULL)
    {
        printf("Underflow, the stack is empty");
    }
    while (q!=NULL)
    {
        printf("%d\t\n",(q->info));
        q=q->next;
    }
}

Stack using linked list :- 

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
void push();
void pop();
void peep();
struct node
{
    int info;
    struct node *next;
};
typedef struct node node;
node*top=NULL;
node *head=NULL;
int main()
{
    int ch,num;
    while (7)
    {
        printf("\nEnter 1 for push\nEnter 2 for pop\nEnter 3 for peep\nEnter 4 for exit\n");
        scanf ("%d", &ch);
        switch (ch)
        {
        case 1:
            printf("Enter a value in the stack\n");
            scanf("%d", &num);
            push(num);
            break;
        case 2:
            pop();
            break;
        case 3:
            peep();
            break;
        case 4:
            exit(0);
            break;
        default:
            printf("wrong choice, Enter according to the given choices\n");
        }
        getch();
    }
   
}
void push(int a)
{
    node *New,*q=NULL;
    New=(node*)malloc(sizeof(node));
    New->info=a;
    New->next=NULL;
    if (top==NULL)
    {
        New->next=NULL;
        top=New;
        head=top;
    }
    else
    {
         top->next=New;
         top=top->next;

    }

}
void pop()
{
    node *tmp,*q=head;
    if (top==NULL)
    {
        printf("under flow, the stack is empty\n");
    }
    else
    {
        if(q->next==NULL)
        {
            tmp=q;
            printf("The deleted value is %d\n",top->info);
            top=NULL;
            q=top;
            head=q;
            free(tmp);
        }
        else
        {
             while(q->next->next!=NULL)
            {
                q=q->next;
            }
            printf("The deleted value is %d\n",top->info);
            tmp=top;
            top=q;
            top->next=NULL;
            free(tmp);
        }
    }
}
void peep()
{
    node *q=head;
    if (top==NULL)
    {
        printf("Underflow, the stack is empty");
    }
    while (q!=NULL)
    {
        printf("%d\t\n",(q->info));
        q=q->next;
    }
}

Output:


Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for exit
1
Enter a value in the stack
10
......
......
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for exit
1
Enter a value in the stack
20
......
......
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for exit
3
10
20
......
......
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for exit
2
The deleted value is 20
......
......
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for exit
2
The deleted value is 10
......
......
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for exit
2
under flow, the stack is empty
......
......
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for exit
1
Enter a value in the stack
10
......
......
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for exit
3
10
......
......
Enter 1 for push
Enter 2 for pop
Enter 3 for peep
Enter 4 for exit
4
...... program finished with exit code 0.

To run the  above code use this link https://onlinegdb.com/vGNA4aR6N
you can even edit the code and implement some thing that may come to your mind.

Some general observations of implementing stack using array and linked list :-

Stack using array vs Linked list:-

Stack using Array
Stack using linked list

1.    Array is collection of homogenous data type.

Linked list is a data structure in which data is not stored in continuous memory allocation. It has two parts (i)data (ii) node.  

2.    Since array is static memory allocation, the size of the array is fixed at the moment of declaration/initialization.

In case of linked list, it is dynamic memory allocation the size is defined at run time.

 

3.    Stack using array is not memory efficient as the total memory allocated during the initialization of the array may be left unused while only using a portion of the allocated memory and this causes memory wastage.

In case of Stack is linked list is memory efficient as the total memory allocation is done during run time and no extra memory is allocated and this reduces memory wastage.

4.    In case of stack using array no extra memory is used except from the part that is initialized to it.

In case of stack using linked list there is a usage of extra memory as there is both data part and an address part.

5.    The time complexity of stack using array is O(n).

In case of stack using linked list time complexity is O(log n).

Expressions:- 

An expression is a statements that a gives us a value when evaluated . Parsing means analyzing a string or a set of symbols one by one depending on a particular criterion.

Expression parsing is a term that means evaluation of arithmetic and logical expressions.

Whenever given an expression as a input , the computer will read it as a string and parse it to evaluate it to give a relevant output(value). An expression might look something like this example: (a+c)^(a-c)+z*x.

In data structure, expression parsing is used to evaluate logical and arithmetic expressions. We can describe arithmetic operations in the form of a notations. There are three ways to write an arithmetic expression :

  1. infix expression.
  2. prefix expression.
  3. postfix expression.

Infix Expression:-

In this expression, the operator is in between both the operands. In this form the expression can be read easily by humans. However, it is very complex for the computer to parse or evaluate it. so Whenever we give infix expression as an input in the program the compiler first converts it into postfix notation and then evaluates it.  

Postfix Expression:- 

The postfix expression is also know as reverse polish notation. In postfix expression the operators are written after the operands. The example of postfix expression is as follows : AB+D/EF-G^*.

Prefix Expression:-

The prefix expression is also know as polish notation. In this expression , the operators comes before the operands. The example of prefix expression is  as follows :     *^+XYF-YZ.






 

Comments

Post a Comment

Popular posts from this blog

HashedIn by Deloitte Coding Questions & Preparation Guide | CSFStudyPoint

-
HashedIn by Deloitte Coding Questions - CSFStudyPoint HashedIn by Deloitte Coding Questions Overview HashedIn by Deloitte is known for its rigorous recruitment process. Their assessments focus on coding proficiency, problem-solving skills, and technical expertise. Recruitment Process Pre-Placement Talk (PPT) Online Assessment Technical Interviews HR Interview Offer Confirmation Eligibility Criteria To be eligible, candidates must have a relevant degree (B.E/B.Tech/M.E/M.Tech/MCA), a minimum of 65% aggregate, and no active backlogs. Online Assessment Details The assessment includes 3 coding questions (easy, medium, hard) and is conducted on the Codility platform with a 90-minute duration. Sample Coding Question Copycat in Exam Rahul rearranges letters in copied words....
Read more

DEPRECIATION

-
Image
DEPRECIATION DEFINITION OF DEPRECIATION Depreciation may be defined as gradual and permanent decline in the value of fixed assts as a result of wear and tera , obsolescence or for any other reasons. The name "depreciation" comes from the latin word "Depretum" that means "Reduction of values", so depreciation means the reduction in the value of assets which has to be considered for determining revenue. Indian accounting standard (AS-6) states that "Depreciation is allocated" so as to change a fair proportion of depreciable account in each accounting period during the expected useful life of the asset. DETERIORATION & OBSOLESCENCE When a new technology or technical knowledge , how to capture the market and on account of that , existing assets losses its value is known as Obsolescence.                                                   ...
Read more

REPLACEMENT ANALYSIS

-
REPLACEMENT  ANALYSIS  REPLACEMENT ANALYSIS  :- Replacement analysis is a systematic assessment by a buisness of the need to replace its existing asset/assets and taking appropriate decisions there on , with the objective of maintaining / improving its financial performance. When a machine is going to replace the old machine is known as "Defender" and the new machine are known as "Challenger". If  Challenger proves the most economical in term of cost capacity, efficiency, speed of technology, and many other factors , then challenger should be accepted. REASONS FOR REPLACEMENT :- Reasons for replacement are as follows :- PHYSICAL DETERMINATION :- When a asset is put to use the value of such asset may decrease. This decrease in the value of asset is said to be due to physical wear and tear or physical deterioration. Once this type of deterioration sets in , it lead to increased maintenance repair cost on a regular basic and greater energy requires frequently. It is n...
Read more