Time Complexity of Operations

stackTop, stackBottom & Time Complexity of Operations in Stack Using Arrays

In the last documents, we discussed the peek operation and its implementation in C using arrays. Today, we will explore some new stack operations.

Breathe easy, as the concepts we are covering today are among the simplest. We will start by learning about two operations in stacks: stackTop and stackBottom.

Let’s consider a stack array for better understanding.

stackTop:

This operation returns the topmost element in a stack. Retrieving the topmost element is straightforward. We can use the stack member top to fetch the topmost index and its corresponding element. For example, if the top member is at index 2, the stackTop operation will return the value at that index.

stackBottom:

This operation returns the bottommost element in a stack, which is the element at index 0. We can simply access the bottommost index (0) and return the corresponding element. If the bottommost element is at index 0, then the stackBottom operation will return that value.

Both of these operations have a constant runtime of O(1) since they involve accessing elements at specific indices in an array.

Time complexities of other operations:

• isEmpty( ): Checks if the top member equals -1, working in O(1).
• isFull( ): Checks if the top member equals size - 1, also O(1).
• push( ): Involves increasing the top by 1 and inserting the element, which is O(1).
• pop( ): Decreases the top by 1 and returns the ignored element, which is O(1).
• peek( ): Returns the element at the index (top - position + 1), also O(1).

Thus, all the operations we discussed have a constant time complexity.

Implementation:

I encourage you to implement these on your own before moving ahead. Below is a snippet for your reference.

Understanding the snippet below:

1. First, copy everything we have covered up to this point into your IDE. I want to avoid repetition to keep it concise.
2. Ensure you have all the functions and declarations set up.
3. Create an integer function stackTop, passing the reference to the stack as a parameter, and return the element at the index top of the array. That’s it!

int stackTop(struct stack* sp){
    return sp->arr[sp->top];
}

Code Snippet 1: Implementing stackTop

4. Create an integer function stackBottom, and pass the reference to the stack you created as a parameter. And then return the element at the index 0 of the array.

int stackBottom(struct stack* sp){
    return sp->arr[0];
}

Code Snippet 2: Implementing stackBottom

Here is the whole source code:

#include<stdio.h>
#include<stdlib.h>
 
struct stack{
    int size ;
    int top;
    int * arr;
};
 
int isEmpty(struct stack* ptr){
    if(ptr->top == -1){
            return 1;
        }
        else{
            return 0;
        }
}
 
int isFull(struct stack* ptr){
    if(ptr->top == ptr->size - 1){
        return 1;
    }
    else{
        return 0;
    }
}
 
void push(struct stack* ptr, int val){
    if(isFull(ptr)){
        printf("Stack Overflow! Cannot push %d to the stack\n", val);
    }
    else{
        ptr->top++;
        ptr->arr[ptr->top] = val;
    }
}
 
int pop(struct stack* ptr){
    if(isEmpty(ptr)){
        printf("Stack Underflow! Cannot pop from the stack\n");
        return -1;
    }
    else{
        int val = ptr->arr[ptr->top];
        ptr->top--;
        return val;
    }
}
 
int peek(struct stack* sp, int i){
    int arrayInd = sp->top -i + 1;
    if(arrayInd < 0){
        printf("Not a valid position for the stack\n");
        return -1;
    }
    else{
        return sp->arr[arrayInd];
    }
}
 
int stackTop(struct stack* sp){
    return sp->arr[sp->top];
}
 
int stackBottom(struct stack* sp){
    return sp->arr[0];
}
 
int main(){
    struct stack *sp = (struct stack *) malloc(sizeof(struct stack));
    sp->size = 50;
    sp->top = -1;
    sp->arr = (int *) malloc(sp->size * sizeof(int));
    printf("Stack has been created successfully\n");
 
    printf("Before pushing, Full: %d\n", isFull(sp));
    printf("Before pushing, Empty: %d\n", isEmpty(sp));
    push(sp, 1);
    push(sp, 23);
    push(sp, 99);
    push(sp, 75);
    push(sp, 3);
    push(sp, 64);
    push(sp, 57);
    push(sp, 46);
    push(sp, 89);
    push(sp, 6);  
    push(sp, 5);  
    push(sp, 75);  
    
    // // Printing values from the stack
    // for (int j = 1; j <= sp->top + 1; j++)
    // {
    //     printf("The value at position %d is %d\n", j, peek(sp, j));
    // }
     
    return 0;
}

Code Snippet 3: Implementing stackTop & stackBottom

Now, since we have done pushing elements into the stack, we can call our functions, stackTop and stackBottom.

    printf("The top most value of this stack is %d\n", stackTop(sp));
    printf("The bottom most value of this stack is %d\n", stackBottom(sp));

Code Snippet 4: Calling functions stackTop & stackBottom

And the output we received was:

The top most value of this stack is 75  
The bottom most value of this stack is 1
PS D:\Code>

Figure 1: Output of the above program