Stack -Data Structure
What is Stack?
A stack is a non-primitive linear data structure. it is an ordered list in which the addition of a new data item and deletion of the already existing data item is done from only one end known as the top of the stack (TOS). The element which is added in last will be first to be removed and the element which is inserted first will be removed in last. As all the deletion and insertion in a stack is done from the top of the stack, the last added element will be the first to be removed from the stack. That is the reason why stack is also called Last-in-First-out (LIFO).
The most frequently accessible element in the stack is the topmost element, whereas the least accessible element is the bottom of the stack. Push and Pop are two operations that are provided for insertion and deletion from the top of the stack respectively.
Stack Implementation
The stack can be implemented in two ways :
- Static implementation
- Dynamic implementation
Static Implementation: — Here array is used to create a stack. it is a simple technique but is not a flexible way of creation, as the size of the stack has to be declared during program design, after that size implementation is not efficient with respect to memory utilization.
Dynamic implementation: — It is also called linked list representation and uses a pointer to implement the stack type of data structure.
Basics operations on the stack:
Push
Pop
Push operation: — The process of adding new elements to the top of the stack is called push operation.
Algorithm for PUSH operation
- Check if the stack is full or not.
- If the stack is full, then print error of overflow and exit the program.
- If the stack is not full, then increment the top and add the element.
PUSH (Stack, Size, TOP, x)
{
if (TOP=Size)
Print stack overflow and exit
TOP = TOP + 1
Stack[TOP] = x
EXIT
}Pop: — The process of deleting an element. from the top of the stack is called POP operation
Algorithm for POP operation
- Check if the stack is empty or not.
- If the stack is empty, then print error of underflow and exit the program.
- If the stack is not empty, then print the element at the top and decrement the top.
POP (Stack, Size, TOP)
{
if (TOP==-1)
Print Underflow
X = Stack[TOP]
TOP=TOP-1
Return X and Exit
}Code:
- Java Code
import java.util.*;
class Stack {
static final int MAX = 1000;
static int top;
static int arr[] = new int[MAX]; // Maximum size of Stack
static boolean isEmpty()
{
return (top < 0);
}
Stack()
{
top = -1;
}
static boolean push(int val)
{
if (top >= (MAX - 1)) {
System.out.println("Stack Overflow");
return false;
}
else {
arr[++top] = val;
System.out.println(val + " pushed into stack");
return true;
}
}
static int pop()
{
if (top < 0) {
System.out.println("Stack Underflow");
return 0;
}
else {
int val = arr[top--];
return val;
}
}
static int peek()
{
if (top < 0) {
System.out.println("Stack Underflow");
return 0;
}
else {
int val = arr[top];
return val;
}
}
static void print(){
for(int i = top;i>-1;i--){
System.out.print(" "+ arr[i]);
}
}
}
// Driver code
class TUF {
public static void main(String args[])
{
Stack s = new Stack();
s.push(10);
s.push(20);
s.push(30);
System.out.println(s.pop() + " Popped from stack");
System.out.println("Top element is :" + s.peek());
System.out.print("Elements present in stack :");
s.print();
}
}Output:
10 pushed into stack
20 pushed into stack
30 pushed into stack
30 Popped from stack
Top element is :20
Elements present in stack : 20 10
- C++ Code
#include <bits/stdc++.h>using namespace std;#define MAX 1000class Stack {
int top;public:
int arr[MAX]; // Maximum size of Stack Stack() { top = -1; }
bool push(int value)
{
if (top >= (MAX - 1)) {
cout << "Stack Overflow";
return false;
}
else {
arr[++top] = value;
cout << value << " pushed into stack\n";
return true;
}
}int pop()
{
if (top < 0) {
cout << "Stack Underflow";
return 0;
}
else {
int val = arr[top--];
return val;
}
}
int peek()
{
if (top < 0) {
cout << "Stack is Empty";
return 0;
}
else {
int val = arr[top];
return val;
}
}bool isEmpty()
{
return (top < 0);
}
};int main()
{
class Stack s;
s.push(10);
s.push(20);
s.push(30);
cout << s.pop() << " Popped from stack\n";
cout<<"Elements present in stack : ";
while(!s.isEmpty())
{
cout<<s.peek()<<" ";
s.pop();
} return 0;
}
Output:
10 pushed into stack
20 pushed into stack
30 pushed into stack
30 Popped from stack
Elements present in stack : 20 10
Analysis of Stack Operations:
Below mentioned are the time complexities for various operations that can be performed on the Stack data structure.
- Push Operation : O(1)
- Pop Operation : O(1)
- Top Operation : O(1)
- Search Operation : O(n)
Applications of Stack
What is a stack?
Stack is a linear data structure in which elements are stored in a certain order. It follows the LIFO or FILO approach which is Last In First Out or First In Last Out respectively.
The two main operations that can be performed on the stack data structure are push() and pop().
There are other options which include top(), isEmpty(), etc.
We see a stack in our day-to-day lives. For example, a stack of books, a stack of clothes, a stack of shoeboxes, etc.
Applications of stack
- Stack can be really handy in solving problems like balanced parenthesis, reversal of a string, stock span problem, etc.
- Balanced Parenthesis: Suppose you are given a string of parenthesis, say “({})” you need to check if for every opening parenthesis there exists a closing parenthesis. You need to make sure that the order of both closing and opening parenthesis should remain the same.
- Reversal of a string: Suppose you are given a string, say “takeyouforward” and you need to reverse the string. The result should be “drawrofuoyekat”.
- This can be done using a stack by storing the characters in the stack and then popping them out of the stack and simultaneously printing the popped element.
- Stock Span Problem: You’ll be given a daily price of a stock in the form of an array and you need to return the span of the stock’s price for the current day.
- Stack can also be used to implement backtracking approach.
- Stack can be used in inter-conversion and solving of infix, prefix and postfix expressions.
- Infix Expression: An expression where operators come in between two operands. Example: “a+b”.
- Prefix Expression: An expression where operators come before two operands. Example: “+ab”
- Postfix Expression: An expression where operators come after two operands. Example: “ab+”
- Stacks can be really useful in solving these types of expressions and would also work in the inter-conversion of these expressions.
- Calling and implementing of functions is also achieved using stacks.
- If a function called by a program calls another function and that function calls another function, we can assume it as a function call stack. Following code helps in understanding the concept.
func1() {
func2();
}
func2() {
func3();
}
main() {
func1();
}The following diagram represents a function call stack.
5. Stacks can also be used in DFS (Depth First Search)
These are some of the most popular stack applications that we thought of sharing with you, if you know anything else apart from these, please share with us in the comments below.
Implement K stacks in a single Array
Problem Statement: Design a data structure to implement ’N’ stacks using a single array of size ‘S’. It should support the following operations:
- push(X, M): Pushes an element X into the Mth stack. Returns true if the element is pushed into the stack, otherwise false.
- pop(M): Pops the top element from Mth Stack. Returns -1 if the stack is empty, otherwise, returns the popped element.
Examples:
Input: K , N ( K denotes the no. of stacks , N is the size of the array)
There are two types of queries denote these operations :
Type 1: for push(X, M) operation.
Type 2: for pop(M) operation.Input: push(11,0)
Output: Pushes element 11 into stack 0Input: push(13,1)
Output: Pushes element 13 into stack 1Input: pop(1)
Output: Pops the top element from stack 1.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Brute Force
Since we are given one array(size n) and k stacks , the basic approach can be to divide this array into k parts . Where length of each part will be k/n and each part will have its own top to implement the stack.
Code:
- C++ Code
#include<bits/stdc++.h>
using namespace std;int pop(int stno,vector<int> &arr,int &t1,int &t2,int &t3){
if(stno==0){
if(t1!=0){ return arr[t1--];
}
}
else if(stno==1){
if(t2!=0){
return arr[t2--];
}
}
if(t3!=0){
return arr[t1--];
}
return INT_MAX;
}
void push(int ele,int stno,int &t1,int &t2,int &t3,int &b1,int &b2,int &b3,
vector<int>&arr){
cout<<"Element pushed in the stack"<<endl;
if(stno == 0){
if(t1==b1){
cout<<"overflow";
return;
}
else arr[++t1]=ele;
}
else if(stno == 1){
if(t2==b2){
cout<<"overflow";
return;
}
else arr[++t2]=ele;
}
else{
if(t3==b3){
cout<<"overflow";
return;
}
else arr[++t3]=ele;
}
return ;
}
int main(){
int n = 9;
int k = 3;
vector<int>arr(n);
int t1 = -1 ,t2=2,t3=5;
int b1=t1+3,b2=t2+3,b3=t3+3;
//Suppose we are pushing element 11 in stack 0
push(11,0,t1,t2,t3,b1,b2,b3,arr);
push(13,0,t1,t2,t3,b1,b2,b3,arr);
cout<<"Element popoed from the stack "<<pop(0,arr,t1,t2,t3);
return 0;
}
Output:
Element pushed in the stack
Element pushed in the stack
Element popoed from the stack 13
Solution 2: Optimal Approach
Here , we will take 3 array , arr to keep the elements , top array to store the top of each stack and next array , to store the next free space as well as the previous element in the stack. We also use a variable free, to keep track of the next free space.
Initially the array, arr is empty. The top is initialized to -1 as there are no elements in the stack . The next array keeps track of the next free element , so it will be initialized as , index 0 will have 1 , index 1 will have 2 and so on , because the next free space to index 0 at initially is the just next block .
next[n-1] will be -1 because there are no more blocks after that.
CASE 1: Push (11,0) push element 11 in stack 0
We will first check free , here we get the index i of the next free space ,we update free to the next[i]. Now next[i] will keep track of the previous element to which we are about to add, so next[i]=top[0] // top of stack , we then update top of stack in stack array, top[0] = 0 ,because 0 is the index where we are going to store the element. Now we add the element at arr[i] = 11.
CASE 2: Push (13,0) push element 13 in stack 0
We again will first check free which is 1, here we get the index i of the next free space so i=1 now ,we update free to the next[i] , free becomes 2. Now next[i] will keep track of the previous element to which we are about to add, so next[i]=top[0] ,i.e, next[i] = 0 // top of stack , we then update top of stack in stack array, top[0] = i,because 1 is the index where we are going to store the element. Now we add the element at arr[i] = 13.
CASE 3: Push (15,1) push element 15 in stack 1
We again will first check free which is 2, here we get the index i of the next free space so i=2 now, we update free to the next[i], free becomes 3. Now next[i] will keep track of the previous element to which we are about to add, so next[i]=top[1], i.e, next[i] = -1 // top of stack, we then update top of stack in stack array, top[1] = i,because 3 is the index where we are going to store the element. Now we add the element at arr[i] = 15.
Case 4: pop element from stack 0
To pop an element from a stack, we know we have to remove from the top. We got to top[st no] and check the top element. This also gives us the index I at which in the next array, the previous element to current top is stored. We go to next [1] which is 0, so now new top will be 0 . And as we are going to delete this entry next[i] will get free, so we update next[i]=free, because as we had decided it will keep track of next free cell and free= I, as current cell is now going to be empty. We can now return arr[i] as that is the top element in the stack.
To check if stack is empty, we can simply check is top[st no] = -1
For overflow we can stop when we get free=-1
Code:
- C++ Code
#include<bits/stdc++.h>
using namespace std;int pop(int stno,vector<int> &arr,vector<int>&top,vector<int>&next,int &free){
int i;
if(top[stno]==-1){
cout<<"Underflow"; // can't pop if stack is empty
return 1e9; // just because we have to return something in
//case of underflow
}
i=top[stno]; //find top of stack
top[stno] = next[i]; // change top to updated top
next[i]=free; // because this cell is now clear
free=i;
return arr[i];
}
void push(int ele,int stno,vector<int> &arr,vector<int>&top,vector<int>&next,
int &free ){
cout<<"Element is pushed in the stack"<<endl;
int i;
if(free == -1){ //overflow condition
cout<<"stack overflow"<<endl;
return ;
}
else{
i= free; // i= space where we can add element
free=next[i]; // free is next[i], next avilable space
next[i]=top[stno]; // keeps track of previous top
top[stno]=i; // changes top to new top
arr[i]=ele; //stores the element
}
return ;
}
int main(){
int n = 9,i,free;
int k=3;
vector<int>arr(n);
vector<int>top(k,-1);
vector<int>next(n);
for(int i=0;i<n-1;i++){
next[i]=i+1; //Initialize next array to keep tarack of free spaces
}
next[n-1]=-1;
free=0;
push(11,0,arr,top,next,free);
push(13,0,arr,top,next,free);
push(15,1,arr,top,next,free);
cout<<"Element is popped from the stack "<<pop(0,arr,top,next,free);
cout<<endl;
cout<<"Element is popped from the stack "<<pop(0,arr,top,next,free);
return 0;
}Output:
Element is pushed in the stack
Element is pushed in the stack
Element is pushed in the stack
Element is popped from the stack 13
Element is popped from the stack 11
Two stacks in an array
Problem Statement: You need to try implementing 2 stacks in a single array.
Example:
push1(10): Insert 10 in stack1
push2(21): Insert 21 in stack2
pop2(): Pop top element from stack2Approaches
To solve this problem, we can use 2 approaches. One is space efficient and one is not.
In this article, we’ll discuss both approaches.
Approach 1: Divide the array into two equal halves
In this approach, we’ll divide the array into two equal halves.
One half would be assigned to stack1 and one half would be assigned to stack 2.
The following diagram explains the above approach
Let’s try coding this approach. Here we’ll use class twoStack to build our two-stack array.
Code:
- Java Code
import java.util.*;
class TUF{
public static void main(String args[]) {
twoStack ts=new twoStack(5);
ts.pushStack1(10);
ts.pushStack1(22);
ts.popStack1();
ts.popStack2();
ts.popStack1();
}
}
class twoStack {
static int arr[];
static int size;
static int top1;
static int top2;
twoStack(int n) {
arr = new int[n];
size = n;
top1 = n / 2 + 1;
top2 = n / 2;
}
static void pushStack1(int data) {
if (top1 > 0) {
top1--;
arr[top1] = data;
System.out.println("Element pushed");
} else {
System.out.println("Stack Overflow");
}
}
static void pushStack2(int data) {
if (top2 < size - 1) {
top2++;
arr[top2] = data;
System.out.println("Element pushed");
} else {
System.out.println("Stack Overflow");
}
}
static void popStack1() {
if (top1 <= size / 2) {
top1++;
System.out.println("top element popped");
} else {
System.out.println("Stack Underflow");
}
}
static void popStack2() {
if (top2 >= size / 2 + 1) {
top2--;
System.out.println("top element popped");
} else {
System.out.println("Stack underflow");
}
}
}Output:
Element pushed
Element pushed
top element popped
Stack underflow
top element popped
- C++ Code
#include <iostream>
using namespace std;class twoStack {
int * arr;
int size;
int top1;
int top2;
public:
twoStack(int n) {
arr = new int[n];
size = n;
top1 = n / 2 + 1;
top2 = n / 2;
}
void pushStack1(int data) {
if (top1 > 0) {
top1--;
arr[top1] = data;
cout << "Element pushed" << "\n";
} else {
cout << "Stack Overflow" << "\n";
}
}
void pushStack2(int data) {
if (top2 < size - 1) {
top2++;
arr[top2] = data;
cout << "Element pushed" << "\n";
} else {
cout << "Stack Overflow" << "\n";
}
}
void popStack1() {
if (top1 <= size / 2) {
top1++;
cout << "top element popped" << "\n";
} else {
cout << "Stack Underflow" << "\n";
}
}
void popStack2() {
if (top2 >= size / 2 + 1) {
top2--;
cout << "top element popped" << "\n";
} else {
cout << "Stack underflow" << "\n";
}
}
};
int main() {
twoStack ts(5);
ts.pushStack1(10);
ts.pushStack1(22);
ts.popStack1();
ts.popStack2();
ts.popStack1();
}Output:
Element pushed
Element pushed
top element popped
Stack underflow
top element popped
Note: In this approach, there is a problem. Stackoverflow errors would be really common. Let’s understand this with an example.
Suppose you insert elements in stack1 and insert no elements in stack2. If we try inserting more elements in stack1, then the StackOverflow error would be raised since stack1 is full, but if we notice there is still space left in the array.
Now let’s discuss another efficient approach.
Approach 2: Efficient Approach
This approach is a dynamic approach, in terms of stack but static in terms of the array.
Here if the number of elements is greater than the half of the array in one stack, we would still insert more elements until we reach the boundary of the other stack top pointer.
Here, we assign the top pointer of stack1 to -1 and the top pointer of stack2 to the array’s size.
The following code explains the above approach
Code:
- Java Code
import java.util.*;
class TUF{
public static void main(String args[]) {
twoStack ts= new twoStack(6);
ts.pushStack1(10);
ts.popStack2();
}
}
class twoStack {
static int arr[];
static int size;
static int top1;
static int top2;
twoStack(int n) {
arr = new int[n];
size = n;
top1 = -1;
top2 = size;
}
static void pushStack1(int data) {
if (top1 < top2 - 1) {
top1++;
arr[top1] = data;
System.out.println("Element pushed");
} else System.out.println("Stack Overflow");
}
static void pushStack2(int data) {
if (top1 < top2 - 1) {
top2--;
arr[top2] = data;
System.out.println("Element pushed");
} else System.out.println("Stack Overflow");
}
static void popStack1() {
if (top1 >= 0) {
top1--;
System.out.println("Element popped");
} else System.out.println("Stack Underflow");
}
static void popStack2() {
if (top2 < size) {
top2++;
System.out.println("Element Popped");
} else System.out.println("Stack Underflow");
}
}output:
Element pushed
Stack Underflow
- C++ Code
#include <iostream>
using namespace std;class twoStack {
int * arr;
int size;
int top1;
int top2;
public:
twoStack(int n) {
arr = new int[n];
size = n;
top1 = -1;
top2 = size;
}
void pushStack1(int data) {
if (top1 < top2 - 1) {
top1++;
arr[top1] = data;
cout << "Element pushed" << "\n";
} else cout << "Stack Overflow" << "\n";
}
void pushStack2(int data) {
if (top1 < top2 - 1) {
top2--;
arr[top2] = data;
cout << "Element pushed" << "\n";
} else cout << "Stack Overflow" << "\n";
}
void popStack1() {
if (top1 >= 0) {
top1--;
cout << "Element popped" << "\n";
} else cout << "Stack Underflow" << "\n";
}
void popStack2() {
if (top2 < size) {
top2++;
cout << "Element Popped" << "\n";
} else cout << "Stack Underflow" << "\n";
}
};
int main() {
twoStack ts(6);
ts.pushStack1(10);
ts.popStack2();
return 0;
}Output:
Element pushed
Stack Underflow
This approach is super efficient when you want to dynamically expand the stack in which an element needs to be inserted when the top pointer exceeds half of the array.
Evaluation of Postfix Expression
Given a postfix expression Containing only operators [+, — , *, / ] and numbers. Postfix expression is given the form of a vector of strings. Each element is either operator or operand in postfix expression. Concatenating these strings gives the postfix expression. Evaluate the postfix expression and return the corresponding value of the expression.
NOTE: Division between two integers should truncate toward zero.
Example:
Example 1:
Input: [“ 1 ”, ” 3 ”,” - ”,” 4 ”, “ * ” ]
Output: -8
Explanation: The Arthematic Expression Corresponding to postfix is (1-3)*4 which is equal to -8.Example 2:
Input: [“ 4 ”, ” 3 ”,” 15 ”,” / ”, “ - ” ]
Output: 4
Explanation: The Arthematic Expression Corresponding to postfix is( 4 + (3/15)) which is equal to 4.Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Algorithm:
- We know that in postfix expression operator comes after the operand.
- The Intuition is to iterate the postfix expression, When we find the number/operand push it into the stack
- Whenever we encounter the operator, pop the last two numbers in the stack.
- Apply the operation corresponding to the operator on the two numbers and push back the result obtained after performing operations on the numbers into the stack.
- While applying the operation care should be taken. For operations like addition, and multiplication the order of the numbers doesn’t matter. But the order of numbers is important for subtraction and division.
- The number popped second is the first number that encounters first in infix expression. So In subtraction first popped number is subtracted from the second popped number. Similarly, In division, the second popped number is divided by the first popped number.
- After the iteration, there will be only one element left in the stack. Which is the value of the postfix expression.
Code:
- Java Code
import java.util.*;
class TUF {
static int EvalutePostfix(String[] postfix) {
Stack < Integer > st = new Stack < > ();
for (String token: postfix) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
int first = st.peek();
st.pop();
int second = st.peek();
st.pop();
if (token == "+")
st.push(first + second);
else if (token == "-")
st.push(second - first);
else if (token == "*")
st.push(first * second);
else
st.push(second / first);
} else
st.push(Integer.parseInt(token));
}
return st.peek();
}
public static void main(String args[]) {
String postfix[] = {"1","3","-","4","*"};
int value = EvalutePostfix(postfix);
System.out.println(value);
}
}Output: -8
Time Complexity: O(N) N is the no of strings in Postfix Expression. As we are iterating the postfix expression only once, Time Complexity is O(N).
Space Complexity: O(N) Space Used for the stack.
- C++ Code
#include <bits/stdc++.h>using namespace std;int EvalutePostfix(vector < string > & postfix) {
stack < int > st;
for (auto & token: postfix) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
int first = st.top();
st.pop();
int second = st.top();
st.pop();
if (token == "+")
st.push(first + second);
else if (token == "-")
st.push(second - first);
else if (token == "*")
st.push(first * second);
else
st.push(second / first);
} else
st.push(stoi(token));
}
return st.top();
}int main() {
vector < string > postfix = {"1","3","-","4","*"};
int value = EvalutePostfix(postfix);
cout << value << endl;
}
Output: -8
Time Complexity: O(N) N is the no of strings in Postfix Expression. As we are iterating the postfix expression only once, Time Complexity is O(N).
Space Complexity: O(N) Space Used for the stack.
Implement Queue using Stack
Problem Statement: Given a Stack having some elements stored in it. Can you implement a
Queue using the given Stack?
Queue: A Queue is a linear data structure that works on the basis of FIFO(First in First out). This means the element added at first will be removed first from the Queue.
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Using two Stacks where push operation is O(N)
Approach:
push(x) ->
pop()->
top()->
size()->
size() operation is for returning the size of a queue which can be done by using the function Stack1. size(). It will actually return the total number of elements in the queue.
Code:
- Java Code
import java.util.*;
class MyQueue {
Stack < Integer > input = new Stack < > ();
Stack < Integer > output = new Stack < > ();
/** Initialize your data structure here. */
public MyQueue() {
}
/** Push element x to the back of queue. */
public void push(int x) {
System.out.println("The element pushed is " + x);
input.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
// shift input to output
if (output.empty())
while (input.empty() == false) {
output.push(input.peek());
input.pop();
}
int x = output.peek();
output.pop();
return x;
}
/** Get the front element. */
public int peek() {
// shift input to output
if (output.empty())
while (input.empty() == false) {
output.push(input.peek());
input.pop();
}
return output.peek();
}
int size() {
return (output.size() + input.size());
}
}
class TUF {
public static void main(String args[]) {
MyQueue q = new MyQueue();
q.push(3);
q.push(4);
System.out.println("The element poped is " + q.pop());
q.push(5);
System.out.println("The top element is " + q.peek());
System.out.println("The size of the queue is " + q.size());
}
}Output:
The element pushed is 3
The element pushed is 4
The element poped is 3
The element pushed is 5
The top element is 4
The size of the queue is 2
Time Complexity: O(1 )
Space Complexity: O(2N)
- C++ Code
#include <bits/stdc++.h>using namespace std;struct Queue {
stack < int > input, output;
// Push elements in queue
void Push(int data) {
// Pop out all elements from the stack input
while (!input.empty()) {
output.push(input.top());
input.pop();
}
// Insert the desired element in the stack input
cout << "The element pushed is " << data << endl;
input.push(data);
// Pop out elements from the stack output and push them into the stack input
while (!output.empty()) {
input.push(output.top());
output.pop();
}
}
// Pop the element from the Queue
int Pop() {
if (input.empty()) {
cout << "Stack is empty";
exit(0);
}
int val = input.top();
input.pop();
return val;
}
// Return the Topmost element from the Queue
int Top() {
if (input.empty()) {
cout << "Stack is empty";
exit(0);
}
return input.top();
}
// Return the size of the Queue
int size() {
return input.size();
}
};
int main() {
Queue q;
q.Push(3);
q.Push(4);
cout << "The element poped is " << q.Pop() << endl;
q.Push(5);
cout << "The top of the queue is " << q.Top() << endl;
cout << "The size of the queue is " << q.size() << endl;
}
Output:
The element pushed is 3
The element pushed is 4
The element poped is 3
The element pushed is 5
The top of the queue is 4
The size of the queue is 2
Time Complexity: O(N )
Space Complexity: O(2N)
Solution 2: Using two Stacks where push operation is O(1)
Approach :
Push()->
Pop()->
top()->
Size():
Code:
- C++ Code
- Java Code
#include <bits/stdc++.h>using namespace std;class MyQueue {
public:
stack < int > input, output;
/** Initialize your data structure here. */
MyQueue() { } /** Push element x to the back of queue. */
void push(int x) {
cout << "The element pushed is " << x << endl;
input.push(x);
} /** Removes the element from in front of queue and returns that element. */
int pop() {
// shift input to output
if (output.empty())
while (input.size())
output.push(input.top()), input.pop(); int x = output.top();
output.pop();
return x;
} /** Get the front element. */
int top() {
// shift input to output
if (output.empty())
while (input.size())
output.push(input.top()), input.pop();
return output.top();
} int size() {
return (output.size() + input.size());
}};
int main() {
MyQueue q;
q.push(3);
q.push(4);
cout << "The element poped is " << q.pop() << endl;
q.push(5);
cout << "The top of the queue is " << q.top() << endl;
cout << "The size of the queue is " << q.size() << endl;}
Output:
The element pushed is 3
The element pushed is 4
The element poped is 3
The element pushed is 5
The top of the queue is 4
The size of the queue is 2
Time Complexity: O(1 )
Space Complexity: O(2N)
Implement Stack using single Queue
Problem Statement: Implement a Stack using a single Queue.
Note: Stack is a data structure that follows the Last In First Out (LIFO) rule.
Note: Queue is a data structure that follows the First In First Out (FIFO) rule.
Example:
Explanation:
push(): Insert the element in the stack.
pop(): Remove and return the topmost element of the stack.
top(): Return the topmost element of the stack
size(): Return the size of the stackSolution:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Intuition: As we know stack follows last in first out, which means we get the most recently inserted element whenever we remove an element from the stack. But queue follows first in first out, it means we get that element which we inserted in the starting at each deletion, it means if we want to use the queue like a stack we have to arrange elements in the queue such that we get the most recent element at each deletion.
Approach:
- Take a single queue.
- push(x): Push the element in the queue.
- Use a for loop of size()-1, remove element from queue and again push back to the queue, hence the most recent element becomes the most former element and vice versa.
- pop(): remove the element from the queue.
- top(): show the element at the top of the queue.
- size(): size of the current queue.
Repeat step3 at every insertion of the element.
Code:
- Java Code
import java.util.*;
public class tuf {
public static void main(String[] args) {
stack s = new stack();
s.push(3);
s.push(2);
s.push(4);
s.push(1);
System.out.println("Top of the stack: " + s.top());
System.out.println("Size of the stack before removing element: " + s.size());
System.out.println("The deleted element is: " + s.pop());
System.out.println("Top of the stack after removing element: " + s.top());
System.out.println("Size of the stack after removing element: " + s.size());
}
}
class stack {
Queue < Integer > q = new LinkedList < > ();
void push(int x) {
q.add(x);
for (int i = 0; i < q.size() - 1; i++) {
q.add(q.remove());
}
}
int pop() {
return q.remove();
}
int top() {
return q.peek();
}
int size() {
return q.size();
}
}Output:
Top of the stack: 1
Size of the stack before removing element: 4
The deleted element is: 1
Top of the stack after removing element: 4
Size of the stack after removing element: 3
Time Complexity: O(N)
Space Complexity: O(N)
- C++ Code
#include<bits/stdc++.h>using namespace std;class Stack {
queue < int > q;
public:
void Push(int x) {
int s = q.size();
q.push(x);
for (int i = 0; i < s; i++) { q.push(q.front());
q.pop();
}
}
int Pop() {
int n = q.front();
q.pop();
return n;
}
int Top() {
return q.front();
}
int Size() {
return q.size();
}
};int main() {
Stack s;
s.Push(3);
s.Push(2);
s.Push(4);
s.Push(1);
cout << "Top of the stack: " << s.Top() << endl;
cout << "Size of the stack before removing element: " << s.Size() << endl;
cout << "The deleted element is: " << s.Pop() << endl;
cout << "Top of the stack after removing element: " << s.Top() << endl;
cout << "Size of the stack after removing element: " << s.Size();}
Output:
Top of the stack: 1
Size of the stack before removing element: 4
The deleted element is: 1
Top of the stack after removing element: 4
Size of the stack after removing element: 3
Time Complexity: O(N)
Space Complexity: O(N)