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 C++
#include (bits/stdc++.h> using namespace std;
struct Node{
int data;
Node *next;
Node(int x){
data=x;
next=NULL;
}
};
struct MyStack{
Node *head;
int sz;
MyStack(){
head=NULL;
sz=0;
}
void push(int x){
Node *temp=new Node(x);
temp->next=head;
head=temp;
sz++;
}
int pop(){
if(head==NULL){cout(("Stack is Empty"((endl;return INT_MAX;}
int res=head->data;
Node *temp=head;
head=head->next;
delete(temp);
sz--;
return res;
}
int peek(){
if(head==NULL){cout(("Stack is Empty"((endl;return INT_MAX;}
return head->data;
}
int size(){
return sz;
}
bool isEmpty(){
return head==NULL;
}
};
int main()
{
MyStack s;
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; }
Applications of stack:
Stacks can be used to check for the balancing of paranthesis in an expression.
Infix to Postfix/Prefix conversion.
Redo-undo features at many places such as editors, photoshop, etc.
Forward and backward feature in web browsers.
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]
We follow this algorithm.
Create a temporary stack say tmpStack.
While input stack is NOT empty do this:
Pop an element from input stack call it temp
while temporary stack is NOT empty and top of temporary stack is greater than temp,
pop from temporary stack and push it to the input stack
push temp in temporary stack
The sorted numbers are in tmpStack
// C++ program to sort a stack using an // auxiliary stack. #include (bits/stdc++.h> using namespace std;
// This function return the sorted stack
stack(int> sortStack(stack(int> &input)
{
stack(int> tmpStack;
while (!input.empty())
{
// pop out the first element
int tmp = input.top();
input.pop();
// while temporary stack is not empty and top
// of stack is greater than temp
while (!tmpStack.empty() && tmpStack.top() > tmp)
{
// pop from temporary stack and push
// it to the input stack
input.push(tmpStack.top());
tmpStack.pop();
}
// push temp in temporary of stack tmpStack.push(tmp); }
return tmpStack; }
// main function
int main()
{
stack(int> input;
input.push(34);
input.push(3);
input.push(31);
input.push(98);
input.push(92);
input.push(23);
// This is the temporary stack stack(int> tmpStack = sortStack(input); cout (( "Sorted numbers are:\n";
while (!tmpStack.empty())
{
cout (( tmpStack.top()(( " ";
tmpStack.pop();
}
}
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.
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; }
