# Tag Info

Accepted

### Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted?

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 ...
• 70.9k

### What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?

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 ...
• 315
Accepted

### Assigning a unique representation to equivalent circular queues

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 ...
• 141k

### Can a queue automaton recognize palindromes?

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 ...
• 463
Accepted

### Circular queue problem

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 ...
• 270k

### Assigning a unique representation to equivalent circular queues

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, ...
• 320
Accepted

### Breadth First Search actually require specifically Queue instead of any other type of Collection?

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 ...
• 80.2k
Accepted

### Is Breadth First Search Space Complexity on a Grid different?

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 ...
• 141k

### What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?

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 ...
• 293
Accepted

### Category theory structures to describe topics and queues

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 ...
• 58
Accepted

### Understanding basic queue and dequeue operations

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 ...
• 500
Accepted

### Analysis of the Banana Game

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 ...
• 270k
Accepted

### Why isn't deque implemented as a dynamic array?

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 ...
• 386

### Assigning a unique representation to equivalent circular queues

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.
• 9,325
Accepted

### Designing a Queue that efficiently tracks position

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 ...
• 141k

### Queue implemented using stacks

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 ...
• 8,857
Accepted

### What's the advantage of two pointers linked list implementation of Queue versus one pointer circular list

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. ...
• 4,371

### Using Pascal's Triangle to implement queues and stacks using heaps

I assume that the data stuctures given are abstract. They can only be updated using their interface operations. A (fifo) queue has indeed init, ...
• 27.6k

### Preventing multiple threads from racing on a queue while not wastefully polling its size

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 "...
• 25.2k
Accepted

### Why is average waiting time is the same for FIFO and LIFO

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' ...
• 183

### Duplicate elements in Queue for BFS Maze Algorithm

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 ...
• 141k
Accepted

### Monotonic queues recurrence relation

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 ...
• 34.1k
Accepted

### Why do we do topological sorting to find shortest or longest path in weighted DAG?

By using this algorithm the expected time complexity would not be O(V+E) as we have to visit an edge multiple times. ...

### Queue for two types using 2 queues?

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 ...
• 346
1 vote
Accepted

### Queue FIFO search speed up through the change of visited array?

Suppose 3 rooms each of which contains number 6 have been visited before any room the product of whose coordinates is 6 has been visited. In the first version of your code, every room of the second ...
• 34.1k
1 vote

### Why can't we replace Dijkstra's priority queue with a regular queue?

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 ...
• 80.2k
1 vote

### Circular Queue using Dynamic Array

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 ...
• 1,243
1 vote
Accepted

### Amortized time complexity for double stack emulated queue

In the remove operation, every iteration of the while loop pops an element from stack_push, ...
• 270k
1 vote

### Data Structure example

Have a look at this post here. Data structure with search, insert and delete in amortised time $O(1)$? To summarise, it is not possible to have all operations in constant time. If usage of parallelism ...

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