In this chapter, we will learn how to design our own stack using array.
In this chapter, we will learn how to design our own stack using array.
Design stack data structure using an array. Implement push()
, pop()
, and peek()
operation in constant time.
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:
push()
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.
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.
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.The algorithm works as follows:
top
is used to keep track of the top element in the stack.top == -1
.top
and place the new element at the position pointed by top
.top
and decrement its value.push()
operation, we check if the stack is already full.pop()
operation, we check if the stack is already empty.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
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.
The above algorithm’s space complexity will also be O(N)
this space will be used for creating stack[]
array to store elements.
© 2022 - All Rights Reserved.