Stack in Data Structure

It is an ordered list of elements of data items in which insertion as well as deletion operations takes place at only one end called as top. Stack is also called as push down list or referred as LIFO (Last In First Out). We can implement stack by using static or dynamic allocation of memory.


Stack Push-Pop Operations

Operations on Stack

  • void initialize(stack *s)
  • int isEmpty(stack *s)
  • int isFull(stack *s)
  • int pop(stack *s)
  • void push (stack *s, int data)
  • void showStackItems (stack *s)
  • void peekElement (stack *s, int index)

1. void initialize (stack * s)

It initializes a stack as an empty stack. Initial value of top is set to -1.

2. int isEmpty (stack * s)

Function checks whether the stack is empty. It returns 1 or 0 depending on whether the stack is empty or not.

3. int isFull (stack * s)

The function checks whether the stack is full. A stack is said to be full when the associated array is completely filled up. Whenever the stack is full, top points to the last element (i.e. data[SIZE-1]) of the array. The function returns 1 or 0 depending on whether the stack is full or not.

4. int pop (stack * s)

The function deletes topmost element from the stack and also returns it to the calling program. Deletion from an empty stack will cause underflow.

underflow : stack empty condition.

5. void push (stack * s, int x)

The function inserts the element x onto the stack pointed by s. Insertion will cause an overflow if the stack is full.

overflow : stack full condition.

6. void showStackItems (stack * s)

The function display all the elements of the stack and will cause an underflow if the stack is empty.

7. void peekElements (stack * s)

The function display the element of the given index in stack. If stack is empty, the function will cause as underflow.


Array Representation

A one - dimensional array can be used to hold elements of a stack. Another variable "top" is used to keep track of the index of the top most element.

Stack Declaration

struct stack
{
    int data[MAX];
    int top;
}s;


Implementation of stack using array


1. Stack Initialization

void init_stack(struct stack *s)
{
    s->top = -1;
}

2. Stack isEmpty function

int isEmpty(struct stack *s)
{
    if (s->top == -1)
    {
        printf("\nStack Underflow!!!\n");
        return (1);
    }
    else
    {
        return (0);
    }
}

3. Stack isFull function

int isFull(struct stack *s)
{
    if (s->top == MAX - 1)
    {
        printf("\nStack Overflow!!!\n");
        return (1);
    }
    else
    {
        return (0);
    }
}

4. Stack push function

void push_Stack(struct stack *s, int val)
{
    if (!isFull(s))
    {
        s->top++;
        s->item[s->top] = val;
        printf("\nInserted Element in Stack : %d\n", val);
    }
}

5. Stack pop function

int pop_Stack(struct stack *s)
{
    if (!isEmpty(s))
    {
        int val = s->item[s->top];
        s->top--;
        return val;
    }
}

6. Stack show function

void showStackItems(struct stack *s)
{
    if (!isEmpty(s))
    {
        for (int i = 0; i <= s->top; i++)
        {
            printf("Element : %d\n", s->item[i]);
        }
    }
}

7. Stack peek function

void peekElement(struct stack *s, int index)
{
    if (s->top - index + 1 < 0 || isEmpty(s))
    {
        printf("\n Cannot peek the element of the index %d \n", index);
    }
    else
    {
     printf("\nElement of the Index %d is %d \n", index, s->item[s->top - index + 1]);
    }
}

C-Program for Implementing stack using array

#include <stdio.h>
#include <stdlib.h>
#define MAX 5

struct stack
{
    int top;
    int item[MAX];
};

void init_stack(struct stack *s)
{
    s->top = -1;
}

int isStackFull(struct stack *s)
{
    if (s->top == MAX - 1)
    {
        printf("\nStack Housefull !!!\n");
        return (1);
    }
    else
    {
        return (0);
    }
}

int isStackEmpty(struct stack *s)
{
    if (s->top == -1)
    {
        printf("\nStack Empty !!!\n");
        return (1);
    }
    else
    {
        return (0);
    }
}

void push_Stack(struct stack *s, int val)
{
    if (!isStackFull(s))
    {
        s->top++;
        s->item[s->top] = val;
        printf("\nInserted Element in Stack : %d\n", val);
    }
}

void pop_Stack(struct stack *s)
{
    if (!isStackEmpty(s))
    {
        int val = s->item[s->top];
        s->top--;
        printf("\nDeleted Element of Stack : %d\n", val);
    }
}

void showStackItems(struct stack *s)
{
    if (!isStackEmpty(s))
    {
        for (int i = 0; i <= s->top; i++)
        {
            printf("Element : %d\n", s->item[i]);
        }
    }
}

void peekElement(struct stack *s, int index)
{
    if (s->top - index + 1 < 0 || isStackEmpty(s))
    {
        printf("\n Cannot peek the element of the index %d \n", index);
    }
    else
    {
        printf("\n Element of the Index %d is %d \n", index, s->item[s->top - index + 1]);
    }
}

void main()
{
    // Allocating Memory To The Stack
    struct stack *s = (struct stack *)malloc(sizeof(struct stack));

    // Variable Declaration
    int ch, element, index;

    // To Initialize Stack
    init_stack(s);

    do
    {
        printf("\nEnter your choice\n");
        printf("1. Push \n2. Pop \n3. Display\n4. Peek_Element\n5. Exit\n");
        printf("\nYour Choice : ");
        scanf("%d", &ch);

        switch (ch)
        {

        // To Push Elements In Stack
        case 1:
            printf("\nEnter element to push in stack : ");
            scanf("%d", &element);
            push_Stack(s, element);
            break;

        // To Pop Element From Stack
        case 2:
            pop_Stack(s);
            break;

        // To Show All Stack Elements
        case 3:
            printf("\nElements of stack : \n");
            showStackItems(s);
            break;

        // To Peek a Element From The Stack By Passing The Index
        case 4:
            printf("Enter The Index To Peek Element : ");
            scanf("%d", &index);
            peekElement(s, index);
            break;

        // To Terminate Execution of Program
        case 5:
            exit(0);
            break;

        // For Invalid Choice
        default:
            printf("\nSorry, Invalid Choice\n");
            break;
        }
    } while (ch > 0 && ch <= 5);
}

C-Program for Implementing stack using Linked List

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

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

struct stack *top = NULL;

int isEmpty(struct stack *top)
{
    if (top == NULL)
    {
        return (1);
    }
    else
    {
        return (0);
    }
}

int isFull(struct stack *top)
{
    struct stack *n = (struct stack *)malloc(sizeof(struct stack));
    n->data = 100;
    n->next = NULL;
    if (n == NULL)
    {
        return (1);
    }
    else
    {
        return (0);
    }
}

void StackTraversal(struct stack *top)
{
    struct stack *p = top;
    while (p != NULL)
    {
        printf("Element : %d\n", p->data);
        p = p->next;
    }
    printf("\n");
}

void push(struct stack *tp, int data)
{
    if (isFull(tp))
    {
        printf("Stack Overflow !!!\n");
    }
    else
    {
        struct stack *n = (struct stack *)malloc(sizeof(struct stack));
        n->data = data;
        n->next = tp;
        top = n;
    }
}

int pop(struct stack *tp)
{
    if (isEmpty(tp))
    {
        printf("Stack Underflow !!!\n");
    }
    else
    {
        struct stack *n = tp;
        top = tp->next;
        int val = n->data;
        free(n);
        return (val);
    }
}

void main()
{
    push(top, 25);
    printf("Elements of the Stack after Push : \n");
    StackTraversal(top);

    push(top, 31);
    printf("Elements of the Stack after Push : \n");
    StackTraversal(top);

    push(top, 02);
    printf("Elements of the Stack after Push : \n");
    StackTraversal(top);

    push(top, 100);
    printf("Elements of the Stack after Push : \n");
    StackTraversal(top);

    int element = pop(top);
    printf("Elements of the Stack after Pop %d : \n", element);
    StackTraversal(top);

    element = pop(top);
    printf("Elements of the Stack after Pop %d : \n", element);
    StackTraversal(top);

    element = pop(top);
    printf("Elements of the Stack after Pop %d : \n", element);
    StackTraversal(top);

    element = pop(top);
    printf("Elements of the Stack after Pop %d : \n", element);
    StackTraversal(top);

    element = pop(top);
    printf("Elements of the Stack after Pop %d : \n", element);
    StackTraversal(top);
}

Comments

Post a Comment

Popular posts from this blog

Searching Algorithms in Data Structure

Searching is a process of retriving or locating or finding information matching with some specific value. In data structure there are two types of searching. Linear or sequencial search Binary search   Linear or Sequencial Search It is a simplest form of searching and can be applied for sequencial storage such as array, stack, queue, linked list. Algorithm Linear/Sequencial Search Step 1: Start Step 2: Set 0 to i Step 3: Read and store value to search in val Step 4: if a(i) = val, print value is found at (i+1) position and go to step 8 Step 5: Set i to i + 1 Step 6: If i is less than n then, go to Step 4 Step 7: Print element not found Step 8: Stop n - size of array a - array val - value to be searched in array Source Code #include <stdio.h> #include <conio.h> #include <stdlib.h> int main() { int n; printf("Enter the size of array : "); scanf("%d", &n); int arr[n]; for...
Read more

Sorting Algorithms in Data Structure

Sorting is a process of arranging information either in ascending or in descending order of key values. In data structures there are techniques available to sort the data. Types of sorting algorithms Bubble sort Insertion sort Selection sort Quick sort Radix sort Merge sort   1. Bubble Sort It is one of the simplest & popular sorting method. The basic idea of this sorting is that in each pass we have to compare a successive pair of element i.e. a[i] & a[i+1]. Interchange these two values, if they are not place in proper order. Place the element in it's correct position in each pass. In first pass largest element is shifted at bottom. In second pass second largest will be shifted to the second last position & so on. Thus to sort n values n-1 passes are required. Algorithm Bubble Sort Step 1: Start Step 2: Set 1 to pass Step 3: Set o to i Step 4: if a[i]> a[i+1] then, Swap a[i] & a[i+1] Step 5: Add I to i. Step 6: If i...
Read more

Circular Linked List

Image
I n a Circular Linked List the first and the last elements are adjacent. A linked list can be made circular by storing the address of the first node in the next field of the last node. In a circular linked list, last node is connected back to the first node. In some applications, it is convenient to use circular linked list. A queue data structure can be implemented using a circular linked list, with a single pointer "rear" as the front node can be accessed through the rear node. Implementation of Circular Linked List Circular Linked List Creation and Traversal Algorithm for traversing a circular list is slightly different than the same algorithm for a singly linked list because "NULL" is not encountered. Source Code (Circular Linked List Creation and Traversal) #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; }; void CircularLinkedListTraversal(stru...
Read more