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

|

516 Discussions

|

  • saisasikiran2005
     + 0 comments

    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;
}

  • Shahriarcodes8
     + 0 comments

    python solution:

    query =[]
number_of_queries = int(input())
for q in range(number_of_queries):
    operation = input().split()
    if len(operation) == 2:
        query.append(operation[1])
    elif len(operation) == 1 and operation[0] != '3':
        query.remove(query[0])
    elif operation[0] == '3':
        print(query[0])

  • murad_jmv
     + 0 comments

    Optimal pseudocode, if you resolved it but couple tests giving timout exception then, rewrite this to your preffered programming language:

    enQStack = new Stack()
deQStack = new Stack()

enqueue(num):
	# push all new elements to enqueue stack O(1)
	enQStack.push(num)

dequeue():
	# if dequeue stack has elements pop from it O(1)
	# else fill dequeue stack with elements from enqueue stack O(n), then pop from it
	if deQStack is empty:
		fillDeQStack()
	deQStack.pop()

peek():
	# if dequeue stack has elements peek from it O(1)
	# else fill dequeue stack with elements from enqueue stack O(n), then peek from it
	if deQStack is empty:
		fillDeQStack()
	deQStack.peek()

fillDeQStack():
	# fill dequeue stack with elements from enqueue stack O(n), dequeue = reversed enqueue
	while enQStack is not empty:
		deQStack.push(enQStack.pop())

  • dinothedinosaur1
     + 0 comments

    Python 3 solution:

    queue = []

number_of_queries = int(input())

for _ in range(number_of_queries):
    query_and_data = input()
    query_and_data_split = query_and_data.split()
    if len(query_and_data_split) == 2:
        queue += [int(query_and_data_split[1])]
    elif int(query_and_data_split[0]) == 2:
        queue = queue[1:]
    elif int(query_and_data_split[0]) == 3:
        print(queue[0])