Last Updated: 11 Dec, 2021
Stack Implementation Using Array
Easy
Asked in companies
Stack is a data structure that follows the LIFO (Last in First out) principle. Design and implement a stack to implement the following functions:
1. Push(num): Push the given number in the stack if the stack is not full.
2. Pop: Remove and print the top element from the stack if present, else print -1.
3. Top: Print the top element of the stack if present, else print -1.
4. isEmpty: Print 1 if the stack is empty, else print 0.
5. isFull: Print 1 if the stack is full, else print 0.
You have been given ‘m’ operations which you need to perform in the stack. Your task is to implement all the functions of the stack.
Example:
We perform the following operations on an empty stack which has capacity 2:
When operation 1 1 is performed, we insert 1 in the stack.
When operation 1 2 is performed, we insert 2 in the stack.
When operation 2 is performed, we remove the top element from the stack and print 2.
When operation 3 is performed, we print the top element of the stack, i.e., 3.
When operation 4 is performed, we print 0 because the stack is not empty.
When operation 5 is performed, we print 0 because the stack is size 1, which is not equal to its capacity.
Input Format:
The first line contains two single space-separated integers, ‘n’ and ‘M’, representing the size of the stack and number of operations, respectively.
The next ‘m’ lines contain operations that have to be performed on the stack.
Output Format :
Print output of each query in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
The basic idea is to store the size of the stack while performing the operations. We keep a variable (say, ‘stackSize’) to store the size, initialized with -1.
Push: While inserting a number in the stack, we increase the size value by 1 and store it in our array at index ‘stackSize’.
When we pop the element from the stack
Pop: We check if the ‘stackSize’ value equals 0. If it is not equal to 0, we simply print the value present at index ‘stackSize’ and decrease the ‘stackSize’ value by 1.
Top: This operation is similar to the ‘Pop’ operation, we don’t decrease the ‘stackSize’ value.
isEmpty: We simply check whether the ‘stackSize’ value is -1 or not.
isFull: We check whether the value of ‘stackSize’ equals ‘n’ - 1 or not.
Here is the algorithm :
push(‘num’)
- Check if ‘stackSize’ is not equal to ‘N’ - 1.
- Increment ‘stackSize’ by 1.
- Update 'stack[stackSize]’ to ‘num’.
pop()
- Check if ‘stackSize’ is not equal to -1.
- Decrease ‘stackSize’ by 1.
- Return stack[stackSize + 1]’.
- Else,
- Return -1.
top()
- Check if ‘stackSize’ is not equal to -1.
- Return stack[stackSize]’.
- Else,
- Return -1.
isEmpty()
- Check if ‘stackSize’ is not equal to -1.
- Return 0.
- Else,
- Return 1.
isFull()
- Check if ‘stackSize’ is not equal to ‘n’ - 1.
- Return 0.
- Else,
- Return 1.