# Implement Stack Using Array

In this chapter, we will learn how to design our own stack using array.

#### 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:

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

#### Code

``````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.

#### Space Complexity

The above algorithm’s space complexity will also be `O(N)` this space will be used for creating `stack[]` array to store elements.

#### Innoskrit

We're building a next-level EdTech Startup.