Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

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.

Implementation of stack in C++

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 in 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.
Pop operation in stack

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.

Code:

#include <bits/stdc++.h>
using namespace std;

 

struct Node {
    int data;
    Node *next = NULL;  
};
class Stack {
    Node *top = NULL;
    public:
        void push();  // Used to push element
        void pop();  // Used to pop element 
        void diplay(); // Used to display the stack
        ~Stack();     // Used to remove the memory
};
void Stack::push() {
    Node *temp = new Node; // Creating New node
    cout << “Enter Data: “;
    int value;
    cin >> value; 
    temp -> data = value; // Adding value
    temp -> next = top;   // Pointing to top
    top = temp;  // Changing top to current element
}
void Stack::pop() {
    if (top == NULL) {   // Check whether empty or not
        cout <<“Stack Empty\n;
    }
    else {
        Node *temp = top;
        cout << temp -> data << ” deleted\n; // Data Deleted
        top = top -> next; // Changing top to next element
        delete temp;  // Deleting the memory
    }
}
void Stack::diplay() {
    Node *temp = top;
    while (temp != NULL) {  // Printing until encounter NULL position
        cout << temp -> data << ” “;
        temp = temp -> next;
    }
    cout << endl;
}
Stack::~Stack() { // Destructor Called to delete data
    
    while (top != NULL) {
        Node *temp = top;
        cout << temp -> data << ” deleted\n”;
        top = top -> next;
        delete temp;
    }
}
int main() {
    Stack st;
    char ch;
    do {
        cout <<“Enter \n;
        cout << “1. P for push operation\n;
        cout << “2. R for pop operation\n;
        cout << “3. D for display operation\n;
        cout << “4. Q to quit\n;
        cin >> ch;
        switch(ch) {
            case ‘P’ : st.push(); break;
            case ‘R’ : st.pop(); break;
            case ‘D’ : st.diplay(); break;
        }
    }while (ch != ‘Q’);
    return 0;
}

Output:

Enter 
1. P for push operation
2. R for pop operation
3. D for display operation
4. Q to quit
P
Enter Data: 20
Enter
1. P for push operation
2. R for pop operation
3. D for display operation
4. Q to quit
P
Enter Data: 21
Enter
1. P for push operation
2. R for pop operation
3. D for display operation
4. Q to quit
R
21 deleted
Enter
1. P for push operation
2. R for pop operation
3. D for display operation
4. Q to quit
P
Enter Data: 11
Enter
1. P for push operation
2. R for pop operation
3. D for display operation
4. Q to quit
D
11 20
Enter
1. P for push operation
2. R for pop operation
3. D for display operation
4. Q to quit
Q
11 deleted
20 deleted

Time Complexity
For Various Stack Operations

Push

O(1)

 

Pop

O(1)

 

Display

O(n)

 

Space Complexity

O(n)