Stack Implementation using Templates in C++
In the previous post, we have discussed the C++ implementation of the stack data structure using classes. In this article, we will make code generic for all data types by using C++ templates.
The stack can be implemented as follows using templates in C++:
|
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 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
#include <iostream> #include <cstdlib> using namespace std; // Define the default capacity of a stack #define SIZE 10 // A class to represent a stack template <class X> class stack { X *arr; int top; int capacity; public: stack(int size = SIZE); // constructor void push(X); X pop(); X peek(); int size(); bool isEmpty(); bool isFull(); // destructor ~stack() { delete[] arr; } }; // Constructor to initialize the stack template <class X> stack<X>::stack(int size) { arr = new X[size]; capacity = size; top = -1; } // Function to add an element `x` to the stack template <class X> void stack<X>::push(X x) { if (isFull()) { cout << "Overflow\nProgram Terminated\n"; exit(EXIT_FAILURE); } cout << "Inserting " << x << endl; arr[++top] = x; } // Function to pop the top element from the stack template <class X> X stack<X>::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--]; } // Function to return the top element of the stack template <class X> X stack<X>::peek() { if (!isEmpty()) { return arr[top]; } else { exit(EXIT_FAILURE); } } // Utility function to return the size of the stack template <class X> int stack<X>::size() { return top + 1; } // Utility function to check if the stack is empty or not template <class X> bool stack<X>::isEmpty() { return top == -1; // or return size() == 0; } // Utility function to check if the stack is full or not template <class X> bool stack<X>::isFull() { return top == capacity - 1; // or return size() == capacity; } int main() { stack<string> pt(2); pt.push("A"); pt.push("B"); pt.pop(); pt.pop(); pt.push("C"); // Prints the top of the stack cout << "The top element is " << pt.peek() << endl; // Returns the total number of elements present in the stack cout << "The stack size is " << pt.size() << endl; pt.pop(); // check if the stack is empty or not if (pt.isEmpty()) { cout << "The stack is empty\n"; } else { cout << "The stack is not empty\n"; } return 0; } |
Output:
Inserting A
Inserting B
Removing B
Removing A
Inserting C
The top element is C
The stack size is 1
Removing C
The stack is empty
The time complexity of all stack operations is constant, i.e., O(1).
Also See:
Stack Implementation using a Linked List – C, Java, and Python
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)