goglturtle.blogg.se - Linked list stack implememntation using two queues 261

#Linked list stack implememntation using two queues 261 full
#Linked list stack implememntation using two queues 261 code

Solution: Maintain a queue of size n, and as the numbers keep on coming, keeping on pushing them to queue until queue is full. Think about it before looking at the solution. At any instant you need to output last n numbers which appeared in the stream. Queue implementation using Stacks Adhoc Problem 1

#Linked list stack implememntation using two queues 261 full

Click on the link below to see the full working code: We are just using the S2 as a supportive stack to preserve the order of elements present in S1. keep on doing the 4th step till S2 is empty.keep on popping from S2 and push the corresponding element to S1.Now our target element is the top element of S2, so pop() it.keep on popping from S1 and push the corresponding element to S2.Now when a push() happens we will insert the element into S1 and whenever a pop() operation happens, then we will follow the following steps: So we will try to achieve FIFO by the use of two stacks. Stack implementation using Queues Queue implementation using Stacks

#Linked list stack implememntation using two queues 261 code

The last two steps are just to transfer elements from Q2 to Q1.įollowing is the C++ code for the above(here I will be using STL Queues): Notice one thing here: we are using Q2 as supporting Queue (just to store popped elements from Q1). The above five steps are needed to be done, for each pop operation.

Keep on doing that as long as Q2 is not empty.

Now again keeping on popping from Q2 and pushing it to Q1.

while popping check if Q1 is empty, if its empty, the last popped element is our output.

keep on popping from the Q1 and pushing the popped element to Q2.

Now lets say a pop() query comes, then follow the following steps: keep on pushing the elements to Q1 as long as push() requests are coming. Now say an push() request comes, then we will push that element to Q1 i.e. We will be doing this by using two Queues.

Now our target is to implement push() and pop() using Queues. Solution: We know that Stack follows LIFO property. So once they get into loop(if the loop exist) they will certainly meet at some point and if they don’t meet it means that there is no loop in the linked list.īrainStorm Will the above logic work if the other pointer speed is 3x,4x… times the first one? Stack implementation using Queues

Consider two pointers moving in the linked list and one is moving at twice the speed of the other. This idea we will use here to detect a loop in the linked list. Notice one thing- faster runner will cross the slower one at some point. Now, consider both the athletes are running at different speeds i.e. Solution The underlying idea which we will use here is that - Consider a circular track in where two atheletes are running.

Output yes/no if a loop is present in the linked list.

Insert a node at the last node and configure it accordinglyįor the full working code, see the following link:Ĭlone Linked List with random ptr Detect loop in Linked Listĭetect whether a loop is present in linked list or not.

NewNode->randomPtr = oldNode->randomPtr->next

First of all, we will insert nodes between all the two nodes of the given linked list such that.

To solve this problem, lets see at following steps: Solution: The solution would here be trivial if the given linked list didn’t have the random pointer.

We just need to connect current and newHead each timeĬlone a linked list with next and a random pointer.

Now for each iteration of the loop, we will be reversing only current and previous nodes and this will result into breaking of linked list into two linked lists whose one head is current and other head is newHead after each iteration of the while loop.

we will maintain 3 pointers namely- previous, current and newHead such that current = previous->next and newHead = current->next initially.

if there is two nodes then reverse those nodes and return the newHead.

if there is single node or no node then return that node.

Solution: Following is the algorithm: (3 pointers method)

Output: head of the reverse linked list.

Input: head of the linked list to be reversed.

After having finished with the traversal, check if the stack is empty or not - if its empty - the given sequence is valid, if not empty - its invalidīracketValidationCode Reverse Linked List.

On encounter with ‘)’ pop from the stack.

Traverse over the string, on encounter with ‘(‘ push it to the stack.Solution: This problem can be solved by using stack. Given a sequence of opening and closing braces, find whether the given sequence is a valid sequence or not.