Programmers Should Know : Five Different Stack Implementations

0
232
Stack Implementations

Data structure is core computer science and engineering subject. There are numerous data structure to organise to organise data efficiently. Stack is one of the linear data structure. It is used for applications where the data access pattern is First-In-Last-Out. The way of stack implementation is a major deciding factor in efficiency of operations on stack. This article contains five different stack implementations. Depending on the application context, one should select the right stack implementation.

Content:


1. Stack Implementation Using Array with Global Variable (Without Structure)
2. Stack Implementation Using Array with With Structure and Global Stack Variable (of type structure)
3. Stack Implementation Using Array with With Structure and Local Stack Variable (of type structure) in Main Function
4. Stack Implementation Using Linear Linked List with Global Stack Variable(Declaration at Structure Definition)
5. Stack Implementation Using Linear Linked List with Local Stack Variable in Main Function


1. Stack Implementation Using Array with Global Variable (Without Structure) [Back]


#include<stdio.h>
//#include<conio.h>
#include<stdlib.h>
#define size 5

int s[size];
int top;

int isfull()
{
if (top >= size)
    return 1;
else
    return 0;
}

void push(int item)
{
    s[top] = item;
    top++;
}

int isempty()
{
    if (top == 0)
        return 1;
    else
        return 0;
}

int pop()
{
    int item;
    top--;
    item = s[top];
    return (item);
}

void display()
{
    int i;
    if (isempty())
        printf("\nStack Is Empty!");
    else
    {
        for (i = top-1; i >= 0; i--)
        printf("\n%d", s[i]);
    }
}

void main()
{

    int item, choice;
    char ans;
    top = 0;

    printf("\n\tImplementation Of Stack");
    do 
    {
        printf("\nMain Menu");
        printf("\n1.Push \n2.Pop \n3.Display \n4.exit");
        printf("\nEnter Your Choice");
        scanf("%d", &choice);
    
        switch (choice)
        {
        case 1:
            printf("\nEnter The item to be pushed");
            scanf("%d", &item);
    
            if (isfull())
                printf("\nStack is Full, Can't Insert..!");
            else
                push(item);
            break;
    
        case 2:
            if (isempty())
                printf("\nEmpty stack..! Underflow..!!");
            else
            {
                item = pop();
                printf("\nThe popped element is %d", item);
            }
            break;
    
        case 3:
            display();
            break;
    
        default :
            printf("\n Bye...! End of Switch Case");
        }

    } while (choice != 4);

    printf("\n Bye...! End of Program");
    //getch();
}

2. Stack Implementation Using Array with With Structure and Global Stack Variable (of type structure) [Back]


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

#define size 5

struct stack{
    int s[size];
    int top;
} stk;

int isfull() {
    if (stk.top >= size)
        return 1;
    else
        return 0;
}

void push(int item) {
    stk.s[stk.top] = item;
    stk.top++;
}

int isempty() {
    if (stk.top == 0)
        return 1;
    else
        return 0;
}

int pop() {
    int item;
    stk.top–;
    item = stk.s[stk.top];
    return (item);
}

void display() {
    int i;
    if (isempty())
        printf(“\nStack Is Empty!”);
    else {
        for (i = stk.top-1; i >= 0; i–)
            printf(“\n%d”, stk.s[i]);
    }
}

void main()
{
    int item, choice;
    char ans;
    stk.top = 0;

    printf(“\n\tImplementation Of Stack”);
    do {
        printf(“\nMain Menu”);
        printf(“\n1.Push \n2.Pop \n3.Display \n4.exit”);
        printf(“\nEnter Your Choice”);
        scanf(“%d”, &choice);
        switch (choice)
        {
            case 1:
            printf(“\nEnter The item to be pushed”);
            scanf(“%d”, &item);
            if (isfull())
                printf(“\nStack is Full, Can’t Insert..!”);
            else
                push(item);
            break;
        case 2:
            if (isempty())
                printf(“\nEmpty stack..! Underflow..!!”);
            else {
                item = pop();
                printf(“\nThe popped element is %d”, item);
            }
            break;
    
        case 3:
            display();
            break;
        default :
            printf(“\n Bye…! End of Operations to be Performed”);
        }

    } while (choice != 4);
    printf(“\n Bye…! End of Program”);
    //getch();
}

3. Stack Implementation Using Array with With Structure and Local Stack Variable (of type structure) in Main Function [Back]


#include<stdio.h>
//#include<conio.h>
#include<stdlib.h>
#define size 5

struct stack {
    int s[size];
    int top;
};

int isfull(struct stack *stk) {
    if (stk->top >= size)
        return 1;
    else
        return 0;
}

void push(struct stack *stk, int item) {
    stk->s[stk->top] = item;
    stk->top++;
}

int isempty(struct stack *stk) {
    if (stk->top == 0)
        return 1;
    else
        return 0;
}

int pop(struct stack *stk) {
    int item;
    stk->top–;
    item = stk->s[stk->top];
    return (item);
}

void display(struct stack *stk) {
    int i;
    if (isempty(stk))
        printf(“\nStack Is Empty!”);
    else {
        for (i = stk->top-1; i >= 0; i–)
            printf(“\n%d”, stk->s[i]);
    }
}

void main()
{
    int item, choice;
    char ans;
    struct stack  stk;
    stk.top = 0;

    printf(“\n\tImplementation Of Stack”);
    do {
        printf(“\nMain Menu”);
        printf(“\n1.Push \n2.Pop \n3.Display \n4.exit”);
        printf(“\nEnter Your Choice”);
        scanf(“%d”, &choice);
        
        switch (choice)
        {
            case 1:
                printf(“\nEnter The item to be pushed”);
                scanf(“%d”, &item);
                if (isfull(&stk))
                    printf(“\nStack is Full, Can’t Insert..!”);
                else
                    push(&stk, item);
                break;

            case 2:
                if (isempty(&stk))
                    printf(“\nEmpty stack..! Underflow..!!”);
                else {
                    item = pop(&stk);
                    printf(“\nThe popped element is %d”, item);
                }
                break;
    
            case 3:
                display(&stk);
                break;

            default :
                        printf(“\n Bye…! End of Operations to be Performed”);
        }

    } while (choice != 4);
    printf(“\n Bye…! End of Program”);
//getch();
}

4. Stack Implementation Using Linear Linked List with Global Stack Variable(Declaration at Structure Definition)  [Back]


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

struct stack {
    int item;
    struct stack *next;
}*top;

//struct stack *top;

struct stack * get_node(int item) {
    struct stack * nnode;
    nnode = (struct stack *) malloc(sizeof(struct stack));

    if (nnode == NULL)
        printf(“\nMemory Cannot be allocated”);

    nnode->item = item;
    nnode->next = NULL;
    return (nnode);
}

void Push(int Item) {
    struct stack *nnode;
    //struct stack * get_node(int);
    nnode = get_node(Item);
    nnode->next = top;
    top = nnode;
}

int isempty() {
    if (top == NULL)
        return 1;
    else
        return 0;
}

int Pop() {
    int item;
    struct stack *temp;
    item = top->item;
    temp = top;

    top = top->next;
    free(temp);

    return (item);
}

void Display() {
    struct stack *temp;
    temp = top;

    if (isempty(temp))
        printf(“\nThe stack is empty!”);
    else {
        while (temp != NULL) {
            printf(“%d\n”, temp->item);
            temp = temp->next;
        }
    }
    //getch();
}

void main() {

    int item, choice;
    //clrscr();

    top = NULL;

    printf(“\nStack Using Linked List : nn”);
    do {
        //clrscr();
        printf(“\n\n The main menu”);
        printf(“\n1.Push \n2.Pop \n3.Display \n4.Exit”);
        printf(“\n Enter Your Choice”);
        scanf(“%d”, &choice);

        switch (choice) {
            case 1:
                printf(“\nEnter the data”);
                scanf(“%d”, &item);
                Push(item);
                break;

            case 2:
                if (isempty())
                    printf(“\nStack underflow!”);
                else {
                    item = Pop();
                    printf(“\nThe popped node is%d”, item);
                }
                break;
            case 3:
                Display();
                break;

            default:
                printf(“\n End of Program..!”);
                exit(0);
        }

    } while (choice != 4);
    //getch();
}

5. Stack Implementation Using Linear Linked List with Local Stack Variable in Main Function [ Back ]


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

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

struct stack * get_node(int item) {
    struct stack * nnode;
    nnode = (struct stack *) malloc(sizeof(struct stack));
    if (nnode == NULL)
    printf(“\nMemory Cannot be allocated”);

    nnode->item = item;
    nnode->next = NULL;
    return (nnode);
}

void Push(int Item, struct stack **top) {
    struct stack *nnode;
    //struct stack * get_node(int);
    nnode = get_node(Item);
    nnode->next = *top;
    *top = nnode;
}

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

int Pop(struct stack **top) {
    int item;
    struct stack *temp;
    item = (*top)->item;
    temp = *top;

    *top = (*top)->next;
    free(temp);
    return (item);
}

void Display(struct stack **head) {
    struct stack *temp;
    temp = *head;
    if (Sempty(temp))
        printf(“\nThe stack is empty!”);
    else {
        while (temp != NULL) {
            printf(“%d\n”, temp->item);
            temp = temp->next;
        }
    }
//getch();
}

void main() {
    struct stack *top; // top is the top of the stack.
    int item, choice;

    //clrscr();

    top = NULL;

    printf(“\nStack Using Linked List : nn”);
    do {
        //clrscr();
        printf(“\n\n The main menu”);
        printf(“\n1.Push \n2.Pop \n3.Display \n4.Exit”);
        printf(“\n Enter Your Choice”);
        scanf(“%d”, &choice);

        switch (choice) {
            case 1:
                printf(“\nEnter the data”);
                scanf(“%d”, &item);
                Push(item, &top);
                break;

            case 2:
                if (Sempty(top))
                    printf(“\nStack underflow!”);
                else {
                    item = Pop(&top);
                    printf(“\nThe popped node is%d”, item);
                }
                break;

            case 3:
                Display(&top);
                break;
    
            default:
                printf(“\n End of Program..!”);
                exit(0);
            }

    } while (choice != 4);
    //getch();
}
SHARE
Previous articleFuture of Google Search – Artificial Intelligence
Next articleSimplest Android Program to Upload and Download Data from Web Server
Dr R M Makwana
Dr. Makwana is Ph.D. in Computer Engineering, specialized in Artificial Intelligence from Sardar Patel University, Anand, Gujarat, India. Accelerated career growth from lecturer to professor in short span, having teaching experience of more than 13 years. He is TechSavvy with Research interest in Artificial Intelligence, Image Processing, Computer Vision, and Internet of Things. Actively supporting research community by providing service as a member of technical program committees of national and international conferences and workshops, as well as by reviewing journal and conference papers.

LEAVE A REPLY