Stack Implementation Using Array

Easy
0/40
Average time to solve is 20m
profile
Contributed by
181 upvotes
Asked in companies
QualcommNatwest GroupOracle

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
2 6
1 1
1 2
2
3
4
5
Sample Output 1 :
2 
1
0
0
Explanation For Sample Output 1 :
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., 1.

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.
Sample Input 2 :
5 5
1 2
2
2 
1 1
3
Sample Output 2 :
2 
-1
1
Explanation For Sample Output 2 :
We perform the following operations on an empty stack which has a capacity of 5:

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 2 is performed, as the stack is empty, we print -1.

When operation 1 1 is performed, we insert 1 in the stack.

When operation 3 is performed, we print the top element of the stack, i.e., 1.
Constraints :
1 <= 'n', 'm' <= 10^3

Time Limit: 1 sec
Hint

Try to store the current size of the stack.

Approaches (1)
Brute Force

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’)

 

  1. Check if ‘stackSize’ is not equal to ‘N’ - 1.
    • Increment ‘stackSize’ by 1.
    • Update 'stack[stackSize]’ to ‘num’.

 

pop()

 

  1. Check if ‘stackSize’ is not equal to -1.
    • Decrease ‘stackSize’ by 1.
    • Return stack[stackSize + 1]’.
  2. Else,
    • Return -1.

 

top()

 

  1. Check if ‘stackSize’ is not equal to -1.
    • Return stack[stackSize]’.
  2. Else,
    • Return -1.

 

isEmpty()
 

  1. Check if ‘stackSize’ is not equal to -1.
    • Return 0.
  2. Else,
    • Return 1.

 

isFull()
 

  1. Check if ‘stackSize’ is not equal to ‘n’ - 1.
    • Return 0.
  2. Else,
    • Return 1.
Time Complexity

O(1)

 

We don’t traverse the array in any of the operations. Therefore, the overall time complexity will be O(1).

Space Complexity

O(N), where ‘N’ is the capacity of the stack.

 

We use extra space to store the elements of the stack. Therefore, the overall space complexity will be O(N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Stack Implementation Using Array
Full screen
Console