Stack (array implementation)

Introduction

Stack is a linear data structure that follows a particular order in which several type of operations like push pull are performed. The order can be LIFO or FILO, both are same so don’t be confused.

LIFO:(Last in first out) It means which element that can be filled at last that will be removed first.

FILO:(first in last out) It means that element will be removed at last which is filled at first.

Operations that can be performed:

1. push
2. pop
3. peek
4. isempty

Creation of stack

The class has three properties: arr a pointer array to store the stack elements, top to represent the topmost index in the stack, and size to specify the maximum capacity of the stack. Also, the class has a constructor that takes an integer size as a parameter and initializes the properties accordingly. The constructor allocates memory for the stack using the new keyword, sets the stack size, and initializes top to -1 to indicate that the stack is initially empty.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

//array emplementation of stack

 #include<iostream>
 using namespace std;

 class stack {
    //properties
    public:
        int *arr;
        int top;
        int size;

    //behaviour
    stack(int size) {
        this -> size = size;
        arr = new int[size];
        top=-1;
    }
 };

Push Function

The push function is part of the stack class. It adds a new element to the stack. It checks if there is space available by comparing the difference between the maximum size of the stack and the current top index. If space is available, the function increments the top index to make room for the new element, assigns the new element to the top position in the array, effectively adding it to the stack. If the stack is already full, the function prints an error message indicating “stack overflow,” signifying that the operation cannot be performed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

//push function
void push (int element) {
       if(size-top >1 ){
           top++;
           arr[top] = element;
       }
       else{
           cout << "stack overflow" << endl;
       }
   }

Pop Function

The pop function remove the topmost element from the stack, it follows the (LIFO) principle. It first checks if there are any elements in the stack by examining the value of the top index. If the top index is greater than or equal to 0, it means there is at least one element in the stack. In that case, the function decrements the top index, effectively removing the top element and making the next element (if any) the new top. However, if the top index is less than 0, it means the stack is empty, and there are no elements to remove. In this situation, the function prints an error message, “stack underflow,”.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

//pop function
void pop(){
        if(top >= 0){
            top--;
        }
        else{
            cout<< " stack underflow "<<endl;
        }

    }

Peek Function

The peek function is used to look at the topmost element of the stack without removing it. When called, the function first checks if there are any elements in the stack by examining the value of the top index. If the top index is greater than or equal to 0, it means there is at least one element in the stack. In this case, the function returns the value of the element at the top position. However, if the top index is less than 0, it means the stack is empty, and there are no elements to peek at. In this situation, the function prints an error message, “stack is empty,” and returns -1 to indicate that there’s no valid element to return.

1
2
3
4
5
6
7
8

int peek() {
        if(top >=0 )
            return arr[top];
        else{
            cout <<"stack is empty "<<endl;
            return -1;
        }
    }

IsEmpty function

The isempty function is used to check whether the stack is empty or not. When called, the function examines the value of the top index, which represents the position of the topmost element in the stack. If the top index is equal to -1, it means there are no elements in the stack, and it is considered empty. In this case, the function returns true to indicate that the stack is empty. However, if the top index is not -1, it means there is at least one element in the stack, and it is not empty. In this situation, the function returns false to indicate that the stack is not empty. In summary, the isempty function provides a convenient way to check the emptiness status of the stack, returning true if it’s empty and false if it contains elements.

1
2
3
4
5
6
7
8

bool isempty(){
        if(top == -1){
            return true;
        }
        else{
            return false;   
        }
    }

The main function

In this C++ code, the main function demonstrates the usage of a stack. Firstly, it creates a stack object st with a size of 5. Then, it uses the push function to add three elements (22, 33, and 44) to the stack. The peek function is called to print the top element 44. Subsequently, the pop function is used to remove the top element from the stack, and peek is called again to print the new top element 33. This process is repeated two more times with the last element 22 being popped, and peek is called again, but the stack is now empty. Finally, the isempty function is called to verify if the stack is empty, and it prints stack is empty as the output, confirming that the stack is empty at this point.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int main(){
    stack st(5);

    st.push(22);
    st.push(33);
    st.push(44);
    cout << st.peek()<<endl;
    st.pop();
    cout << st.peek()<<endl;
st.pop();
    cout << st.peek()<<endl;
    st.pop();
    cout << st.peek()<<endl;

    if(st.isempty()){
        cout<< "stack is empty"<<endl;
    }
    else
    cout<<"stack is not empty"<<endl;
 }

output of the following code

 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

//array emplementation of stack

 #include<iostream>
 
 using namespace std;

 class stack {
    //properties
    public:
        int *arr;
        int top;
        int size;

    //behaviour
    stack(int size) {
        this -> size = size;
        arr = new int[size];
        top=-1;
    }

    void push (int element) {
        if(size-top >1 ){
            top++;
            arr[top] = element;
        }
        else{
            cout << "stack overflow" << endl;
        }
    }

    void pop(){
        if(top >= 0){
            top--;
        }
        else{
            cout<< " stack underflow "<<endl;
        }

    }

    int peek() {
        if(top >=0 )
            return arr[top];
        else{
            cout <<"stack is empty "<<endl;
            return -1;
        }
    }

    bool isempty(){
        if(top == -1){
            return true;
        }
        else{
            return false;   
        }
    }

 };

 int main(){
    stack st(5);

    st.push(22);
    st.push(33);
    st.push(44);
    cout << st.peek()<<endl;
    st.pop();
    cout << st.peek()<<endl;
st.pop();
    cout << st.peek()<<endl;
    st.pop();
    cout << st.peek()<<endl;

    if(st.isempty()){
        cout<< "stack is empty"<<endl;
    }
    else
    cout<<"stack is not empty"<<endl;
 }