Implementation of Stack in C++ (Introduction)

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.

Push Time ComplexityO(1)
Pop Time ComplexityO(1)
Display Time ComplexityO(n)
Space ComplexityO(n)

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:

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

Pop Operation

Algorithm:

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

C++ Program for Implementation of stack (array) using structure

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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java