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. Queue using Two Stacks
  2. Discussions

Queue using Two Stacks

Sort by

recency

|

29 Discussions

|

  • jpdunn1970
     + 0 comments

    Java

        public static class QueueUsingTwoStacks<T> {
        private Stack<T> stack1 = new Stack<>();
        private Stack<T> stack2 = new Stack<>();
        
        public void enqueue(T a) {
            stack1.push(a);
        }
        
        public T dequeue() {
            fillStack2IfEmpty();
            return stack2.pop();
        }
        
        public T peek() {
            fillStack2IfEmpty();
            return stack2.peek();
        }
        
        private void fillStack2IfEmpty() {
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
        }
    }

  • kocsis_tamas_ol1
     + 0 comments

    C++ Using a second stack to reverse the stack for poping/displaying first element just gives TLE for many testcases. Seems like problem design issue, editorial explain same logic also.

    Otherwise a vector is obviously faster to at least display the first element, but that wasnt the task I guess. (Ofc pop_front is still o(n))

  • shiaramoon
     + 0 comments

    There is a really easy way to do this if you use an array, but it can be very ineffient for larger queues. Here what I suggest using as a framework for python code in order to actually try out coding with 2 stacks to simulate a proper queue:

    class DblStackQ:
    '''Use self.stack1 to refer to stack1 and self.stack2 to refer to stack 2. Only .pop, .append, and [-1] may be used on self.stack1 and self.stack2. No other lists or arrays may be used.'''
    
    stack1 = []
    stack2 = []
    
    def enqueue(self,x):
        #write code here
    
    def dequeue(self):
        #write code here
    
    def peek(self):
        #write code here
    
    
    
if __name__ == "__main__":
    q = int(input())
    inputs = []
    for i in range(q):
        inputs.append(tuple(map(int, input().split())))
    
    queue = DblStackQ()
    for t in inputs:
        if t[0] == 1:
            queue.enqueue(t[1])
        elif t[0] == 2:
            queue.dequeue()
        elif t[0] == 3:
            print(queue.peek())

  • jimiwills
     + 0 comments

    i don't really understand why it's asking to do it with 2 stacks

    class Solution {
    private static List<int> oneStack = new List<int>();

    static void Main(String[] args) {
        var q = int.Parse(Console.In.ReadLine()!.TrimEnd()); // number of queries
        for(var i=0; i<q; i++){
            var a = Console.In.ReadLine()!.TrimEnd().Split(" ").Select(x => int.Parse(x)).ToArray();
            var t = a[0];
            switch(t){
                case 1:
                    enqueue(a[1]);
                    break;
                case 2:
                    dequeue();
                    break;
                case 3: 
                    print();
                    break;
                default:
                    throw new Exception($"t={t}");
            }
        }
    }

    static void enqueue(int x){
        oneStack.Add(x);
    }

    static void dequeue(){
        oneStack = oneStack.Skip(1).ToList();
    }

    static void print(){
        Console.WriteLine(oneStack.First());
    }
}

  • inq_daniel_eliz1
     + 0 comments

    My answer in Python

    q = int(input())
inpts = []

for i in range(q):
    inpts.append(input())


ans = []

for i in inpts:
    if i[0] == "1":
        j, num = i.split(" ")
        ans.append(int(num))
    elif i[0] == "2":
        ans.pop(0)
    elif i[0] == "3":
        print(ans[0])