# Tag Info

44

Fixed-size queues are often implemented using what some people call circular buffers. If you remove the protection against it being full, you get the desired behaviour. Of course, no actual pushing will happen in the array -- that would be too expensive -- but it will look like it from the outside.

17

Enqueueing You don't need to traverse the entire list to find the new tail, you just need to add a new node where the current tail points to and set that node as the new tail. Pseudocode (assuming that head != null and tail != null): function enqueue(value) { node = new Node(value) // O(1) tail.next = node // O(1) tail = node ...

11

Enumerate all possible rotations of the queue. Take the lexicographically first of them. Use this as your representative. If you want a short index into a hash table, take the hash of that. Then any two equivalent queues will get the same representative / same index. If the queue has $n$ items, implementing this naively takes $O(n^2)$ time. However, it ...

8

The construction of a PDA except with a FIFO instead of a LIFO data structure attached can mimic any single tape TM as follows: it keeps the cell contents in the queue along with two special markers for the end of the tape and for the head of the TM. Every time you make a move, you just go through the entire queue and re-push everything you pop, making ...

5

Suppose that we arrange the numbers $0,\ldots,n-1$ in an oriented cycle. The number which follows $i$ is $i+1$ for $i \neq n-1$, and $0$ for $i=n-1$. We can combine both cases by saying that the number following $i$ is $i+1 \bmod{n}$.

4

This is a variant of the tandem repeats problem. Such a problem can be attacked via (generalized) suffix trees. This problem is strongly related to the lexicographically minimal rotation problem, for which there are fast algorithms different from the below. A more thorough description of the below appears in chapter 7 of Gusfield's "Algorithms on Strings, ...

4

If you can only push (enqueue) or pull (dequeue) from the queue, then your only option is to pull all the elements and re-enter them. If you need such an operation, you can use deque (double-ended queue). See: http://en.wikipedia.org/wiki/Double-ended_queue .

4

It doesn't literally have to be a queue. Anything that ensures that one level is completely explored before moving to the next one would suffice. However, the most natural way to do this is with a queue and any other implementation is going to be harder to describe and/or harder to implement than just "use a queue." As evidence that it's harder to describe, ...

3

The comment in the book apparently assumes that your linked list implementation maintains two pointers, head that points to the first node in the list, and last that points to the last node. With this design, appending to the list is simply: list.last.next = newNode; list.last = newNode; But removing the last node requires finding the 2nd to last node, so ...

3

CLRS defines a queue using an array which wraps around i.e when we no longer can insert/delete in the last position, we move to the first position. From the book, The elements in the queue are in locations head[Q], head [Q] + 1, . . . , tail [Q] - 1, where we "wrap around" in the sense that location 1 immediately follows location n in a circular order. ...

3

It depends what you mean by a "on a grid". If you mean that you are working with the graph of a complete grid, with number_rows * number_cols vertices (one for each grid point) and an edge between every pair of adjacent vertices: Yes, that's correct. The asymptotic time complexity of both is O(number_rows * number_cols), and the asymptotic space ...

3

A data structure Queue is very close to the concept of a List, however a Queue is a First-In-First-Out (FIFO) data structure. The available operations to interact with the List structure then, are limited to enqueue() and dequeue() (it is not a case in fact that a queue can be implemented using a List structure). In the context of Category Theory you might ...

3

Your instructor might have been reading the article Stackable and queueable permutations by Peter G. Doyle, who considers two exercises in Knuth's Art of Computer Programming. The context is that the string in question is a sequence of distinct numbers, and the task is to output them in increasing order (Doyle's article actually discusses the other ...

3

The reason why std::deque is implemented as a sequence of non-contiguous blocks is to guarantee different complexity bounds (and different concrete performance) for operations with regards to std::vector. You already partially said it: changing the capacity of an std::vector requires reallocating the memory and copying the entire content to the new memory. ...

3

Always use minimal lexicographic word to put into your hash. There is a special algorithm for that purpose called Booth's algorithm, which runs in $\mathcal O(n)$ time.

3

One simple data structure is a balanced binary tree, with members stored in the leaves, and augmented so that each internal node also stores the number of leaves under it. Now you can implement all of your operations in $O(\log n)$ time. Operation 1 can be implemented by finding the leaf where the member $m$ resides (either add a pointer to the member ...

2

I believe the question is asking you to implement the queue so that every time you perform a queue operation (enqueue or dequeue) your implementation does O(1) total operations on the stacks used to implement this. For example, an implementation that performed at most 137 total pushes and pops per time that the client calls enqueue or dequeue would satisfy ...

2

You wouldn't have just your queue and your semaphore. You would also have a global atomic variable where "false" means "I can guarantee one hundred percent that there is no data in the queue", and "true" means "There is probably some data in the queue, but maybe not". Any code that modifies the queue would very carefully update the global variable. You ...

2

Maybe an example will help, consider lets say for 3 minutes we add 2 tasks each minute, and we process 1 task a minute. With a FIFO queue the timeline will be: t(0): 'a' and 'b' added: [a, b] - 'a' processed after waiting $0$ - [b] t(1): 'c' and 'd' added: [b, c, d] - 'b' processed after waiting $1$ - [c, d] t(2): 'e' and 'f' added: [c, d, e, f] - 'c' ...

2

If you're not using a circular list, then you must have a pointer to head and tail to achieve $O(1)$ enqueue and dequeue. Furthermore, if it is not a circular list and not a doubly-linked list, then without a pointer to head, we can't enqueue! Some picture might help a little too. Single Linked List with only tail pointer: There's no way to get back to ...

2

I assume that the data stuctures given are abstract. They can only be updated using their interface operations. A (fifo) queue has indeed init, enqueue(item) "at the end", dequeue(item) retrieve "from the beginning" and the test isempty. Upto small personal preferences. I also think that the heap here means the binary heap implementation of the priority ...

2

It is no wonder that you are confused. One characteristic of DP problem is the recurrence relation that combines solutions to subproblems to a solution to larger subproblems. That article presents the following general "recurrence relation". Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i However, because the same A appears on both ...

2

By using this algorithm the expected time complexity would not be O(V+E) as we have to visit an edge multiple times. queue.add(s) while(the queue is not empty) for every adjacent vertex v of u if( dist[v] > dist[u] + weight(u,v) ) dist[v] = dist[u] + weight(u,v) add v to the queue But by using the topological sorting, we get the order ...

2

Your solution seems to have higher time complexity than needed. If you have $n$ dogs and then $n$ cats then dequeuing all cats will cost you $O(n^2)$ as you need to go through dogs first. I'd go with three queues: all animals, dogs, cats. Enqueue: Create an instance of dog/cat, push into all animals queue. Next, push the same instance to the dog/cat queue ...

1

The whole point of Dijkstra is that you visit the nodes in order of their distance from the source. If you use a queue that isn't a priority queue, then you visit the nodes in whatever "random" order the implementation happens to enqueue them.

1

I think the author is just saying the circular list has capacity of $n-1$ where $n$ is the total cells. When the array is doubled there is copying of these $n-1$ elements to new array in addition with shifting of these $n-1$ elements in the worst case, thus making it total $2n-2$ doubling and sliding in the worst case.

1

In the remove operation, every iteration of the while loop pops an element from stack_push, and this dominates the running time of remove. We can charge each such iteration to the insert operation which pushed the very same element to stack_push. This way we deduce that the amortized running time of both operations is $O(1)$. You can formalize the above ...

1

Yes. There is no point having duplicates in the queue, so don't enqueue a position if (a) it has already been visited, or (b) it is already on the queue. What happens if you skip checking whether it is already on the queue? Depending on how the rest of your code works, this could slow down your implementation significantly (it could increase the ...

1

Suppose that the queue consists of elements $Q[a],\ldots,Q[b]$, where $Q = Q[1],\ldots,Q[n]$ is an array of length $n$. If $a \leq b$ then the queue contains $b-a+1$ elements, and if $a > b$ then the queue contains $b-a+1+n$ elements.

Only top voted, non community-wiki answers of a minimum length are eligible