queue

Definition :- A queue is a collection of same type of entities, which ensures that all entities in collection will have a sequential storage structure that permits access only at the two ends of the sequence. We refer to the ends of the sequence as the front and rear. The first element in queue have the position as front and value or pointer or front changes according to the solution of the given problem. [Read More]

Problem A device boots with an empty FIFO queue. In the first 400 ns period after startup, and in each subsequent 400 ns period, a maximum of 80 words will be written to the queue. Each write takes 4 ns. A worker thread requires 3 ns to read a word, and 2 ns to process it before reading the next word. What is the shortest depth of the FIFO such that no data is lost? [Read More]

Problem - Implement a stack using a queue Solution Method 1 - Implement a stack using 2 queues We have already discussed the problems here. Method 2 - Implement a stack using a single queue Here are the operations(note that push operation is expensive) push: enqueue new element. If n is the number of elements in the queue, then remove and insert element n-1 times. pop: dequeue push 1 front +----+----+----+----+----+----+ | 1 | | | | | | insert 1 +----+----+----+----+----+----+ push2 front +----+----+----+----+----+----+ | 1 | 2 | | | | | insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | 2 | 1 | | | | remove and insert 1 +----+----+----+----+----+----+ insert 3 front +----+----+----+----+----+----+ | | 2 | 1 | 3 | | | insert 3 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | 1 | 3 | 2 | | remove and insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | | 3 | 2 | 1 | remove and insert 1 +----+----+----+----+----+----+ Code: [Read More]

Problem : Implement a stack using 2 queues and standard operations (enqueue, dequeue, isempty, size) Solution A similar problem has been blogged here, where we implement a queue using 2 stacks. There should be TWO versions of the solution. Version A: The stack should be efficient when pushing an item. Version B: The stack should be efficient when popping an item. Method 1 - When push is efficient and pop is costly [Read More]

Problem Statement Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Example: The array is [1 3 -1 -3 5 3 6 7], and w is 3. Window position Max \--------------- ----- $1 3 -1$ -3 5 3 6 7 3 1 $3 -1 -3$ 5 3 6 7 3 1 3 $-1 -3 5$ 3 6 7 5 1 3 -1 $-3 5 3$ 6 7 5 1 3 -1 -3 $5 3 6$ 7 6 1 3 -1 -3 5 $3 6 7$ 7 Input: A long array A[], and a window width w [Read More]

Algorithm Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and  then visit i.e. mark the vertex as visited and process all of v’s neighbors.  Now that we’ve visited and processed all of v’s neighbors,  we need to visit and process all of v’s neighbors neighbors Pseudocode BFS(graph G, vertex s) $all nodes initially unexplored$ \-mark s as explored let Q = queue data structure, initialized with s while (Q not empty) remove the first node of Q, call it v for each edge (v, w): if w is unexplored mark w as explored add w to Q (at the end) We visit each node only once and each edge at most twice (for edge(v, w), we might encounter it when we’re at node v and at node w). [Read More]

What is priority queue? A data structure for maintaining items or elements in a queue of priorities, which is usually implemented using an array. A queue of this nature helps to insert every item with an assigned priority and these inserted items could be deleted if required. Minimum number of queues needed to implement the priority queue? Two. One queue is used for actual storing of data and another for storing priorities. [Read More]

Algorithm Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and  then visit i.e. mark the vertex as visited and process all of v’s neighbors.  Now that we’ve visited and processed all of v’s neighbors,  we need to visit and process all of v’s neighbors neighbors Example So consider the tree: [Read More]

You can implement a stack with O(1) pop(), push() and get_min(): just store the current minimum together with each element. So, for example, the stack [4,2,5,1] (1 on top) becomes [(4,4), (2,2), (5,2), (1,1)]. See here for the full implementation. Then you can use two stacks to implement the queue. Push to one stack, pop from another one; if the second stack is empty during the pop, move all elements from the first stack to the second one. [Read More]

Problem Implement a Queue using two stacks. Solution Logic :  We’ll implement a FIFO queue using two stacks.Lets call the stacks Instack and Outstack. Enqueue: An element is inserted in the queue by pushing it into the Instack.  ** Dequeue:** An element is extracted from the queue by popping it from the Outstack.  If the Outstack is empty then all elements currently in Instack are transferred to Outstack but in the reverse order. [Read More]