If queue Q2 is not empty then transfer n-1 elements from Q2 to Q1 and then, DeQueue the last element of Q2 and return it.If queue Q1 is not empty then transfer n-1 elements from Q1 to Q2 and then, DeQueue the last element of Q1 and return it.Pop Operation: Transfer n-1 elements to other queue and delete last from queue for performing pop operation. If Q1 is empty then Enqueue the element in it. Check whether queue Q1 is empty or not.Whichever queue is not empty, insert the element in it. We make sure that one queue is empty always. Let S1 and S2 be the two Stacks to be used in the implementation of queues. #'spin' the queues until q1 is ready to pop the right value. Q1.enque(item) #just stick it in the first queue. Q2= queue #only contains one item at most. The only way to make this faster is to not to use queues in the first place. You can prove this algorithm cannot be written faster than N by noting that the information about the last element in a queue is only available through knowing the size of the queue, and that you must destroy data to get to that element, hence the 2nd queue. The algorithm where lists are traded back and fourth may be better,Īs a size calculation is not needed, although you still need to loop and compare with empty. Seems that all algorithms that come immediately to mind have N complexity, where N is the size of the list: whether you choose to do work on the 'pop' or do work on the 'push' Here's my answer - where the 'pop' is inefficient. StackImplUsingQueues s1 = new StackImplUsingQueues()
("The stack is empty, nothing to return") Int old_count = queue_get_element_count (q), i Sample implementation: int stack_pop (queue_data *q) If n is the number of elements in the queue, then remove and insert element n-1 times.
This would be version B, for version A you just reverse the process by dequeuing the elements into the second queue except for the last one. With this way the latest is always at the front of the queue. The easiest (and maybe only) way of doing this is by pushing new elements into the empty queue, and then dequeuing the other and enqeuing into the previously empty queue.
0 kommentar(er)
