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

|

237 Discussions

|

  • robbie_chambers1
     + 0 comments

    I am quite new to coding so I just used the knowledge on linked lists i gained from the previous exercise. This passed all the tests but could someone help me diagnose the complexity of my solution:

    # Enter your code here. Read input from STDIN. Print output to STDOUT
class LinkedListNode():
    data: int = None
    next: 'LinkedListNode' = None


class Queue():
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, x):
        final_element = LinkedListNode()
        final_element.data = x
        # Handle empty queue case
        if not self.head:
            self.head = final_element
            if not self.tail:
                self.tail = final_element
        else:
            self.tail.next = final_element
            self.tail = self.tail.next

    def dequeue(self):
        # Handle empty queue case
        if not self.head:
            return None
        dequeue_value = self.head.data
        self.head = self.head.next
        # If queue is empty, remove tail
        if self.head is None:
            self.tail = None
        return dequeue_value

    def handle_query(self, query):
        query_type = query[0]
        # Enqueue query
        if query_type == 1:
            x = query[1]
            self.enqueue(x)
        # Dequeue query
        elif query_type == 2:
            return self.dequeue()
        # Print query
        elif query_type == 3:
            if self.head.data:
                print(self.head.data)
            else:
                print(None)

if __name__ == "__main__":
    q = int(input())
    queue = Queue()
    for _ in range(q):
        query = list(map(int, input().split()))
        queue.handle_query(query)

  • leviatan_89
     + 0 comments

    There is no Go template...

  • evansadamd
     + 0 comments

    You could have two stacks: stack1 and stack2. You could then dequeue everything in stack1 into stack2 for operations 2 and 3, and then requeue them back into stack1 for further elements. This will not have a good time complexity.

    Consider: We enqueue elements into stack1:

    stack1 = [3,2,1] stack2=[] (empty)

    We get a dequeue/peek operation. We must unstack everything into stack2. Everything now looks like this:

    stack1 = [] stack2 = [1,2,3]

    We read/pop 1.

    Do we really need to put everything back into stack1?

    If we only unstack stack1 when stack2 is empty. We can keep adding new elements to stack1 without touching stack2. Any remaining elements in stack2 at this point are in the proper FIFO order as of when it was last updated. Anything added to stack1 at this point would need to wait for stack2's elements to be dequeued anyways.

    Consider:

    Enqueue 4: stack1 = [4] stack2 = [2,3]

    Because stack2 still has elements, if we get a peek/pop operation, we will next read/pop 2.

    You can think of your total structure like so: [stack2][stack1]: [2,3][x...4] where (x..). represents potential other elements put on stack1.

  • samarthgaba27
     + 1 comment

    YES I CHEATED but it was fun to see it passing all test cases

    arr = []
for i in range(int(input())):
    query = input().split(" ")
    if query[0] == "1":
        arr.append(query[1])
    elif query[0] == "2":
        arr.pop(0)
    else:
        print(arr[0])

  • udemezuu
     + 0 comments

    Here is my c++ solution

    The idea behind moving items from stack 1 to stack 2 only when stack 2 is empty is because any item pushed unto stack 1 is the latest.

    When stack 2 is empty, and stack 1 is inverted unto stack 2 the oldest item is at the top of stack 2. Stack 2 keeps the order of oldest to newer from top to bottom.

    That way any item newer than bottom of stack 2 will be placed on stack 1.

    struct Queue {
   stack<long> s1, s2;

    // Enqueue an item to the queue
    void enQueue(long x)
    {

        // Push item into the first stack
        s1.push(x);
    }

    // Dequeue an item from the queue
    void deQueue()
    {

        int output ;
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        s2.pop();

    }

    int printFront(){
        long x = 0;
        if (s2.empty()){
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
       
        x = s2.top();
        
        return x;
    }
};

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
        Queue q;
    long input;
     int numQueries;
    long elementEnqueue;
    long printedOut;
    string outString;
    cin >> numQueries;
   vector<long>outputs;

    for(int i = 0; i<numQueries; i++){

        cin >> input;

        if(input == 1){
            cin >> elementEnqueue;
            q.enQueue(elementEnqueue);
        }
        if(input == 2){
             q.deQueue();
        }
        if(input == 3){
           printedOut = q.printFront();
           outputs.push_back(printedOut);
        }
    }

    for(int i = 0; i < outputs.size(); i++){
        cout << outputs[i] << endl;
    }
   

    return 0;
}