Sunday, 5 March 2017

Stack data structure with program

Stacks

Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects. A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates, etc.

A real-world stack allows operations at one end only. For example, we can place or remove a card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations at one end only. At any given time, we can only access the top element of a stack.


Basic features of Stack
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the element which is placed (inserted or added) last, is accessed first. In stack terminology, insertion operation is called PUSH operation and removal operation is called POP operation.
  1. Stack is an ordered list of similar data type.
  2. Stack is a LIFO structure. (Last in First out).
  3. push() function is used to insert new elements into the Stack and pop() is used to delete an element from the stack. Both insertion and deletion are allowed at only one end of Stack called Top.
  4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.


Applications of Stack
·         To reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack.
·         An "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
o    Undo/Redo stacks in Excel or Word.
·         Language processing :
o    space for parameters and local variables is created internally using a stack.
o    compiler's syntax check for matching braces is implemented by using stack.
·         A stack of plates/books in a cupboard.
·         A garage that is only one car wide. To remove the first car in we have to take out all the other cars in after it.
·         Wearing/Removing Bangles.
·         Back/Forward stacks on browsers.
·         Support for recursion
o    Activation records of method calls.


Implementation of Stack

Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size. Here we will implement Stack using array.


Program

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <stdio.h>
#include <conio.h>
#define MAXSIZE 5

typedef struct stack /* Structure definition for stack */
{
    int stk[MAXSIZE];
    int top;
}STACK ;
STACK s;

/* Function declaration/Prototype*/

void push (void);
int pop(void);
void display (void);
main ()
{
    int choice,option;
    //clrscr ();
    option = 1;
    s.top = -1;
    
    printf ("STACK OPERATIONn");
    while (option)
    {
        printf ("------------------------------------------n");
        printf (" 1 --> PUSH n");
        printf (" 2 --> POP n");
        printf (" 3 --> DISPLAY n");
        printf (" 4 --> EXIT n");
        printf ("------------------------------------------n");
        
        printf ("Enter your choicen");
        scanf ("%d", &choice);
        
        switch (choice)
        {
            case 1: push();
            break;
            case 2: pop();
            break;
            case 3: display();
            break;
            case 4: return 0;
        }
        
        fflush (stdin);
        printf ("Do you want to continue(Type 0 or 1)?n");
        scanf ("%d", &option);
    }
    
}

/*Function to add an element to the stack*/
void push ()
{
    int num;
    if (s.top == (MAXSIZE - 1))
    {
        printf ("Stack is Fulln");
        return;
    }
    else
    {
        printf ("Enter the element to be pushedn");
        scanf ("%d", &num);
        s.top = s.top + 1;
        s.stk[s.top] = num;
    }
    return;
}

/*Function to delete an element from the stack*/
int pop ()
{
    int num;
    if (s.top == - 1)
    {
        printf ("Stack is Emptyn");
        return (s.top);
    }
    else
    {
        num = s.stk[s.top];
        printf ("poped element is = %dn", s.stk[s.top]);
        s.top = s.top - 1;
    }
    return(num);
}

/*Function to display the status of the stack*/
void display ()
{
    int i;
    if (s.top == -1)
    {
        printf ("Stack is emptyn");
        return;
    }
    else
    {
        printf ("nThe status of the stack isn");
        for (i = s.top; i >= 0; i--)
        {
            printf ("%dn", s.stk[i]);
        }
    }
    printf ("n");
}
Posted by at
Labels: ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)