Hot answers tagged

44 votes
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 ...
user avatar
  • 70.9k
17 votes

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 ...
user avatar
  • 315
11 votes
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 ...
user avatar
  • 141k
9 votes

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 ...
user avatar
  • 463
5 votes
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 ...
user avatar
4 votes

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, ...
user avatar
4 votes
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 ...
user avatar
4 votes
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 ...
user avatar
  • 141k
3 votes

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 ...
user avatar
  • 293
3 votes
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 ...
user avatar
  • 58
3 votes
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 ...
user avatar
  • 500
3 votes
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 ...
user avatar
3 votes
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 ...
user avatar
  • 386
3 votes

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.
user avatar
  • 9,325
3 votes
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 ...
user avatar
  • 141k
2 votes

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 ...
user avatar
2 votes
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. ...
user avatar
  • 4,371
2 votes

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, ...
user avatar
  • 27.6k
2 votes

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 "...
user avatar
  • 25.2k
2 votes
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' ...
user avatar
  • 183
2 votes

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 ...
user avatar
  • 141k
2 votes
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 ...
user avatar
  • 34.1k
2 votes
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. ...
user avatar
2 votes

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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar

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