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 ...
- 72k
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 ...
- 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 ...
D.W.♦
- 156k
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 ...
- 463
6
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 ...
- 275k
5
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 ...
- 81.4k
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, ...
- 310
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 ...
D.W.♦
- 156k
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 ...
- 443
3
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.
...
- 53
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 ...
- 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 ...
- 520
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 ...
- 275k
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 ...
- 448
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.
- 9,425
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 ...
D.W.♦
- 156k
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 ...
- 9,037
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. ...
- 4,431
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, ...
- 29.8k
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 "...
- 28.3k
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' ...
- 313
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 ...
D.W.♦
- 156k
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 ...
- 38.6k
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 ...
- 376
2
votes
Choice of data structure to contain last 5 minutes of long continuous data stream
The data structure you are looking for is double-ended queue (deque). It is basically what you have imagined, with the extra ease of operations on the front.
Deque has been implemented in many ...
- 38.6k
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 ...
- 38.6k
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 ...
- 81.4k
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,293
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, ...
- 275k
Only top scored, non community-wiki answers of a minimum length are eligible