##### What is a Stack?

A stack is an abstract data type that adheres to the Last-In-First-Out (LIFO) principle in the context of data structures and algorithms (DSA). It’s a linear data structure with operations like push (adding an element to the top) and pop (removing the topmost element).

**Note:** A stack can be visualized as a stack of plates where you can only access the topmost plate. The last plate you put on the stack is the first one to be removed.

##### Standard Stack Operations:

**The following are some common operations implemented on the stack:**

**push():**When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs.**pop():**When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.**isEmpty():**It determines whether the stack is empty or not.**isFull():**It determines whether the stack is full or not.’**peek():**It returns the element at the given position.**count():**It returns the total number of elements available in a stack.**change():**It changes the element at the given position.**display():**It prints all the elements available in the stack.

Operation | Time Complexity(N- no. o elements in the stack) | Space Complexity |
---|---|---|

push() | O(1) | O(1) |

pop() | O(1) | O(1) |

isEmpty() | O(1) | O(1) |

isFull() | O(1) | O(1) |

peek() | O(1) | O(1) |

count() | O(1) | O(1) |

change() | O(1) | O(1) |

display() | O(N) | O(N) |

##### Application of Stack:

Stacks are commonly used in various algorithms and programming tasks due to their simple and efficient structure. Some applications of stacks include:

**Expression evaluation:**Stacks can be used to evaluate arithmetic expressions, such as infix, postfix, or prefix notations.**Function call management:**Stacks are used to manage function calls and recursion in programming languages.**Undo operations:**Stacks can be used to implement undo functionality in applications.**Backtracking:**Stacks are useful for backtracking algorithms, such as depth-first search (DFS).**Browser history:**Stacks can be used to maintain the history of visited web pages in a browser.

##### Implementation of stack in DSA:

A stack can be implemented in two ways:

- Array implementation
- Linked list implementation

**Array Implementation:**

`push(int element)`

: This function adds an element to the top of the stack. It has a**time complexity of O(1)**since adding an element to an array at a specific index takes constant time.`pop()`

: This function removes and returns the topmost element from the stack. It also has a**time complexity of O(1)**since accessing and removing an element from a specific index in an array takes constant time.`isEmpty()`

: This function checks if the stack is empty. It has a**time complexity of O(1)**since it only requires checking the value of the`top`

variable, which is constant time.`isFull()`

: This function checks if the stack is full. It has a**time complexity of O(1)**since it only requires comparing the`top`

variable with the capacity, which is constant time.`peek()`

: This function returns the topmost element of the stack without removing it. It has a**time complexity of O(1)**as it directly accesses the element at the`top`

index of the array.`size()`

: This function returns the number of elements in the stack. It has a**time complexity of O(1)**as it simply returns the value of the`top`

variable, which represents the number of elements in the stack.`display()`

: This function displays all the elements in the stack. It has a**time complexity of O(N)**where N is the number of elements in the stack since it requires iterating over each element in the array and printing it.- The
**space complexity**for all the functions is O(1) as they use a fixed amount of additional space regardless of the input size.

```
public class Stack {
private int capacity;
private int top;
private int[] stackArray;
public Stack(int capacity) {
this.capacity = capacity;
this.top = -1;
this.stackArray = new int[capacity];
}
public void push(int element) {
if (top < capacity - 1) {
stackArray[++top] = element;
} else {
System.out.println("Stack Overflow");
}
}
public int pop() {
if (top >= 0) {
return stackArray[top--];
} else {
System.out.println("Stack Underflow");
return -1; // Or throw an exception
}
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == capacity - 1);
}
public int peek() {
if (top >= 0) {
return stackArray[top];
} else {
System.out.println("Stack is empty");
return -1; // Or throw an exception
}
}
public int size() {
return top + 1;
}
public void display() {
System.out.print("Stack: ");
for (int i = 0; i <= top; i++) {
System.out.print(stackArray[i] + " ");
}
System.out.println();
}
}
```

**Linked List Implementation:**

`push(int element)`

: This function adds an element to the top of the stack by creating a new node and updating the`top`

reference. It has a**time complexity of O(1)**since it involves creating a new node and updating a reference.`pop()`

: This function removes and returns the topmost element from the stack by updating the`top`

reference. It also has a**time complexity of O(1)**as it only involves updating a reference.`isEmpty()`

: This function checks if the stack is empty. It has a**time complexity of O(1)**as it only requires checking the value of the`top`

reference, which is constant time.`peek()`

: This function returns the topmost element of the stack without removing it. It has a**time complexity of O(1)**as it directly accesses the element referenced by the`top`

reference.`display()`

: This function displays all the elements in the stack by iterating over the linked list. It has a**time complexity of O(N)**where N is the number of elements in the stack since it requires visiting each node in the linked list.- The
**space complexity**for all the functions is O(1) as they use a fixed amount of additional space regardless of the input size.

```
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class Stack {
private Node top;
public Stack() {
this.top = null;
}
public void push(int element) {
Node newNode = new Node(element);
newNode.next = top;
top = newNode;
}
public int pop() {
if (top != null) {
int poppedValue = top.data;
top = top.next;
return poppedValue;
} else {
System.out.println("Stack Underflow");
return -1; // Or throw an exception
}
}
public boolean isEmpty() {
return (top == null);
}
public int peek() {
if (top != null) {
return top.data;
} else {
System.out.println("Stack is empty");
return -1; // Or throw an exception
}
}
public void display() {
System.out.print("Stack: ");
Node current = top;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
```

##### Array vs Linked list implementation of stack:

Array Implementation | Linked List Implementation | |
---|---|---|

Memory Allocation | Requires a fixed-size array | Dynamic allocation of nodes |

Insertion (Push) | Direct access at top index (O(1)) | Creation of new node and reference update (O(1)) |

Deletion (Pop) | Direct access at top index (O(1)) | Reference update and node deallocation (O(1)) |

Memory Efficiency | More memory efficient (no overhead) | Slightly less memory efficient (overhead of nodes and references) |

Resizing | Resizing the array can be expensive | No resizing required |

Advantages | – Constant-time access and updates – More memory efficient | – Dynamic size handling |

Disadvantages | – Limited capacity – Costly resizing if capacity is exceeded | – No predefined maximum capacity – Slightly less memory efficient |

##### Problems based on Stack:

**You are given N elements and your task is to Implement a Stack in which you can get a minimum element in O(1) time.**

**Example:**

Input:push(2) push(3) pop() getMin() push(1) getMin()Output:2 1Explanation:In the first test case for query push(2) Insert 2 into the stack. The stack will be {2} push(3) Insert 3 into the stack. The stack will be {2 3} pop() Remove top element from stack Poped element will be 3 the stack will be {2} getMin() Return the minimum element min element will be 2 push(1) Insert 1 into the stack. The stack will be {2 1} getMin() Return the minimum element min element will be 1

**Your Task:**

You are required to complete the three methods **push()** which takes one argument an integer **‘x’** to be pushed into the stack, **pop()** which returns an integer popped out from the stack, and **getMin()** which returns the min element from the stack. (-1 will be returned if for **pop() and getMin() **the stack is empty.)

**Expected Time Complexity**: O(1) for all the 3 methods.**Expected Auxiliary Space**: O(1) for all the 3 methods.

**Solution:**

```
import java.util.Stack;
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
}
public int pop() {
if (stack.isEmpty()) {
return -1;
}
int popped = stack.pop();
if (popped == minStack.peek()) {
minStack.pop();
}
return popped;
}
public int getMin() {
if (minStack.isEmpty()) {
return -1;
}
return minStack.peek();
}
}
```

Explanation:

- The
`MinStack`

class has two stacks:`stack`

to store the actual elements`minStack`

to store the minimum values.

- When pushing an element, we first push it onto the
`stack`

. Then, if the`minStack`

is empty or the new element is less than or equal to the top element of`minStack`

, we push the new element onto`minStack`

as well. - When popping an element, we first check if the
`stack`

is empty. If it is, we return -1 indicating an empty stack. Otherwise, we pop the element from the`stack`

and check if it is the same as the top element of`minStack`

. If it is, we also pop the top element from`minStack`

. - When getting the minimum element, we simply return the top element of
`minStack`

. If`minStack`

is empty, we return -1 indicating an empty stack.

**Given an expression string x. Examine whether the pairs and the orders of {,},(,),[,] are correct in exp.For example, the function should return ‘true’ for exp = [()]{}{[()()]()} and ‘false’ for exp = [(]).**

**Note: **The drive code prints “balanced” if function return true, otherwise it prints “not balanced”.

**Example:**

Input: {([])}Output: trueExplanation: { ( [ ] ) }. Same colored brackets can form balanced pairs, with 0 number of unbalanced bracket.

**Expected Time Complexity**: O(|x|)**Expected Auixilliary Space**: O(|x|)

**Solution:**

```
Stack<Character> stack = new Stack<>();
for (char c : exp.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
```

Explanation:

- The
`ispar`

function takes a string`exp`

as input and returns a boolean value indicating whether the brackets are balanced or not. - We iterate through each character in the input string using a for-each loop.
- If we encounter an opening bracket (
`(`

,`[`

, or`{`

), we push it onto the stack. - If we encounter a closing bracket (
`)`

,`]`

, or`}`

), we check if the stack is empty. If it is, there is no corresponding opening bracket, so the brackets are not balanced, and we return false. - If the stack is not empty, we pop the top element from the stack and compare it with the current closing bracket. If they do not form a matching pair (e.g.,
`( )`

,`[ ]`

,`{ }`

), we return false. - If the stack is empty after iterating through all the letters, it signifies that all the brackets have been matched and balanced, and we return true. If there are still unmatched opening brackets in the stack, we return false.

**Given a binary tree, find its preorder traversal.**

**Example 1:**

Input:1 / 4 / \ 4 2Output:1 4 4 2

**Example 2:**

Input:6 / \ 3 2 \ / 1 2Output:6 3 1 2 2

**Your Task:**

You just have to complete the function **preorder() **which takes the root node of the tree as input and returns an array containing the preorder traversal of the tree.

**Expected Time Complexity: **O(N).**Expected Auxiliary Space: **O(N).

**Solution:**

```
// class Node{
// int data;
// Node left,right;
// Node(int d){
// data=d;
// left=right=null;
// }
// }
class BinaryTree
{
//Function to return a list containing the preorder traversal of the tree.
static ArrayList<Integer> preorder(Node root)
{ ArrayList<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
result.add(node.data);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
// Code here
}
}
```

Explanation:

- The
`BinaryTree`

class represents a binary tree. - The
`preorder`

function takes the root node of the binary tree as input and returns an`ArrayList<Integer>`

containing the preorder traversal of the tree. - We start by creating an empty
`ArrayList<Integer>`

called`result`

to store the preorder traversal elements. - If the root node is null, we simply return the empty
`result`

list. - We use a stack to keep track of the nodes during the traversal. We initialize the stack with the root node.
- While the stack is not empty, we perform the following steps:
- Pop a node from the stack and add its data value to the
`result`

list. - Push the right child of the node onto the stack (if it exists) before the left child (to ensure preorder traversal).

- Pop a node from the stack and add its data value to the
- After traversing all the nodes, we return the
`result`

list containing the preorder traversal elements.

**Given a stack, the task is to sort it such that the top of the stack has the greatest element.**

**Example:**

Input:Stack: 11 2 32 3 41Output:41 32 11 3 2

**Your Task: **

You don’t have to read input or print anything. Your task is to complete the function **sort() **which sorts the elements present in the given stack. (The sorted stack is printed by the driver’s code by popping the elements of the stack.)

**Expected Time Complexity**: O(N*N)**Expected Auxilliary Space**: O(N) recursive.

**Solution:**

```
import java.util.Stack;
class SortStack {
public static void sort(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
int temp = stack.pop();
sort(stack);
insertSorted(stack, temp);
}
private static void insertSorted(Stack<Integer> stack, int element) {
if (stack.isEmpty() || element > stack.peek()) {
stack.push(element);
} else {
int temp = stack.pop();
insertSorted(stack, element);
stack.push(temp);
}
}
}
```

Explanation:

- The
`sort`

function takes a stack of integers as input and sorts its elements in descending order. - If the stack is empty, we simply return as there are no elements to sort.
- We recursively sort the stack by performing the following steps:
- Pop an element from the stack and store it in the variable
`temp`

. - Recursively sort the remaining elements of the stack.
- Insert the
`temp`

element back into the stack in the correct position using the`insertSorted`

helper function.

- Pop an element from the stack and store it in the variable
- The
`insertSorted`

function is a recursive helper function that inserts an element into the stack at the correct position. - If the stack is empty or the element is greater than the top element of the stack, we push the element onto the stack.
- Otherwise, we recursively call
`insertSorted`

with the remaining stack elements until we find the correct position to insert the element. - The
**time complexity of this approach is O(N^2)**, where N is the number of elements in the stack. This is because, in the worst case, each element needs to be inserted at its correct position by comparing it with the elements already in the stack. - The auxiliary
**space complexity is O(N)**as the recursive calls consume space on the function call stack.

*Note: also read about* Pointers in DSA

**Follow Me**

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py

Staying up to the mark is what defines me. Hi all! I’m Rabecca Fatima a keen learner, great enthusiast, ready to take new challenges as stepping stones towards flying colors.