« Stacks Using Arrays

Stacks

1. Stack is a linear data structure like our arrays and LinkedList.
2. Stacks are abstract data type: meaning we can insert or delete elements from the stack in a very specific way unlike arrays and LinkedList. Random operatios are not allowed in Stacks.

StackUsingArrayUse.cpp

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13#include "StackUsingArray.cpp"
14int main()
15{
16    // StackUsingArray s(4);
17    // StackUsingArray s;
18    // s.push(10);
19    // s.push(20);
20    // s.push(30);
21    // s.push(40);
22    // s.push(50);
23
24    // cout << s.size() << endl;
25    // cout << s.top() << endl;
26
27    // cout << s.pop() << endl;
28
29    // cout << s.top() << endl;
30    // cout << s.size() << endl;
31
32    // cout << s.isEmpty() << endl;
33
34    StackUsingArray<char> s;
35    s.push(100);
36    s.push(101);
37    s.push(102);
38    s.push(103);
39    s.push(104);
40
41    cout << s.size() << endl;
42    cout << s.top() << endl;
43
44    cout << s.pop() << endl;
45
46    cout << s.top() << endl;
47    cout << s.size() << endl;
48
49    cout << s.isEmpty() << endl;
50
51    return 0;
52}

StackUsingArray.cpp

Copy
1#include <climits> //as we use INT_MIN
2template <typename T>
3
4class StackUsingArray
5{
6private:
7    T *data;
8    int nextIndex;
9    int capacity;
10
11public:
12    StackUsingArray()
13    {
14        data = new T[4];
15        nextIndex = 0;
16        capacity = 4;
17    }
18
19    int size()
20    {
21        return nextIndex;
22    }
23
24    bool isEmpty()
25    {
26        return (nextIndex == 0);
27    }
28
29    void push(T element)
30    {
31        if (nextIndex == capacity)
32        {
33            // cout << "Stack full!" << endl;
34            // return;
35            T *newData = new T[2 * capacity];
36            for (int i = 0; i < capacity; i++)
37            {
38                newData[i] = data[i];
39            }
40            capacity = 2 * capacity;
41            delete[] data;
42            data = newData;
43        }
44        data[nextIndex] = element;
45        nextIndex++;
46    }
47
48    T pop()
49    {
50        if (isEmpty())
51        {
52            cout << "Stack is empty!" << endl;
53            // return INT_MIN;
54            return 0; // why 0 because 0 is a standard value which can be used for any data type
55            // for int and double it will work for bool it will be false for char it will for 0 ASCII value which is null
56            // for pointers it will be treated as null pointer
57        }
58        nextIndex--;
59        return data[nextIndex];
60    }
61
62    T top()
63    {
64        if (isEmpty())
65        {
66            cout << "Stack empty!" << endl;
67            // return INT_MIN;
68            return 0;
69        }
70        return data[nextIndex - 1];
71    }
72};