A stack is a linear data structure that serves as a container of objects that are inserted and removed according to the LIFO (last-in first-out) rule.
Stack has three main operations: push, pop and peek. We have discussed about these operations in previous post and covered array and linked list implementation of stack data structure in C. In this article, stack implementation in C++ is covered using class.
Below stack implementation in C++ covers below operation –
push:Inserts a new element at the top of the stack, above its current top element.
pop:Removes the top element on the stack, thereby decrementing its size by one.
isEmpty:Returns true if stack is empty i.e. its size is zero else it returns false.
isFull:Returns true if stack is full i.e. its size has reached maximum allocated capacity else it returns false.
peek:Returns the top element present in the stack without modifying the stack.
size:Returns the count of elements present in the stack.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
#include <iostream> #include <cstdlib> using namespace std; // define default capacity of the stack #define SIZE 10 // Class for stack class stack { int *arr; int top; int capacity; public: stack(int size = SIZE); // constructor void push(int); int pop(); int peek(); int size(); bool isEmpty(); bool isFull(); }; // Constructor to initialize stack stack::stack(int size) { arr = new int[size]; capacity = size; top = -1; } // Utility function to add an element x in the stack void stack::push(int x) { if (isFull()) { cout << "OverFlow\nProgram Terminated\n"; exit(EXIT_FAILURE); } cout << "Inserting " << x << endl; arr[++top] = x; } // Utility function to pop top element from the stack int stack::pop() { // check for stack underflow if (isEmpty()) { cout << "UnderFlow\nProgram Terminated\n"; exit(EXIT_FAILURE); } cout << "Removing " << peek() << endl; // decrease stack size by 1 and (optionally) return the popped element return arr[top--]; } // Utility function to return top element in a stack int stack::peek() { if (!isEmpty()) return arr[top]; else exit(EXIT_FAILURE); } // Utility function to return the size of the stack int stack::size() { return top + 1; } // Utility function to check if the stack is empty or not bool stack::isEmpty() { return top == -1; // or return size() == 0; } // Utility function to check if the stack is full or not bool stack::isFull() { return top == capacity - 1; // or return size() == capacity; } // Stack implementation in C++ int main() { stack pt(3); pt.push(1); pt.push(2); pt.pop(); pt.pop(); pt.push(3); cout << "Top element is: " << pt.peek() << endl; cout << "Stack size is " << pt.size() << endl; pt.pop(); if (pt.isEmpty()) cout << "Stack Is Empty\n"; else cout << "Stack Is Not Empty\n"; return 0; } |
Output:
Inserting 1
Inserting 2
Removing 2
Removing 1
Inserting 3
Top element is: 3
Stack size is 1
Removing 3
Stack Is Empty
The time complexity of all stack operations is constant. i.e. O(1).
Several of the C++ Standard Library container types have push_back and pop_back operations with LIFO semantics like std::stack, std::list. Stack is also included in Java’s collection framework.
std::stack
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <stack> using namespace std; // Stack implementation in C++ using std::stack int main() { stack<string> s; s.push("A"); // Insert "A" in the stack s.push("B"); // Insert "B" in the stack s.push("C"); // Insert "C" in the stack s.push("D"); // Insert "D" in the stack // Returns the number of elements present in the stack cout << "Stack size is " << s.size() << endl; // Prints the top of the stack ("D") cout << "Top element is: " << s.top() << endl; s.pop(); // removing the top ("D") s.pop(); // removing the next top ("C") cout << "Stack size is " << s.size() << endl; // check if stack is empty if (s.empty()) cout << "Stack is Empty\n"; else cout << "Stack is not Empty\n"; return 0; } |
std::list
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <list> using namespace std; // Stack implementation in C++ using std::list int main() { list<string> s; s.push_front("A"); // Insert "A" in the stack s.push_front("B"); // Insert "B" in the stack s.push_front("C"); // Insert "C" in the stack s.push_front("D"); // Insert "D" in the stack // Returns the number of elements present in the stack cout << "Stack size is " << s.size() << endl; // Prints the top of the stack ("D") cout << "Top element is: " << s.front() << endl; s.pop_front(); // removing the top ("D") s.pop_front(); // removing the next top ("C") cout << "Stack size is " << s.size() << endl; // check if stack is empty if (s.empty()) cout << "Stack is Empty\n"; else cout << "Stack is not Empty\n"; return 0; } |
Top element is: D
Stack size is 2
Stack is not Empty
Thanks for reading.
Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply