Implementation of Stack in C++ (Introduction)

June 27, 2022

Introduction to Stack

A stack is another type of Data Structure,generally implemented using arrays. Generally, the implementation is LIFO i.e. Last in First out .They are used to convert prefix expression into postfix expression , balanced parenthesis problem, finding preorder of a tree.

More about Stacks

Stack can be defined as a Data Structure that serves as saving the data in a particular fashion.
In linear data structures like an array and linked list a user is allowed to insert or delete any element to and from any location respectively.
However, in a Stack, both, insertion and deletion, is permitted at one end only.
It works on the LIFO (Last In – First Out) basis, i.e, the first element that is inserted in the stack would be the last to be deleted; or the last element to be inserted in the stack would be the first to be deleted.

Stack Operations

Push: Adding a new item to the Stack Data Structure, in other words pushing new item to Stack DS. It is said to be in an overflow condition if the stack is full.
Pop: Removing an item from the stack, i.e. popping an item out. If a stack is empty then it is said to be in an underflow condition
Display: This basically display the whole stack.

Push Operation

Algorithm:

Check whether stack is full or not.
If the stack is full, it is not possible to add another element.
Otherwise, create new node, store the data and change the pointer of top to the newly created node.

Pop Operation

Algorithm:

In case of pop, note whether the stack is empty or not.
It is not possible to remove element if the stack is empty.
Else, store the top variable in temp and make top point to the next variable and delete temp.

Run

// C++ Program for Implmentation of stack (array) using structure
#include <limits.h>
#include <bits/stdc++.h>
using namespace std;
// A structure to represent a stack 
struct Stack { 
    int top; 
    int maxSize; 
    int* array; 
}; 

struct Stack* create(int max) 
{ 
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); 
    stack->maxSize = max; 
    stack->top = -1; 
    stack->array = (int*)malloc(stack->maxSize * sizeof(int));
    //here above memory for array is being created
    // size would be 10*4 = 40
    return stack; 
} 

// Checking with this function is stack is full or not
// Will return true is stack is full else false 
//Stack is full when top is equal to the last index 
int isFull(struct Stack* stack) 
{ 
    if(stack->top == stack->maxSize - 1){
        cout<<"Will not be able to push maxSize reached\n";
    }
    // Since array starts from 0, and maxSize starts from 1
    return stack->top == stack->maxSize - 1; 
} 
  
// By definition the Stack is empty when top is equal to -1 
// Will return true if top is -1
int isEmpty(struct Stack* stack) 
{ 
    return stack->top == -1; 
}

// Push function here, inserts value in stack and increments stack top by 1
void push(struct Stack* stack, int item) 
{ 
    if (isFull(stack)) 
        return; 
    stack->array[++stack->top] = item; 
    cout<<"We have pushed "<<item <<" to stack\n"; 
}

// Function to remove an item from stack.  It decreases top by 1 
int pop(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
        return INT_MIN; 
    return stack->array[stack->top--]; 
} 
  
// Function to return the top from stack without removing it 
int peek(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
        return INT_MIN; 
    return stack->array[stack->top]; 
} 

int main()
{
struct Stack* stack = create(10); 
  
    push(stack, 5); 
    push(stack, 10); 
    push(stack, 15);
    
    int flag=1;
    while(flag)
    {
        if(!isEmpty(stack))
            cout<<"We have popped"<< pop(stack)<<" from stack\n";
        else
            cout<<"Can't Pop stack must be empty\n";
        
            flag=0;
    }
    return 0;
}

We have pushed 5 to stack                         
We have pushed 10 to stack
We have pushed 15 to stack
We have popped 15 from the stack

Time Complexity
For Various Stack Operations

Push

O(1)

Pop