Skip to main content

9. Stack

 

Stack

  • Stack is a linear data structure that follows the LIFO(Last-in-First-out) principle.
  • Stack has only one end.
  • It contains only one pointer top pointer pointing to the topmost element of the stack.
  • 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.

Applications of Stack

  • Functions Call: Stack plays an important role in programs that call several functions in succession. During a recursive function call, firstly the last function call ends, and at last the function which is called first ends.
  • Conversion of notations of arithmetic expression.
  • Parenthesis matching of an arithmetic expression.
  • Backtracking: It is a recursive algorithm that is used for solving the optimization problems.
  • Reversing the data.
  • Decimal to Binary conversion.

Stack ADT

In order to create a stack, we need a pointer to the topmost element and memory space for the other elements to get in and their data.

Some of the basic operations on stack are as:

  • push(): To insert or push an element into the stack.
  • pop(): To delete or remove the topmost element from the stack.
  • peek(index): To return the value at given index from top of the stack.
  • isEmpty(): To determine whether the stack is empty or not to carry efficient pop operation.
  • isFull(): To determine whether the stack is full or not to carry efficient push operation.

Array ADT for implementing Stack

struct MyStack
{
    int TotalSize;
    int Top;
    int *BaseAddress;
} stack;

void createStack(struct MyStack *a, int tsize)
{
    (*a).TotalSize = tsize;
    (*a).Top = -1;
    (*a).BaseAddress = (int *)malloc(sizeof(int) * tsize);
}

Linked List ADT for implementing Stack

struct Node
{
    int data;
    struct Node *next;
};
struct Node *top = NULL;

Algorithm for push() operation in Stack

We assume a stack whose maximum capacity is defined by MAX and Top points the topmost. Also we assume that the Top value starts from 0 while pointing the first element and new element be value.

  1. START
  2. If Top == MAX - 1
    • print "Stack is FULL, insertion not possible."
  3. Else
    1. Set Top = Top + 1
    2. Insert the value at the index of Top.
  4. END
void pushArray(struct MyStack *a)
{
    if ((*a).Top == (*a).TotalSize - 1)
    {
        printf("\n\t\t\tStack is FULL, you can't PUSH any element.");
    }
    else
    {
        (*a).Top++;
        printf("\t\t\tEnter value of element you want to push in stack: ");
        scanf("%d", &(*a).BaseAddress[(*a).Top]);
        printf("\t\t\tInsertion Successful");
    }
}

void pushLinkedList()
{
    struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
    if (temp == NULL)
    {
        printf("\t\t\tInsertion not possible...\n");
    }
    else
    {
        printf("\t\t\tEnter the value you want to push in stack: ");
        scanf("%d", &(*temp).data);
        if (top == NULL)
            (*temp).next = NULL;
        else
            (*temp).next = (top);
        top = temp;
        printf("\t\t\tInsertion Successful");
    }
}

Algorithm for pop() operation in Stack

We assume a stack whose Top points the topmost element in the stack.

  1. START
  2. If Top == -1
    • print "Stack is EMPTY, deletion not possible."
  3. Else
    1. print the value at index Top as deleted element.
    2. Set Top = Top - 1
  4. END
void popArray(struct MyStack *a)
{
    if ((*a).Top == -1)
    {
        printf("\n\t\t\tStack is EMPTY, you can't POP any element.");
    }
    else
    {
        printf("\t\t\tDeleted element: %d\n", (*a).BaseAddress[(*a).Top]);
        (*a).Top--;
    }
}


void popLinkedList()
{
    struct Node *temp;
    temp = top;
    if (top == NULL)
        printf("\t\t\tStack is EMPTY, you can't POP any element.\n");
    else
    {
        temp = top;
        top = (*top).next;
        printf("\t\t\tDeleted value: %d\n", (*temp).data);
        free(temp);
    }
}

Algorithm for peek() operation in Stack

We assume a stack whose Top points the topmost element in the stack and pos be the position whose value needs to be displayed.

  1. START
  2. If pos < 0 or pos > Top + 1
    • print "Invalid position".
  3. Else
    • print the element at index Top - position + 1
  4. END
void peek(struct MyStack *a)
{
    int position;
    if ((*a).Top == -1)
    {
        printf("\n\t\t\tStack is EMPTY, so there is no element in STACK.");
    }
    else
    {
        printf("\n\t\t\tEnter the position of element you want from top: ");
        scanf("%d", &position);
        if (position > (*a).Top + 1)
            printf("\t\t\tThe stack contains only %d elements.", (*a).Top + 1);
        else if (position < 0)
            printf("\t\t\tInvalid position...");
        else
            printf("\t\t\tThe element with position %d from top in stack = %d",
            position, (*a).BaseAddress[(*a).Top - position + 1]);
    }
}

Comments

Post a Comment