Implement Stack Using Array

Table Of Contents

Problem Statement
Solution
LIFO Principle
Operations on Stack
Algorithm
Code
Time Complexity
Space Complexity

Problem Statement

Design stack data structure using an array. Implement push(), pop(), and peek() operation in constant time.

Solution

In this chapter, you will learn about the stack data structure and its implementation in Java, Python, and C++.

A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted into the stack is removed first.

You can think of the stack data structure as a pile of plates on top of another.

Here, you can:

Put a new plate on top – push()
Remove the top plate – pop()

And, if you want the plate at the bottom, you must first remove all the plates on top. This is exactly how the stack data structure works.

LIFO Principle

In programming terms, putting an item on top of the stack is called push() and removing an item is called pop().

In the above visualization, item 30 was kept last, but it was removed first. This is precisely how the LIFO (Last In First Out) Principle works.

Operations on Stack

There will be 5 basic operations:

isEmpty() : To check whether the stack is empty or not.
isFull() : To check whether the stack is full or not.
push(item) : To insert an item into the stack.
pop() : To delete an element from the stack.
peek() : To get the element that is inserted at last. Generally, we call it an element present at the top.

Algorithm

The algorithm works as follows:

A pointer called top is used to keep track of the top element in the stack.
When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing top == -1.
When pushing an element, we increase the value of top and place the new element at the position pointed by top.
When popping an element, we return the element pointed to by top and decrement its value.
Before push() operation, we check if the stack is already full.
Before pop() operation, we check if the stack is already empty.

Code

Java

Python

C++

import java.io.*;

class Stack {

    private int maxSize, top;
    private int stack[];

    public Stack(int maxSize) {
        this.top = -1;
	this.maxSize = maxSize;
	this.stack = new int[maxSize];
    }

    private boolean isEmpty() {
	if(top < 0) {
	    return true;
        }
	return false;
    }

    private boolean isFull() {
	if(top >= maxSize - 1) {
	    return true;
        }
	return false;
    }

   public void push(int key) {
		
	// isFull() will return true, if stack is full.
	if(isFull()) {
	    System.out.println("Stack Overflow");
	    return;
	}

	stack[++top] = key;
	System.out.println("The element is pushed and top points to => " + stack[top]);
    }

    public int pop() {
        
        // isEmpty() will return true, if stack is empty
        if(isEmpty()) {
            System.out.println("Stack Underflow");
    	    return -1;
    	}
    
    	// otherwise, delete the element from the top and decrement top.
    	int deletedElement = stack[top];
    	top--;
    	return deletedElement;
    }

    int peek() {
        if(isEmpty()) {
    	    System.out.println("Stack Underflow");
    	    return -1;
    	}
    
    	int peekElement = stack[top];
    	return peekElement;
    }

    public static void main(String[] args) {
	Stack stack = new Stack(100);
	stack.push(10); 
	stack.push(20); 
	stack.push(30); 
	System.out.println("Deleted element is: " + stack.pop());
	System.out.println("Top element is: " + stack.peek());
    }

}

class Stack:
	
    def __init__(self, max_size):
    	self.top = -1
    	self.max_size = max_size
    	self.stack = []
    
    def is_empty(self):
    	if(self.top < 0):
    	    return True
    	return False

    def is_full(self):
    	if(self.top >= self.max_size - 1):
    	    return True
    	return False

    def push(self, key):
		
	# is_full() will return true, if stack is full.
    	if(self.is_full()):
      	    print("Stack Overflow")
      	    return None
    			
        #  otherwise, increment top and add key to stack[top], here top works as an index only.
    	self.top += 1
    	self.stack.append(key)
    	print("The element is pushed and top points to => ", self.stack[self.top])
    
    def pop(self):
		
    	# is_empty() will return true, if stack is empty
    	if(self.is_empty()):
            print("Stack underflow")
            return -1
    
    	# otherwise, delete the element from the top and decrement top.
    	deletedElement = self.stack[self.top]
    	self.top -= 1
    	return deletedElement
    
    def peek(self):
    	if(self.is_empty()):
    	    print("Stack underflow")
    	    return -1
    
    	peekElement = self.stack[self.top];
    	return peekElement

if __name__ == '__main__':   
    stack = Stack(100)
    stack.push(10) 
    stack.push(20) 
    stack.push(30) 
    print("Deleted element is:", stack.pop())
    print("Top element is: ", stack.peek())

#include <bits/stdc++.h>
using namespace std;

class Stack {

private:

    int maxSize, top;
    int *stack;
    
    bool isEmpty() {
    	if(top < 0) {
    		return 1;
    	}
    	return 0;
    }
    
    bool isFull() {
    	if(top >= maxSize - 1) {
    		return 1;
    	}
    	return 0;
    }

public:
    
    Stack(int maxSize) {
        this->top = -1;
        this->maxSize = maxSize;
        this->stack = new int[maxSize];
    }
    
    void push(int key) {
    
    	// isFull() will return true, if stack is full.
    	if(isFull()) {
    		cout << "Stack Overflow" << endl;
    		return;
    	}
    
    	// otherwise, increment top and add key to stack[top], here top works as an index only.
    	stack[++top] = key;
    	cout << "The element is pushed and top points to => " <<  stack[top] << endl;
    }
    
    int pop() {
        
        // isEmpty() will return true, if stack is empty
        if(isEmpty()) {
    		cout << "Stack Underflow" << endl;
    		return -1;
    	}
    
    	// otherwise, delete the element from the top and decrement top.
    	int deletedElement = stack[top];
    	top--;
    	return deletedElement;
    }
    
    int peek() {
        if(isEmpty()) {
    		cout << "Stack Underflow" << endl;
    		return -1;
    	}
    
    	int peekElement = stack[top];
    	return peekElement;
    }
    
};

int main(int argc, char const *argv[]) {
    Stack stack(100);
    stack.push(10);
    stack.push(20);
    stack.push(30);
    cout << "Deleted element is: " << stack.pop() << endl;
    cout << "Top element is: " << stack.peek() << endl;
    return 0;
}

Output:

The element is pushed and top points to => 10
The element is pushed and top points to => 20
The element is pushed and top points to => 30
Deleted element is: 30
Top element is: 20

Time Complexity

Suppose you are given N number of elements to be inserted into the Stack, therefore you will call push() N number of times to push all the elements into the stack. Hence, the time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array.