Stack Flashcards
Array Implementation of Stack in C++
#include (bits/stdc++.h> using namespace std;
struct MyStack{
int *arr;
int cap;
int top;
MyStack(int c){
cap=c;
arr=new int [cap];
top=-1;
}
void push(int x){
if(top==cap-1){cout(("Stack is full"((endl;return;}
top++;
arr[top]=x;
}
int pop(){
if(top==-1){cout(("Stack is Empty"((endl;return INT_MIN;}
int res=arr[top];
top--;
return res;
}
int peek(){
if(top==-1){cout(("Stack is Empty"((endl;return INT_MIN;}
return arr[top];
}
int size(){
return (top+1);
}
bool isEmpty(){
return top==-1;
}
};
int main()
{
MyStack s(5);
s.push(5);
s.push(10);
s.push(20);
cout((s.pop()((endl;
cout((s.size()((endl;
cout((s.peek()((endl;
cout((s.isEmpty()((endl;
return 0; } 20 2 10 0
List implementation of stack
import java.util.ArrayList;
public class Stack<T> {
private ArrayList<T> list;
public Stack() {
list = new ArrayList<>();
}
// Push operation to add element to the top of stack
public void push(T item) {
list.add(item);
}
// Pop operation to remove and return the top element
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return list.remove(list.size() - 1);
}
// Peek operation to view the top element without removing it
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return list.get(list.size() - 1);
}
// Check if stack is empty
public boolean isEmpty() {
return list.isEmpty();
}
// Get the current size of stack
public int size() {
return list.size();
}
}
This implementation is simpler than the linked list version since it uses ArrayList’s built-in methods. It includes:
1. A generic type T so the stack can hold any data type
2. An ArrayList as the underlying data structure
3. The same basic stack operations:
- push(): Adds an element to the top
- pop(): Removes and returns the top element
- peek(): Views the top element without removing it
- isEmpty(): Checks if stack is empty
- size(): Returns the number of elements
Example usage:
Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.pop()); // Outputs: 3 System.out.println(stack.peek()); // Outputs: 2 System.out.println(stack.size()); // Outputs: 2
The ArrayList implementation has some advantages:
- Simpler code
- Better memory locality for faster access
- Dynamic resizing is handled automatically
Linked List Implementation of Stack in java
I’ll provide a comprehensive explanation of implementing a stack using a linked list in Java. We’ll break this down step by step to help you understand both the concept and the implementation.
/**
* A Stack implementation using a singly linked list data structure.
* This implementation demonstrates how to create a stack with basic
* operations like push, pop, peek, and isEmpty.
*/
public class LinkedListStack<T> {
// Inner class to represent a node in the linked list
private class Node {
T data; // The value stored in the node
Node next; // Reference to the next node in the stack
// Constructor to create a new node
Node(T data) {
this.data = data;
this.next = null;
}
}
// Top of the stack - the most recently added element
private Node top;
// Tracks the number of elements in the stack
private int size;
// Constructor to initialize an empty stack
public LinkedListStack() {
top = null;
size = 0;
}
/**
* Adds an element to the top of the stack.
* Time Complexity: O(1)
*
* @param item The element to be pushed onto the stack
*/
public void push(T item) {
// Create a new node with the given item
Node newNode = new Node(item);
// Set the new node's next to the current top
newNode.next = top;
// Update top to be the new node
top = newNode;
// Increment size
size++;
}
/**
* Removes and returns the top element from the stack.
* Time Complexity: O(1)
*
* @return The top element of the stack
* @throws IllegalStateException if the stack is empty
*/
public T pop() {
// Check if stack is empty
if (isEmpty()) {
throw new IllegalStateException("Cannot pop from an empty stack");
}
// Store the data to return
T data = top.data;
// Move top to the next node
top = top.next;
// Decrement size
size--;
return data;
}
/**
* Returns the top element without removing it.
* Time Complexity: O(1)
*
* @return The top element of the stack
* @throws IllegalStateException if the stack is empty
*/
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Cannot peek an empty stack");
}
return top.data;
}
/**
* Checks if the stack is empty.
* Time Complexity: O(1)
*
* @return true if the stack is empty, false otherwise
*/
public boolean isEmpty() {
return top == null;
}
/**
* Returns the number of elements in the stack.
* Time Complexity: O(1)
*
* @return The number of elements in the stack
*/
public int size() {
return size;
}
// Example usage method to demonstrate stack operations
public static void main(String[] args) {
LinkedListStack<Integer> stack = new LinkedListStack<>();
// Pushing elements
stack.push(10);
stack.push(20);
stack.push(30);
// Printing stack details
System.out.println("Stack size: " + stack.size()); // Should print 3
System.out.println("Top element: " + stack.peek()); // Should print 30
// Popping elements
System.out.println("Popped: " + stack.pop()); // Should print 30
System.out.println("Stack size: " + stack.size()); // Should print 2
}
}
Let me break down the key concepts of this linked list stack implementation:
-
Stack Concept
A stack is a Last-In-First-Out (LIFO) data structure where elements are added and removed from the same end, called the top of the stack. Think of it like a stack of plates where you can only add or remove from the top. -
Linked List Approach
Instead of using an array, we’re using a linked list where each node points to the next node. This allows for dynamic sizing without the need to resize an underlying array. -
Key Operations
-
push(T item): Adds an element to the top of the stack -
pop(): Removes and returns the top element -
peek(): Returns the top element without removing it -
isEmpty(): Checks if the stack is empty -
size(): Returns the number of elements in the stack
-
-
Time Complexity
All operations are O(1) - constant time, which is one of the advantages of using a linked list for a stack. -
Implementation Details
- We use a generic type
<T>to make the stack work with any data type - An inner
Nodeclass represents each element in the stack -
topalways points to the most recently added element -
sizetracks the number of elements for quick size checking
- We use a generic type
Why Use a Linked List for a Stack?
- Dynamic sizing: No need to worry about capacity
- Efficient operations: All stack operations are O(1)
- Memory efficiency: Only allocates memory as needed
Potential Improvements
In a real-world scenario, you might want to add:
- A constructor that takes an initial collection
- Methods to clear the stack
- Iteration support
- Enhanced error handling
Applications of stack:
I’ll explain five key applications of the stack data structure, providing context and depth to help you understand how versatile and powerful stacks can be.
-
Function Call Management (Call Stack)
In programming languages, the call stack is perhaps the most fundamental application of a stack data structure. When a function is called, its local variables, return address, and other execution context are pushed onto the call stack. When the function completes, these details are popped off the stack. This mechanism enables recursive function calls and helps manage program execution flow. Think of it like a stack of plates, where each function call is a plate added to the top, and when a function finishes, its plate is removed. -
Expression Evaluation and Syntax Parsing
Stacks play a crucial role in evaluating mathematical expressions and parsing syntax. Compilers and calculators use stacks to:- Convert infix expressions (like 3 + 4) to postfix notation
- Validate balanced parentheses in programming languages
- Evaluate complex arithmetic expressions
The stack allows these systems to track open brackets, operators, and operands efficiently, processing them in the correct order.
-
Undo Mechanisms in Software
Many software applications use stacks to implement undo functionality. Each action a user takes is pushed onto a stack. When the user wants to undo an action, the most recent action is popped off the stack and reversed. This is used in:- Text editors
- Graphic design software
- Database transaction management
The stack ensures that actions can be undone in the exact reverse order they were performed, maintaining a logical and intuitive user experience.
-
Depth-First Search (DFS) in Graphs and Trees
In graph and tree traversal algorithms, stacks are essential for implementing depth-first search. When exploring a graph or tree, the stack helps track:- Which nodes have been visited
- Which nodes are yet to be explored
- The path of exploration
By pushing and popping nodes from the stack, the algorithm can systematically explore all branches of a graph or tree, making it useful in pathfinding, network analysis, and solving puzzles like mazes.
-
Browser History Navigation
Web browsers use two stacks to manage forward and backward navigation:- A “back” stack stores previously visited pages
- A “forward” stack stores pages you’ve moved away from but can return to
When you click the back button, the current page is pushed to the forward stack, and the previous page is popped from the back stack. This allows intuitive web browsing and maintains a history of your navigation.
Each of these applications demonstrates how a simple last-in, first-out (LIFO) data structure can solve complex computational problems. Stacks provide an elegant way to manage information that needs to be processed in a specific order, making them a fundamental tool in computer science and software engineering.
Sort a stack using a temporary stack
Given a stack of integers, sort it in ascending order using another temporary stack.
Examples:
Input : [34, 3, 31, 98, 92, 23]
Output : [3, 23, 31, 34, 92, 98]
Input : [3, 5, 1, 4, 2, 8]
Output : [1, 2, 3, 4, 5, 8]
I’ll help you solve this problem of sorting a stack using a temporary stack. I’ll break down the solution step by step and explain the approach thoroughly.
import java.util.Stack;
public class StackSorter {
/**
* Sorts a stack in ascending order using a temporary stack.
*
* Time Complexity: O(n^2)
* Space Complexity: O(n)
*
* @param inputStack The original stack to be sorted
* @return Sorted stack in ascending order
*/
public static Stack<Integer> sortStack(Stack<Integer> inputStack) {
// If the input stack is empty or has only one element, return it
if (inputStack == null || inputStack.size() <= 1) {
return inputStack;
}
// Create a temporary stack to help with sorting
Stack<Integer> tempStack = new Stack<>();
// Continue until the input stack is empty
while (!inputStack.isEmpty()) {
// Remove the top element from the input stack
int current = inputStack.pop();
// While the temporary stack is not empty and its top element is larger than current
while (!tempStack.isEmpty() && tempStack.peek() > current) {
// Move elements back to the input stack
inputStack.push(tempStack.pop());
}
// Place the current element in the correct position in the temporary stack
tempStack.push(current);
}
// At this point, tempStack is sorted in ascending order
// Transfer elements back to the input stack to restore the original stack reference
while (!tempStack.isEmpty()) {
inputStack.push(tempStack.pop());
}
return inputStack;
}
// Example usage and demonstration
public static void main(String[] args) {
// Create an unsorted stack
Stack<Integer> unsortedStack = new Stack<>();
unsortedStack.push(34);
unsortedStack.push(3);
unsortedStack.push(31);
unsortedStack.push(98);
unsortedStack.push(92);
unsortedStack.push(23);
System.out.println("Original Stack: " + unsortedStack);
// Sort the stack
Stack<Integer> sortedStack = sortStack(unsortedStack);
System.out.println("Sorted Stack: " + sortedStack);
}
}
Let me walk you through the sorting algorithm and its key concepts:
Algorithm Explanation
The sorting algorithm works by using a clever approach with two stacks:
1. The input stack contains the original unsorted elements
2. A temporary stack is used to help sort the elements
Sorting Process
1. Take the top element from the input stack
2. Compare it with elements in the temporary stack
3. If the current element is smaller, move larger elements from the temporary stack back to the input stack
4. Insert the current element in the correct position in the temporary stack
Time and Space Complexity
- Time Complexity: O(n²), where n is the number of elements in the stack
- Space Complexity: O(n), as we’re using an additional stack
Key Insights
- This approach is similar to insertion sort but adapted for stack data structure
- We maintain the sorted order in the temporary stack
- The final sorted stack is obtained by transferring elements from the temporary stack back to the input stack
Comparison with Other Sorting Methods
Unlike array sorting, stack sorting is more challenging because:
- You can only access the top element
- You can’t randomly access or index elements
- Operations are limited to push and pop
Practical Considerations
- Works well for small to medium-sized stacks
- Not the most efficient for very large datasets
- Preserves the original stack reference, which can be useful in some scenarios
Get minimum element from stack
You are given N elements and your task is to Implement a Stack in which you can get minimum element in O(1) time.
Example 1:
Input:
push(2)
push(3)
pop()
getMin()
push(1)
getMin()
Output: 3 2 1
Explanation: In the first test case for
query
push(2) the stack will be {2}
push(3) the stack will be {2 3}
pop() poped element will be 3 the
stack will be {2}
getMin() min element will be 2
push(1) the stack will be {2 1}
getMin() min element will be 1
Your Task:
You are required to complete the three methods push() which take one argument an integer 'x' to be pushed into the stack, pop() which returns a integer poped 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 Auixilliary Space : O(1) for all the 3 methods.
#include (bits/stdc++.h> using namespace std;
The structure of the class is as follows
class _stack{
stack(int> s;
int minEle;
public :
int getMin();
int pop();
void push(int);
};
class Solution{
int minEle;
stack(int> s;
public:
/*returns min element from stack*/
int getMin(){
if(s.size() == 0) return -1;
return minEle;
}
/*returns poped element from stack*/
int pop(){
int val;
if(s.size() == 0) return -1;
else {
if(s.top() >= minEle) {
val = s.top();
s.pop(); // if we unconter val that is smaller than min so pop(equal when duplicate present )
}
else if(s.top() ( minEle) {
val = minEle;
minEle = 2 * minEle - s.top(); // retrieve prev min value
s.pop();
}
}
return val;
}
/*push element x into the stack*/
void push(int x){
if(s.size() == 0) {
s.push(x);
minEle = x; //itself is the minele (only one element in stack)
}
else {
// stack have elements
if(x >= minEle) // if uncomping element is smaller so we push it in stack
s.push(x);
else if(x ( minEle) // it's time to update min
{
s.push(2*x - minEle);
// it's flag to indicate us min and help us to retireve prev min
minEle= x;
}
}
}
};
// { Driver Code Starts.
int main()
{
long long t;
cin>>t;
while(t--)
{
int q;
cin>>q;
Solution ob;
while(q--){
int qt;
cin>>qt;
if(qt==1)
{
//push
int att;
cin>>att;
ob.push(att);
}
else if(qt==2)
{
//pop
cout((ob.pop()((" ";
}
else if(qt==3)
{
//getMin
cout((ob.getMin()((" ";
}
}
cout((endl;
}
return 0;
}
// } Driver Code Ends
Check if stack elements are pairwise consecutive
Given a stack of integers, write a function pairWiseConsecutive() that checks whether numbers in the stack are pairwise consecutive or not. The pairs can be increasing or decreasing, and if the stack has an odd number of elements, the element at the top is left out of a pair. The function should retain the original stack content.
Only following standard operations are allowed on stack.
push(X): Enter a element X on top of stack.
pop(): Removes top element of the stack.
empty(): To check if stack is empty.
Examples:
Input : stack = [4, 5, -2, -3, 11, 10, 5, 6, 20]
Output : Yes
Each of the pairs (4, 5), (-2, -3), (11, 10) and
(5, 6) consists of consecutive numbers.
Input : stack = [4, 6, 6, 7, 4, 3]
Output : No
(4, 6) are not consecutive.
The idea is to use another stack.
Create an auxiliary stack aux.
Transfer contents of given stack to aux.
Traverse aux. While traversing fetch top two elements and check if they are consecutive or not. After checking put these elements back to original stack.
// C++ program to check if successive // pair of numbers in the stack are // consecutive or not #include (bits/stdc++.h> using namespace std;
// Function to check if elements are
// pairwise consecutive in stack
bool pairWiseConsecutive(stack(int> s)
{
// Transfer elements of s to aux.
stack(int> aux;
while (!s.empty()) {
aux.push(s.top());
s.pop();
}
// Traverse aux and see if
// elements are pairwise
// consecutive or not. We also
// need to make sure that original
// content is retained.
bool result = true;
while (aux.size() > 1) {
// Fetch current top two // elements of aux and check // if they are consecutive. int x = aux.top(); aux.pop(); int y = aux.top(); aux.pop(); if (abs(x - y) != 1) result = false;
// Push the elements to original // stack. s.push(x); s.push(y); }
if (aux.size() == 1) s.push(aux.top()); return result; }
// Driver program
int main()
{
stack(int> s;
s.push(4);
s.push(5);
s.push(-2);
s.push(-3);
s.push(11);
s.push(10);
s.push(5);
s.push(6);
s.push(20);
if (pairWiseConsecutive(s)) cout (( "Yes" (( endl; else cout (( "No" (( endl;
cout (( "Stack content (from top)"
" after function call\n";
while (s.empty() == false)
{
cout (( s.top() (( " ";
s.pop();
}
return 0; } Output:
Yes Stack content (from top) after function call 20 6 5 10 11 -3 -2 5 4 Time complexity: O(n). Auxiliary Space : O(n).
Brief definition of Stacks ?
In general, Stack is a linear data structure where elements are inserted in the LIFO order. LIFO stands for Last In First Out, which means that the last element to be inserted in the stack will be the first one to be removed.
C++ STL has an in-built container adaptor which implements the stack data structure internally. We can directly use this container to implement stacks in our programs and perform a number of operations available.
Insertion and Deletion in a stack are done from a single end which is the rear end of the stack data structure.
The stack class is available in which header file ?
file
What does push() do in stacks ?
The push function adds an element ‘g’ passed as parameter to it at the top of the stack.
What pop() does in stacks ?
The pop() function deletes the topmost element of the stack.
What top() does in a stack ?
top(): This function returns a reference to the topmost element of the stack
What size() does in a stack ?
size(): The size() function returns the size of the stack, i.e., the number of elements present in the Stack.
What empty() does in a stack ?
empty(): This function is used to check whether the stack is empty. If the stack is empty it will return True otherwise it will return False.
Can we use loop on stacks for traversals ?
We cannot access stack elements randomly as they are not stored at contigous memory locations. Hence, we cannot use loops or iterators to traverse stacks.
What is the time complexity for all the operations on stack ?
All of the above five functions we discussed works in constant time complexity.
push() —–
pop() —– \
top() —– — O(1) Time Complexity.
size() —– /
empty() —–
Is stack an container adapter ?
Container Adaptor: In C++ STL, container adaptor is a term used for containers that can be built upon other containers. That is, they can be implemented using other containers already available in C++ STL.
The stack is a container adaptor and can be implemented using any other container which supports below operations: Inserting elements to the end. Deleting elements from the end. Returning size of the container. Returning element from the end. Checking if the container is empty.
Give naive approach
Problem: Given an array, print the Next Greater Element(NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in the array. Elements for which no greater element exist, consider next greater element as -1.
Example:
Input: arr[] = {4, 5, 2, 25}
Output:
Element NGE
4 --> 5
5 --> 25
2 --> 25
25 --> -1
Input: arr[] = {1, 2, 4, 8, 6, 10}
Output:
Element NGE
1 --> 2
2 --> 4
4 --> 8
6 --> 10
8 --> 10
10 --> -1
Method 1: A naive method.
Use of two loops: The outer loop picks all the elements one by one. The inner loop looks for the first greater element for the element picked by the outer loop. If a greater element is found then that element is printed as next, otherwise, -1 is printed.
Time complexity: Time taken by above algorithm is O(N2)
Give an appraoch to solve it in linear time
Problem: Given an array, print the Next Greater Element(NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in the array. Elements for which no greater element exist, consider next greater element as -1.
Example:
Input: arr[] = {4, 5, 2, 25}
Output:
Element NGE
4 --> 5
5 --> 25
2 --> 25
25 --> -1
Input: arr[] = {1, 2, 4, 8, 6, 10}
Output:
Element NGE
1 --> 2
2 --> 4
4 --> 8
6 --> 10
8 --> 10
10 --> -1
Method 2: Using of Stack.
Step 1: Push the first element to stack.
Step 2: Pick rest of the elements one by one and follow the following steps in loop.
Mark the current element as next.
If stack is not empty, compare top element of stack with next.
If next is greater than the top element, Pop element from stack. next is the next greater element for the popped element.
Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
Step 3: Finally, push the next in the stack.
After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.
Time Complexity: O(n)
The worst case occurs when all elements are sorted in decreasing order. If elements are sorted in decreasing order, then every element is processed at most 4 times.
Implementation
// A Stack based C++ program to find next // greater element for all array elements. #include using namespace std;
// Prints element and NGE pair for all
// elements of arr[] of size n
void printNGE(int arr[], int n)
{
stack s;
// Push the first element to stack
s.push(arr[0]);
// Iterate for rest of the elements
for (int i = 1; i < n; i++) {
if (s.empty()) {
s.push(arr[i]);
continue;
}
// if stack is not empty, then
// pop an element from stack.
// If the popped element is smaller
// than next, then
// a) print the pair
// b) keep popping while elements are
// smaller and stack is not empty
while (
s.empty() == false
&& s.top() < arr[i]) {
cout << s.top() << " --> "
<< arr[i] << endl;
s.pop();
}
// Push next to stack so that we can
// find next greater for it
s.push(arr[i]);
}
// After iterating over the loop,
// remaining elements in stack do
// not have the next greater element,
// so print -1 for them
while (s.empty() == false) {
cout << s.top() << " --> "
<< -1 << endl;
s.pop();
}
}
// Driver program to test above functions
int main()
{
int arr[] = { 4, 5, 2, 25 };
int n = sizeof(arr) / sizeof(arr[0]);
printNGE(arr, n);
return 0;
}
Problem: Given a sequence of small open and closed parenthesis, you need to check and return if the parenthesis is balanced or not.
Input: string = “(())(())”
Output: 1
Input: string = “(()))”
Output: 0
Approach:
Step1: Declare a stack of characters.
Step2: Traverse the given expression and if the character is open parenthesis then push it in the stack.
Step3: If the character is closed parenthesis then remove that character from stack but you also need to check whether stack is empty or not for avoiding empty exception and return 0 if it so.
Step4: Finally check of the stack is empty or not, if it is empty then return 1 otherwise 0 i.e. if containing open parenthesis return 0.
Time complexity: O(N)
Auxiliary space: O(N)
// Program to check whether the given // bracket sequence is balanced or not. #include using namespace std;
// Function to check the balance
bool isBalanced(string str)
{
// Creating a stack
stack st;
// Iterating through the string
// of braces
for(int i = 0; i < str.length(); i++)
{
// Pusing the elements into stack
if(str[i] == '(')
st.push(str[i]);
// Popping the elements out
else
{
if(st.empty())
return 0;
st.pop();
}
}
// Checking the balance
if(!st.empty())
return 0;
return 1;
}
// Drivers Method
int main()
{
string bracSeq = "(())(())";
cout << isBalanced(bracSeq);
return 0;
}
Problem: Given a String reverse it using Stack.
Input: string = “GeeksQuiz”
Output: “ziuQskeeG”
Input: string = “Welcome to GFG”
Output: “GFG ot emocleW”
Time Complexity: The time taken for this algorithm is O(N) as we are inserting all the elements of string in the stack and then removing it from the stack.
Approach: Create a stack of characters and store all the characters of the string in it. After that, you can remove elements one by one from the stack and print it.
// Program to print the reverse of string #include using namespace std;
// Function to perform the
// reverse operation
void reverse(string str)
{
// Creating a stack of characters
stack st;
// Pushing elements into the stack
for (int i = 0; i < str.length(); i++)
st.push(str[i]);
// Popping elements from the top
// to get the reverse order
while (!st.empty()) {
cout << st.top();
st.pop();
}
}
// Driver Method
int main()
{
// String to reverse
string str = "GeeksQuiz";
reverse(str);
return 0; }
Problem: Given a string of expression, evaluate the eqivalent Postfix expression for it.
Examples:
Input: “231*+9-“
Output: -4
Input: “570*+6-“
Output: -1
Approach:
Step 1: Create a Stack to store operands(values)
Step 2: Scan the given expression and do following for every scanned element.
If the element is a number, push it into the stack
If the element is an operator, pop operands for the operator from the stack. Evaluate the operator and push the result back to the stack.
Step 3: When the expression ends, the number in the stack is the final answer
Time complexity: The evaluation of algorithm takes O(n) time, where n is the number of characters in input expression.
// Program to evaluate the // postfix expression #include using namespace std;
// Function to evaluate postfix
// expressions
int evaluatePostfix(string str)
{
// Creating an empty stack
stack st;
int n = str.length();
// Traversing the string
for (int i = 0; i < n; i++) {
// Pushing elements into stack
// if element is a number
if (isdigit(str[i]))
st.push(str[i] - '0');
// Evaluation of the expression
else {
int val1 = st.top();
st.pop();
int val2 = st.top();
st.pop();
char op = str[i];
// Checking for the operators
switch (op) {
case '+':
st.push(val2 + val1);
break;
case '-':
st.push(val2 - val1);
break;
case '*':
st.push(val2 * val1);
break;
case '/':
st.push(val2 / val1);
break;
}
}
}
return st.top();
}
// Drivers Method
int main()
{
string str = "231*+9-";
cout << evaluatePostfix(str) << endl;
return 0; }
Do it by in n^2
The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate span of stock’s price for all n days.
The span Si of the stock’s price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than its price on the given day.
For example, if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}
A Simple but inefficient method
Traverse the input price array. For every element being visited, traverse elements on the left of it and increment the span value of it while elements on the left side are smaller.
Following is the implementation of this method: // C++ program for brute force method // to calculate stock span values #include using namespace std;
// Fills array S[] with span values
void calculateSpan(int price[], int n, int S[])
{
// Span value of first day is always 1
S[0] = 1;
// Calculate span value of remaining days
// by linearly checking previous days
for (int i = 1; i < n; i++)
{
S[i] = 1; // Initialize span value
// Traverse left while the next element // on left is smaller than price[i] for (int j = i - 1; (j >= 0) && (price[i] >= price[j]); j--) S[i]++; } }
// A utility function to print elements of array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver code
int main()
{
int price[] = { 10, 4, 5, 90, 120, 80 };
int n = sizeof(price) / sizeof(price[0]);
int S[n];
// Fill the span values in array S[] calculateSpan(price, n, S);
// print the calculated span values printArray(S, n);
return 0; }
Do it by using stack
The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate span of stock’s price for all n days.
The span Si of the stock’s price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than its price on the given day.
For example, if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}
A Linear-Time Complexity Method
We see that S[i] on the day i can be easily computed if we know the closest day preceding i, such that the price is greater than on that day than the price on the day i. If such a day exists, let’s call it h(i), otherwise, we define h(i) = -1.
The span is now computed as S[i] = i – h(i). See the following diagram.
To implement this logic, we use a stack as an abstract data type to store the days i, h(i), h(h(i)), and so on. When we go from day i-1 to i, we pop the days when the price of the stock was less than or equal to price[i] and then push the value of day i back into the stack.
Following is the implementation of this method.
We have to check also for a case when all the stock prices should be the same so therefore we have to just check whether the current stock price is bigger than the previous one or not . We will not pop from the stack when the current and previous stock prices are the same.
// C++ linear time solution for stock span problem #include #include using namespace std;
// A stack based efficient method to calculate
// stock span values
void calculateSpan(int price[], int n, int S[])
{
// Create a stack and push index of first
// element to it
stack st;
st.push(0);
// Span value of first element is always 1 S[0] = 1;
// Calculate span values for rest of the elements
for (int i = 1; i < n; i++) {
// Pop elements from stack while stack is not
// empty and top of stack is smaller than
// price[i]
while (!st.empty() && price[st.top()] < price[i])
st.pop();
// If stack becomes empty, then price[i] is // greater than all elements on left of it, // i.e., price[0], price[1], ..price[i-1]. Else // price[i] is greater than elements after // top of stack S[i] = (st.empty()) ? (i + 1) : (i - st.top());
// Push this element to stack st.push(i); } }
// A utility function to print elements of array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver program to test above function
int main()
{
int price[] = { 10, 4, 5, 90, 120, 80 };
int n = sizeof(price) / sizeof(price[0]);
int S[n];
// Fill the span values in array S[] calculateSpan(price, n, S);
// print the calculated span values printArray(S, n);
return 0; }
Given an array of distinct elements, find previous greater element for every element. If previous greater element does not exist, print -1.
Examples:
Input : arr[] = {10, 4, 2, 20, 40, 12, 30}
Output : -1, 10, 4, -1, -1, 40, 40
Input : arr[] = {10, 20, 30, 40}
Output : -1, -1, -1, -1
Input : arr[] = {40, 30, 20, 10}
Output : -1, 40, 30, 20
Expected time complexity : O(n)
An efficient solution is to use stack data structure. If we take a closer look, we can notice that this problem is a variation of stock span problem. We maintain previous greater element in a stack.
// C++ program previous greater element // An efficient solution to print previous greater // element for every element in an array. #include using namespace std;
void prevGreater(int arr[], int n)
{
// Create a stack and push index of first element
// to it
stack s;
s.push(arr[0]);
// Previous greater for first element is always -1. cout << "-1, ";
// Traverse remaining elements
for (int i = 1; i < n; i++) {
// Pop elements from stack while stack is not empty // and top of stack is smaller than arr[i]. We // always have elements in decreasing order in a // stack. while (s.empty() == false && s.top() < arr[i]) s.pop();
// If stack becomes empty, then no element is greater // on left side. Else top of stack is previous // greater. s.empty() ? cout << "-1, " : cout << s.top() << ", ";
s.push(arr[i]);
}
}
// Driver code
int main()
{
int arr[] = { 10, 4, 2, 20, 40, 12, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
prevGreater(arr, n);
return 0;
}
Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in the array. Elements for which no greater element exist, consider the next greater element as -1.
Examples:
For an array, the rightmost element always has the next greater element as -1.
For an array that is sorted in decreasing order, all elements have the next greater element as -1.
For the input array [4, 5, 2, 25], the next greater elements for each element are as follows.
Element NGE
4 –> 5
5 –> 25
2 –> 25
25 –> -1
d) For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows.
Element NGE 13 --> -1 7 --> 12 6 --> 12 12 --> -1
Method 2 (Using Stack)
Push the first element to stack.
Pick rest of the elements one by one and follow the following steps in loop.
Mark the current element as next.
If stack is not empty, compare top element of stack with next.
If next is greater than the top element, Pop element from stack. next is the next greater element for the popped element.
Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements.
Finally, push the next in the stack.
After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.
// A Stack based C++ program to find next // greater element for all array elements. #include using namespace std;
/* prints element and NGE pair for all
elements of arr[] of size n */
void printNGE(int arr[], int n)
{
stack s;
/* push the first element to stack */ s.push(arr[0]);
// iterate for rest of the elements
for (int i = 1; i < n; i++)
{
if (s.empty()) {
s.push(arr[i]);
continue;
}
/* if stack is not empty, then
pop an element from stack.
If the popped element is smaller
than next, then
a) print the pair
b) keep popping while elements are
smaller and stack is not empty */
while (s.empty() == false
&& s.top() < arr[i])
{
cout << s.top()
<< " --> " << arr[i] << endl;
s.pop();
}
/* push next to stack so that we can find next greater for it */ s.push(arr[i]); }
/* After iterating over the loop, the remaining
elements in stack do not have the next greater
element, so print -1 for them */
while (s.empty() == false) {
cout << s.top() << " --> " << -1 << endl;
s.pop();
}
}
/* Driver code */
int main()
{
int arr[] = { 11, 13, 21, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
printNGE(arr, n);
return 0;
}
How to find an element in a stack ?
bool find(stack s, int val)
{
while(!s.empty()) {
if (s.top() == val) return true;
s.pop();
}
return false;
}
Given a stack with push(), pop(), empty() operations, delete the middle of the stack without using any additional data structure.
Middle: ceil(size_of_stack/2.0)
Example 1:
Input:
Stack = {1, 2, 3, 4, 5}
Output:
ModifiedStack = {1, 2, 4, 5}
Explanation:
As the number of elements is 5 ,
hence the middle element will be the 3rd
element which is deleted
Example 2:
Input:
Stack = {1 2 3 4}
Output:
ModifiedStack = {1 3 4}
Explanation:
As the number of elements is 4 ,
hence the middle element will be the 2nd
element which is deleted
Your Task:
You don’t need to read input or print anything. Complete the function deleteMid() which takes the stack and its size as input parameters and modifies the stack in-place.
Note: The output shows the stack from top to bottom.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Recursively call the delete function until you get on the middle element and them pop the element, you will get a stack without the middle element.
class Solution
{
public:
//Function to delete middle element of a stack.
void deleteMid_util(stack&s, int sizeOfStack, int current)
{
//if current pointer is half of the size of stack then we
//are accessing the middle element of stack.
if(current==sizeOfStack/2)
{
s.pop();
return;
}
//storing the top element in a variable and popping it.
int x = s.top();
s.pop();
current+=1;
//calling the function recursively.
deleteMid_util(s,sizeOfStack,current);
//pushing the elements (except middle element) back
//into stack after recursion calls.
s.push(x);
}
void deleteMid(stack&s, int sizeOfStack)
{
deleteMid_util(s,sizeOfStack,0);
}
};
Now, we’ll try to solve a famous stack problem.
You are given an array A of size N. You need to first push the elements of the array into a stack and then print minimum in the stack at each pop.
Example 1:
Input:
N = 5
A = {1 2 3 4 5}
Output:
1 1 1 1 1
Explanation:
After pushing elements to the stack,
the stack will be “top -> 5, 4, 3, 2, 1”.
Now, start popping elements from the stack
popping 5: min in the stack is 1.popped 5
popping 4: min in the stack is 1. popped 4
popping 3: min in the stack is 1. popped 3
popping 2: min in the stack is 1. popped 2
popping 1: min in the stack is 1. popped 1
Example 2:
Input:
N = 7
A = {1 6 43 1 2 0 5}
Output:
0 0 1 1 1 1 1
Explanation:
After pushing the elements to the stack,
the stack will be 5->0->2->1->43->6->1.
Now, poping the elements from the stack:
popping 5: min in the stack is 0. popped 5
popping 0: min in the stack is 0. popped 0
popping 2: min in the stack is 1. popped 2
popping 1: min in the stack is 1. popped 1
popping 43: min in the stack is 1.
popped 43
popping 6: min in the stack is 1. popped 6
popping 1: min in the stack is 1. popped 1.
Your Task:
Since this is a function problem, you don’t need to take any input. Just complete the provided functions _push() and _getMinAtPop(). The _push() function takes an array as parameter, you need to push all elements of this array onto a stack and return the stack. The _getMinAtPop() accepts a stack as a parameter which is returned by _push() function and prints minimum in the stack at each pop separated by spaces.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Approach:
first we will copy all the elements from the array to a stack and then that stack will be used in finding the min element in the stack by using a seperate function.
stack _push(int arr[],int n)
{
// your code here
stack s;
for (int i = 0; i < n; i++) {
s.push(arr[i]);
}
return s;
}
//Function to print minimum value in stack each time while popping.
int getMin(stacks)
{
// your code here
int ans = INT_MAX;
while(!s.empty()) {
ans = min(ans, s.top());
s.pop();
}
return ans;
}
void _getMinAtPop(stack s) {
int x;
while(!s.empty()) {
x = getMin(s);
s.pop();
cout << x << " ";
}
}
Given an integer array Arr of size N. For each element in the array, check whether the right adjacent element (on the next immediate position) of the array is smaller. If next element is smaller, update the current index to that element. If not, then -1.
Example 1:
Input:
N = 5
Arr[] = {4, 2, 1, 5, 3}
Output:
2 1 -1 3 -1
Explanation: Array elements are 4, 2, 1, 5
3. Next to 4 is 2 which is smaller, so we
print 2. Next of 2 is 1 which is smaller,
so we print 1. Next of 1 is 5 which is
greater, so we print -1. Next of 5 is 3
which is smaller, so we print 3. Note
that for last element, output is always
going to be -1 because there is no element
on right.
Example 2:
Input:
N = 6
Arr[] = {5, 6, 2, 3, 1, 7}
Output:
-1 2 -1 1 -1 -1
Explanation: Next to 5 is 6 which is
greater, so we print -1.Next of 6 is 2
which is smaller, so we print 2. Next
of 2 is 3 which is greater, so we
print -1. Next of 3 is 1 which is
smaller, so we print 1. Next of 1 is
7 which is greater, so we print -1.
Note that for last element, output is
always going to be -1 because there is
no element on right.
Your Task:
You don't need to read input or print anything. Your task is to complete the function immediateSmaller() which takes the array of integers arr and n as parameters. You need to change the array itself.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
class Solution{
public:
void immediateSmaller(int *arr, int n) {
// code here
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i])
arr[i - 1] = arr[i];
else
arr[i - 1] = -1;
}
arr[n - 1] = -1;
}
};
Linked list implementation of stack
public class Stack<T> {
private class Node {
T data;
Node next;
Node(T data) {
this.data = data;
this.next = null;
}
}
private Node top;
private int size;
public Stack() {
top = null;
size = 0;
}
// Push operation to add element to the top of stack
public void push(T item) {
Node newNode = new Node(item);
newNode.next = top;
top = newNode;
size++;
}
// Pop operation to remove and return the top element
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
T item = top.data;
top = top.next;
size--;
return item;
}
// Peek operation to view the top element without removing it
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return top.data;
}
// Check if stack is empty
public boolean isEmpty() {
return top == null;
}
// Get the current size of stack
public int size() {
return size;
}
}
This implementation includes:
1. A generic type T so the stack can hold any data type
2. An inner Node class to create the linked structure
3. Basic stack operations:
- push(): Adds an element to the top
- pop(): Removes and returns the top element
- peek(): Views the top element without removing it
- isEmpty(): Checks if stack is empty
- size(): Returns the number of elements
Here’s how you can use it:
Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.pop()); // Outputs: 3 System.out.println(stack.peek()); // Outputs: 2 System.out.println(stack.size()); // Outputs: 2
