### Stack CRUD Array

# Stack CRUD Array

## Introduction to Stack CRUD Array

In computer science, a stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The CRUD array is a common implementation of a stack that supports four main operations: Create, Read, Update, and Delete.

The Create operation adds a new element to the top of the stack. The Read operation retrieves the element at the top of the stack without modifying the stack. The Update operation modifies the element at the top of the stack. The Delete operation removes the element at the top of the stack.

Using a stack CRUD array allows for efficient management of data, as elements can be easily added or removed from the top of the stack. This makes it a useful data structure in various applications, such as expression evaluation, backtracking algorithms, and browser history management.

## Overview of Stack CRUD Array

A stack CRUD array is a data structure that follows the Last-In-First-Out (LIFO) principle. It supports four main operations: Create, Read, Update, and Delete.

- Create: Adds a new element to the top of the stack.
- Read: Retrieves the element at the top of the stack without modifying the stack.
- Update: Modifies the element at the top of the stack.
- Delete: Removes the element at the top of the stack.

By using a stack CRUD array, data can be efficiently managed by easily adding or removing elements from the top of the stack. This makes it a valuable data structure in various applications, including expression evaluation, backtracking algorithms, and browser history management.

## CODE:

#### Python

```
/* Copyrights to venkys.io
For more information, visit https://venkys.io */
# Python program for performing Stack CRUD Array operations
# Stable: No
# Inplace: yes
# Adaptive: No
# Space complexity: O(n)
# Time complexity: O(1)
class STACK:
def __init__(self, size):
self.stack = []
self.top = -1
self.size = size - 1
# push operation on stack
def push(self, val):
self.top += 1
if self.top <= self.size:
self.stack.append(val)
else:
print("STACK AS OVER-FLOWN")
# pop operation on stack
def pop(self):
if self.top >= 0:
self.stack.pop(self.top)
self.top -= 1
else:
print("STACK AS UNDER-FLOWN")
# isunderflown function on stack
def is_underflown(self):
if self.top == -1:
print("THE STACK IS UNDER-FLOWN")
else:
print("THE STACK IS NOT UNDER-FLOWN")
# isoverflown function on stack
def is_overflown(self):
if self.top > self.size:
print("THE STACK IS OVER-FLOWN")
else:
print("THE STACK IS NOT OVER-FLOWN")
# display function on stack
def display(self):
if self.top == -1:
print("|| EMPTY ||")
else:
for i in range(self.top + 1):
print(f"|| {self.stack[i]} ||")
# Top function on stack
def display_top(self):
if self.top == -1:
print("THE STACK IS EMPTY")
else:
print("THE TOP MOST ELEMENT IN STACK IS:", self.stack[self.top])
# Test drive code:
size = int(input("Enter the size of the stack: "))
stack = STACK(size)
print("------IS UNDER-FLOWN OPERATION ON STACK---------")
stack.is_underflown()
stack.display()
print()
print("------------PUSH OPERATION ON STACK-------------")
for _ in range(size):
element = int(input("Enter element to push onto the stack: "))
stack.push(element)
print("Stack status after push operation:")
stack.display()
print()
print("----------DISPLAY OPERATION ON STACK-----------")
stack.display()
print()
print("------------POP OPERATION ON STACK-------------")
for _ in range(size):
stack.pop()
print("Stack status after pop operation:")
stack.display()
print()
print("------IS OVER-FLOWN OPERATION ON STACK---------")
stack.is_overflown()
stack.display()
print()
print("---------TOP OPERATION ON STACK----------")
stack.display_top()
stack.display()
```

## Test Cases

### Test Case 1(Empty Stack):

#### sample input:

- size=5

#### sample output:

- #Test is_underflown on an empty stack

- Expected Output: THE STACK IS UNDER-FLOWN

- #Test is_overflown on an empty stack

- Expected Output: THE STACK IS NOT OVER-FLOWN

### Test Case 2(Non-Empty stack):

#### sample input:

- size=3
- push 10
- push 20
- push 30

#### sample output(pop from an empty stack):

- #Test is_underflown on a non-empty stack

- Expected Output: THE STACK IS UNDER-FLOWN

- #Test is_overflown on an empty stack

- Expected Output: THE STACK IS NOT OVER-FLOWN

### Test Case 3:

#### sample input:

- size=4

#### sample output:

- #Test pop on an empty stack

- Expected Output: STACK AS UNDER-FLOWN

- #Test is_overflown on an empty stack

- Expected Output: THE STACK IS NOT OVER-FLOWN

### Explanation of Testcases:

- In the first case, the stack is initialized but not populated with any elements. Both is_underflown and is_overflown should indicate that the stack is underflown (empty) and not overflown.
- In the second case, elements are pushed onto the stack, making it non-empty. Both is_underflown and is_overflown should indicate that the stack is not underflown and not overflown.
- In the third case, an attempt is made to pop from an empty stack. The pop method should indicate that the stack is underflown, and is_overflown should indicate that the stack is not overflown.

**Step-by-Step Explaination**

The code provided implements a stack class in Python. Let's break down the code structure:

- The
**STACK**class is defined with an**init**method that initializes the stack, top pointer, and size. - The
**push**method adds an element to the stack if it is not full. - The
**pop**method removes the top element from the stack if it is not empty. - The
**is_underflown**method checks if the stack is underflown (empty). - The
**is_overflown**method checks if the stack is overflown (full). - The
**display**method shows all the elements in the stack. - The
**display_top**method returns the topmost element in the stack. - Finally, a test drive code is provided to demonstrate the usage of the stack class.

## CODE:

#### Java

```
/* Copyrights to venkys.io
For more information, visit https://venkys.io */
// Python program for performing Stack CRUD Array operations
// Stable: No
// Inplace: yes
// Adaptive: No
// Space complexity: O(n)
// Time complexity: O(1)
import java.util.Scanner;
class Stack {
int top = -1;
int size;
int[] arr;
Stack(int size) {
this.size = size;
arr = new int[size];
}
// push operation on stack
void push(int data) {
if (top == -1) {
arr[0] = data;
top = 0;
return;
}
if (top > -1 && top < size) {
arr[++top] = data;
return;
}
System.out.println("Stack Overflow");
return;
}
// pop operation on stack
void pop() {
if (top == -1) {
System.out.println("Empty Stack");
return;
}
arr[top--] = 0;
}
// peek operation on stack
void peek() {
if (top == -1)
return;
System.out.println(arr[top]);
return;
}
void print() {
for (int i = 0; i <= top; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Size of stack
System.out.print("Enter the size of the stack: ");
int size = scanner.nextInt();
Stack s = new Stack(size);
// no.of elements to push in stack
System.out.print("Enter the number of elements to push onto the stack: ");
int numElements = scanner.nextInt();
// enter elements to be pushed into stack
for (int i = 0; i < numElements; i++) {
System.out.print("Enter element to push onto the stack: ");
int element = scanner.nextInt();
s.push(element);
}
// Printing top element of stack
System.out.print("Top element of the stack: ");
s.peek();
// printing elments of present stack
System.out.println("Elements in the stack: ");
s.print();
// no.of elements to pop in stack
System.out.print("Enter the number of elements to pop from the stack: ");
int numPop = scanner.nextInt();
for (int i = 0; i < numPop; i++) {
s.pop();
}
// enter elements to be pushed into stack
System.out.print("Enter the number of elements to push onto the stack: ");
numElements = scanner.nextInt();
for (int i = 0; i < numElements; i++) {
System.out.print("Enter element to push onto the stack: ");
int element = scanner.nextInt();
s.push(element);
}
// printing elements of stack after operations
System.out.println("Elements in the stack: ");
s.print();
}
}
```

**step by step explaination**

- The code defines a class named
**Stack**which represents a stack data structure implementation. It has instance variables**top**,**size**, and an integer array**arr**to store the stack elements. - The constructor
**Stack(int size)**initializes the stack size and creates a new integer array of the specified size. - The
**push(int data)**method adds an element to the stack. If the stack is empty, it assigns the element to the first index and updates the**top**variable. If the stack is not empty and there is space available, it increments**top**and adds the element to the next index. If the stack is full, it prints "Stack Overflow". - The
**pop()**method removes the top element from the stack. If the stack is empty, it prints "Empty Stack". It assigns 0 to the top element to remove it. - The
**peek()**method returns the top element of the stack without removing it. If the stack is empty, it does nothing. - The
**print()**method prints all the elements in the stack from top to bottom. - In the
**Main**class, an instance of**Stack**is created with a size of 5. - The
**push()**method is called to add elements 10 and 20 to the stack. - The
**peek()**method is called to print the top element, which is 20. - The
**print()**method is called to print all the elements in the stack, which are 10 and 20. - The
**pop()**method is called twice to remove the elements 20 and 10 from the stack. - The
**push()**method is called three times to add elements 1, 2, and 3 to the stack. - The
**print()**method is called to print all the elements in the stack, which are 1, 2, and 3.

This code demonstrates the basic operations of a stack data structure implemented using an array in Java.

## CODE:

#### CPP

```
/* Copyrights to venkys.io
For more information, visit https://venkys.io */
// Python program for performing Stack CRUD Array operations
// Stable: No
// Inplace: yes
// Adaptive: No
// Space complexity: O(n)
// Time complexity: O(1)
#include <iostream>
using namespace std;
class Stack {
private:
int *arr;
int top = -1;
int max;
public:
Stack(int size) {
arr = new int[size];
max = size;
}
// push operation on stack
void push(int data) {
if (top == -1) {
arr[0] = data;
top = 0;
return;
}
if (top > -1 && top < max) {
arr[++top] = data;
return;
}
cout << "Stack overflow" << endl;
return;
}
// pop operation on stack
void pop() {
if (top == -1) {
cout << "Empty Stack" << endl;
return;
}
arr[top--] = 0;
}
// peek operation on stack
void peek() {
if (top == -1)
return;
cout << arr[top] << endl;
return;
}
void print() {
for (int i = 0; i <= top; i++) {
cout << arr[i] << " ";
}
cout << endl;
return;
}
};
int main() {
int size;
cout << "Enter the size of the stack: ";
cin >> size;
Stack s(size);
// no.of elements to push in stack
int numElements;
cout << "Enter the number of elements to push onto the stack: ";
cin >> numElements;
// enter elements to be pushed into stack
for (int i = 0; i < numElements; i++) {
int element;
cout << "Enter element to push onto the stack: ";
cin >> element;
s.push(element);
}
cout << "Top element of the stack: ";
s.peek();
cout << "Elements in the stack: ";
s.print();
// no.of elements to pop from stack
int numPop;
cout << "Enter the number of elements to pop from the stack: ";
cin >> numPop;
for (int i = 0; i < numPop; i++) {
s.pop();
}
// no.of elements to push onto stack
cout << "Enter the number of elements to push onto the stack: ";
cin >> numElements;
// elements to be pushed onto stack
for (int i = 0; i < numElements; i++) {
int element;
cout << "Enter element to push onto the stack: ";
cin >> element;
s.push(element);
}
// Printing Elements of stack
cout << "Elements in the stack: ";
s.print();
return 0;
}
```

**step by step explaination**

Here is a step-by-step explanation of the code:

- The code begins by including the necessary header files and declaring the namespace.
- The
**Stack**class is defined, which will implement the stack functionality. - The private members of the
**Stack**class are declared:**arr**(to store the elements of the stack),**top**(to keep track of the top element), and**max**(to store the maximum capacity of the stack). - The constructor of the
**Stack**class is defined, which takes the size of the stack as a parameter. It dynamically allocates memory for the stack array and initializes the**top**and**max**variables. - The
**push()**function is defined to insert an element into the stack. It checks if the stack is empty and inserts the element at the first index. If the stack is not empty and has space, it increments the**top**variable and inserts the element at the corresponding index. If the stack is full, it displays a "Stack overflow" message. - The
**pop()**function is defined to remove the top element from the stack. It checks if the stack is empty and displays an "Empty Stack" message. Otherwise, it sets the top element to 0, effectively removing it from the stack. - The
**peek()**function is defined to display the top element of the stack. If the stack is empty, it does nothing. Otherwise, it prints the value of the top element. - The
**print()**function is defined to display all the elements of the stack. It iterates through the stack array and prints each element. - The
**main()**function is implemented. It creates an instance of the**Stack**class with a size of 5. - Elements are pushed onto the stack using the
**push()**function. - The
**peek()**function is called to display the top element of the stack. - The
**print()**function is called to display all the elements of the stack. - Elements are popped from the stack using the
**pop()**function. - More elements are pushed onto the stack.
- The
**print()**function is called again to display the updated elements of the stack.

Finally, the program ends with a return statement.

## Time and Space Complexity Analysis

The time and space complexity of the stack CRUD array implementation can be analyzed as follows:

**Time Complexity:**- Create (Push) Operation: The time complexity of adding an element to the top of the stack is O(1) since it only involves inserting the element at the top position.
- Read (Top) Operation: The time complexity of retrieving the element at the top of the stack is O(1) as it directly accesses the top element.
- Update Operation: The time complexity of modifying the element at the top of the stack is O(1) since it only involves updating the value at the top position.
- Delete (Pop) Operation: The time complexity of removing the element at the top of the stack is O(1) as it removes the top element in constant time.
- Overall, all the stack CRUD operations have a time complexity of O(1) since they involve constant time operations.

**Space Complexity:**- The space complexity of the stack CRUD array is O(n), where n is the maximum size of the stack. This is because the stack uses an array to store its elements, and the space required is proportional to the maximum size of the stack.

It's important to note that the space complexity can vary depending on the implementation and specific requirements of the stack.

## Real-World Applications of Stack CRUD Array

The stack CRUD array data structure has various real-world applications due to its efficient management of data. Some of these applications include:

**Expression Evaluation**: Stacks are commonly used to evaluate arithmetic expressions. They can be used to convert infix expressions to postfix or prefix notation and then evaluate them. The LIFO property of stacks allows for easy evaluation of operators and operands.**Backtracking Algorithms**: Backtracking algorithms, such as maze solving or graph traversal, often use stacks to keep track of the path or states. If a certain path or state is not feasible, it can be easily removed from the stack, allowing the algorithm to explore alternative options.**Browser History Management**: Web browsers often use stacks to manage browsing history. Each visited webpage is added to the stack, and when the user clicks the "back" button, the most recent page is popped from the stack, allowing navigation back to the previous page.

These are just a few examples of how the stack CRUD array data structure can be applied in real-world scenarios. Its simplicity and efficiency make it a valuable tool for managing data and solving various computational problems.