× Home

Introduction to Stack

Introduction:

Stack is a linear data structure.Operations on stack are performed in LIFO (Last in First Out) order

This means the element to enter the container last would be the first one to leave the container. It is imperative that elements above an element in a stack must be removed first before fetching any element.

Applications of Stack:

  • Used in function calls
  • Infix to postfix conversions (and other similar conversions)
  • Parenthesis matching & more...

Stack ADT

In order to create a stack we need a pointer to the top element along with other elements whicha re stored in the stack.
Some of the operations of stack ADT are:

  • Push() → push an element into the stack
  • pop() → remove the topmost element from the stack
  • peak() → value at a given position is ventured
  • isEmpty()/isFull() → determines whether the stack is empty or full.

Implementation

A stack is a collection of elements with certain operation following LIFO (Last in First Out) discipline.
A stack can be implemented using an array or a linked list.

Stack using an Array

If we racall, arrays are linear data structures whose elemwnts are indexed, and the elements can be accessed in constant time with their index. To implement a stack using an array, we'll aintain a variaable that will store the index of the top element.

We have few things to keep in check when we implement stacks using arrays.

1. A fixed-size array → This size can even be bigger than the size of the stack we are trying to implement, to stay on the safe side.
2. An interger variable to store the index of the top element. → or the last element we entered in the array. This value is -1 when there is no element in the array.

We will try constructing a structure to embed all these functionalities. Let's see how.

struct stack{
int size;
int top;
int *arr;
}

So, the struct above includes as its members, the size of the array, the index of the top element, and the pointer to the array we will make.
To use this struct.
You will just have to declare a struct stack, set its top element to -1.
Furthermore, you will have to reserve memroy in the heap using malloc.

Follow the example below for defining a stack:

struct stack S;
S.size = 80;
S.top = -1;
S.arr = (int *)malloc(S.size*sizeof(int));

Code for Implementing stack using array

Before using operations we will create and implement some functions so that operation get easy.

1. so, the first thing would be to create the struct stack which include three members, an interger variable to store the size of the stack, an interger variable to store the index of the topmost element, and an interger pointer to hold the address of the array.

struct stack
{
int size;
int top;
int *arr;
}

2. In main, create a stuck stack s, assign value.

Here We are defining a struct stack pointer s, and use the arrow operators to deal with their members. The advantage of this method is that we can pass these pointers as references into functions very conveniently.

struct stack *s; // we are making this so
that we can pass this into a fuction
s->size = 80;
s->top=-1;
s->arr=(int *)malloc(s->size*sizeof(int));

3. Before we advance to pushing elements in this stack, there are a few conditons to deal with. We can only push an element in this stack if there is some space left or the top is not equal to the last index.
Similarly, we can only pop an element from this stack if some element is stored or the top is not equal to -1.

4. Crate a function which checks if the top is equal to -1. If yes, then it’s empty and returns 1; otherwise, return 0.

int isEmpty(struct stack *ptr)
{
if (ptr->top == -1){
return 1;
}
else{
return 0;
}
}

5. Create an integer function isFull, and pass the pointer to the stack as a parameter. In the function, check if the top is equal to (size-1). If yes, then it’s full and returns 1; otherwise, return 0.

int isFull(struct stack *ptr)
{
if (ptr->top == ptr->size - 1)
{
return 1;
}
else
{
return 0;
}
}

6. conditions to check if the stack is empty or not.

if(isEmpty(s)){
printf("The stack is empty");
}
else{
printf("The stack is not empty");
}

Stack Operations

push()

By pushing, we mean inserting an element at the top of the stack. While using the arrays, we have the index to the top element of the array. So, we'll just insert the new element at the index (top+1) and increase the top by 1. This operation takes a constant time, O(1). It's intutive to note that this operation is valid until (top+1) is valid index and the array has an empty space.

Suppose we have an element x to insert in a stack array of size 4. We first checked if it was full, and found it was not full. We retrieved its top which was 3 here. We made it 4 by increasing it once. Now, just insert the element x at index 4, and we are done.

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;
}
}

pop()

Pop means to remove the last element entered in the stack, and that element has the index top. So, this becomes an easy job. We'll just have to decrease the value of the top by 1, and we are done. Thi popped element can even be used in any way we like.

Suppose we make a pop call in a stack array of size 4. We first checked if it was empty, and found it was not empty. We retrieved its top which was 4 here. Stored the element at 4. We made it 3 by decreasing it once. Now, just return the element x, and popping is done.

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;
}
}

peek()

Peeking into something literally means to quickly see what’s there at someplace. In a similar way, it refers to looking for the element at a specific index in a stack.

Peek operation requires the user to give a position to peek at. Here, position refers to the distance of the current index from the top element +1.

The index, mathematically, is (top -position+1).

So, before we return the element at the asked position, we’ll check if the position asked is valid for the current stack. Index 0, 1 and 2 are valid for the stack illustrated above, but index 4 or 5 or any other negative index is invalid.

Note: peek(1) returns 12 here. Now, since we are done with all the basics of the peek operation, we can try writing its code as well. Here, we’ll focus mainly on the peek operation, so you can just copy the codes from the last tutorial, where we learned writing push and pop, isFull and isEmpty.


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];
}
}

More on stack

stackTop:

This operation is responsible for returning the topmost element in a stack. We can just use the stack member top to fetch the topmost index and its corresponding element.

Here, in the illustration above, we have the top member at index 2. So, the stackTop operation shall retrun the value 22.

stackBottom:

This operation is respoinsible for returning the bottommost element in a stack, which intuitively, is the element at index 0.

Implementation of stackTop and stackBottom

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

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

The time complexitites of these operations.

stackTop & stackBottom: these operations happen to work in a constant runtime, that is O(1). Because we are just accessing an element at an index, and that works in a constant time in an array.

isEmpty(): This operation just checks if the top member equals -1. This works in a constant time, hence, O(1).

isEmpty(): This operation just checks if the top member equals -1. This works in a constant time, hence, O(1).

ifFUll(): This operation just checks if the top member equals is size -1. Even this works in a constant time, hence, O(1).

push(): Pushing an element in a stack needs you to just incres the value of top by 1 and insert the element at the index. This is again a case of O(1).

pop(): Popping an element in a stack neds you to just decrease the value of top by 1 and return the element we ignored. This is again a case of O(1).

Peek(): Peeking at a poisition just returns the element at the index, (top - poisition + 1), which happens to work in a constant time, So, even this is an example of O(1).

So, basically all the operations we discussed follow a constant time complexity.

#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)
{
int hold;
if (isEmpty(ptr))
{
printf("Stack underflow");
return -1;
}
else
{
hold = ptr->arr[ptr->top];
ptr->top--;
return hold;
}
}

int peek(struct stack *ptr, int i)
{
int arrInd = ptr->top - i + 1;
if (arrInd < 0)
{
printf("Not a valid position for the stack\n");
return -1;
}
else
{
return ptr->arr[arrInd];
}
}

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

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

int main()
{
struct stack *s = (struct stack *)malloc(sizeof(struct stack)); // we are making this so that we can pass this into a fuction
s->size = 10;
s->top = -1;
s->arr = (int *)malloc(s->size * sizeof(int));

push(s, 55);
push(s, 56);
push(s, 57);
push(s, 58);
push(s, 59);
push(s, 60);
// printf("just poped %d\n", pop(s));

// printing value from the stack
for (int i = 0; i <= s->top + 1; i++)
{
printf("The value at position %d is %d\n", i, peek(s, i));
}
printf(" Stacktop : %d\n", stackTop(s));
printf(" Stacktbottom : %d", stackBottom(s));
return 0;
}