We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Queues
  4. Queue using Two Stacks
  5. Discussions

Queue using Two Stacks

Sort by

recency

|

519 Discussions

|

  • btmakusha
     + 0 comments

    My solution:

    import java.io.*;
import java.util.*;

public class Solution {
    static Stack<Integer> stack1 = new Stack<>();
    static Stack<Integer> stack2 = new Stack<>();
    
    public static void enqueue(int val) {
        stack1.push(val);
    }
    
    public static int dequeue() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty())
                stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
    
    public static int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty())
                stack2.push(stack1.pop());
        }
        return stack2.peek();
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int q = Integer.parseInt(scan.nextLine().trim());
                
        for (int i = 0; i < q; i++) {
            String[] line = scan.nextLine().trim().split(" ");
            int op = Integer.parseInt(line[0]);
            
            switch (op) {
                case 1 -> enqueue(Integer.parseInt(line[1]));
                case 2 -> dequeue();
                case 3 -> System.out.println(peek());
            }
        }
			}
        
        scan.close();
    }
}

  • goric_leonor
     + 0 comments

    If, despite properly adhering to the specifications, the test cases are timing out, one viable solution would be to stack stacks - push items to a buffer stack and then utilize the submitted queue solution to hold filled stacks. It certainly interprets the requirements in a lenient way, but relies on stacks only; and if you interpret the buffer stack as not counting toward the overall stack limit then it suits them perfectly. ;)

    public class Quee<T>
{
    private Stack<T> incomingStack = new Stack<T>();
    private Que<Stack<T>> outgoingQue = new Que<Stack<T>>();

    public void Enqueue(T item)
    {        
        incomingStack.Push(item);
    }
    
    public T? Dequeue()
    {
        var outgoing = GetOutgoing();
        
        if (!outgoing.TryPop(out var itemOut))
        {
            outgoingQue.Dequeue();
            return default;
        }
        
        return itemOut;
    }
    
    public T? Peek()
    {
        var outgoing = GetOutgoing();
        
        if (!outgoing.TryPeek(out var itemOut))
        {
            outgoingQue.Dequeue();
            return default;
        }
        
        return itemOut;
    }
    
    private Stack<T> GetOutgoing()
    {
        var outgoing = outgoingQue.Peek();
        if (outgoing is null || !outgoing.TryPeek(out var _))
        {
            if (outgoing is not null)
                outgoingQue.Dequeue();

            outgoing = new Stack<T>(incomingStack.Count);
            
            while (incomingStack.TryPop(out var item))
                outgoing.Push(item);
            outgoingQue.Enqueue(outgoing);
        }
        
        return outgoing;
    }
}

public class Que<T>
{
    private bool outgoing = false;
    private Stack<T> incomingStack = new Stack<T>();
    private Stack<T> outgoingStack = new Stack<T>();

    public void Enqueue(T item)
    {
        if (outgoing)
            SwitchToIncoming();
        
        incomingStack.Push(item);
    }
    
    public T? Dequeue()
    {
        if (!outgoing)
            SwitchToOutgoing();
        
        return outgoingStack.TryPop(out var item) ? item : default; 
    }
    
    public T? Peek()
    {
        if (!outgoing)
            SwitchToOutgoing();
        
        return outgoingStack.TryPeek(out var item) ? item : default; 

    }
    
    private void SwitchToOutgoing()
    {
        while(incomingStack.TryPop(out var val))
        {
            outgoingStack.Push(val);
        }
        
        outgoing = true;
    }
    
    private void SwitchToIncoming()
    {
        while(outgoingStack.TryPop(out var val))
        {
            incomingStack.Push(val);
        }
        
        outgoing = false;
    }
}

  • bonnemai
     + 0 comments

    Really using two stacks: 

    n=int(input())
stack_in=[]
stack_out=[]

def transfer():
    while stack_in:
        stack_out.append(stack_in.pop())

for _ in range(n):
    arr=input().split(' ')
    if arr[0]=='1':
        stack_in.append(int(arr[1]))        
    elif arr[0]=='2':
        if not stack_out: 
            transfer()
        if stack_out: 
            stack_out.pop()
    else:
        if not stack_out: 
            transfer()
        if stack_out: 
            print(stack_out[-1])

  • saisasikiran2005
     + 1 comment

    java solution

    import java.io.; import java.util.;

    public class Solution {

    public static void main(String[] args) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    Scanner s=new Scanner(System.in);
    int n=s.nextInt();
    s.nextLine();
    Queue<Integer> q=new LinkedList<>();
    while(n-->0){
        String str=s.nextLine();
        if(str.startsWith("1")){
            int val= Integer.parseInt(str.split(" ")[1]);
            q.add(val);
        }
        else if(str.equals("2")){
          if(!q.isEmpty())  q.remove();
        }
       else {
        if(!q.isEmpty())

        System.out.println(q.peek());
       }
    }
}

    }

  • pradeep_tarakar
     + 0 comments

    Approach: * take 2 stacks one for enque and another for deque. * if operation is enqueue simply push to first stack * if operation is dequeue - check if there are elements in 2nd stack if not copy all elements from 1st stack and pop the top. Otherwise simply pop 2nd stack top * if operation is front - follow above step instead of popping print the top.

    Gist is: stack 2 will have a top element to pop or print. We only copy stack 1 elements into stack 2 when it is empty.

    int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    
    stack<int> st1; // for enqueue
    stack<int> st2; // for dequeue
    int num_of_queries = 0;
    
    cin >> num_of_queries;
    
    for(int i=0; i < num_of_queries; i++){
        int op;
        cin >> op;
        
        if(op == 1){
            int data;
            cin >> data;
            st1.push(data);
            continue;
        }
        if(op == 2){
           if(!st2.empty()){
             st2.pop();
           }else{
            while(!st1.empty()){
                st2.push(st1.top());
                st1.pop();
            }
            st2.pop();
           } 
           continue;
        }
        
        if(op == 3){
            if(!st2.empty()){
                cout << st2.top()<<endl;
            }else{
                while(!st1.empty()){
                    st2.push(st1.top());
                    st1.pop();
                }
                cout << st2.top() <<endl;
            }
        }
    }
    
    return 0;
}