Questions tagged [queues]
A queue is a First In First Out (FIFO) data structure. Popular uses of queues include buffers and breadth-first graph traversal.
0
votes
0answers
16 views
What kind of list or array would use the least space to implement a queue that will never have more than 10 elements. Why?
I was reading that circular array is fit for queue with few elements but not sure about if it also uses the least space.
0
votes
1answer
49 views
Circular Queue using Dynamic Array
I'm learning data structures from "Fundamentals of Data structures in C" by Sahni . In the topic, Circular Queue using Dynamic Array, the author has mentioned below point,
Let capacity be the ...
1
vote
1answer
67 views
Is Breadth First Search Space Complexity on a Grid different?
Is the Space Complexity O(number_rows + number_cols) for Breadth First Search on a Grid. This is an attempt to show my reasoning:
For example, the flood fill question is described here:
https://www....
1
vote
1answer
33 views
Amortized time complexity for double stack emulated queue
Assume that we have a data type $stack$ which has two operation $push$ and $pop$, both operations' time complexity is $O(1)$ in worst case. The $stack$ also has a property $size$ indicate how many ...
6
votes
2answers
965 views
What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?
I’m trying to understand the time complexity of a queue implemented with a linked list data structure. My book says that we can the implement a queue in O(1) time by:
enqueueing at the back
...
0
votes
0answers
31 views
Data Structure which maintains spacing for similar elements
I want a queue like data structure in which a new element inserted has to be some elements away from a related element.
While reading from this data structure, related elements should only be read ...
1
vote
1answer
47 views
Understanding basic queue and dequeue operations
CLRS gives the following implementation for a queue's enqueue and dequeue operations
...
1
vote
1answer
62 views
Duplicate elements in Queue for BFS Maze Algorithm
I'm fairly new to studying data structures and algorithms.
I've implemented a non-recursive BFS on a 2d "maze array" which seems to work well. It finds the position of 2 in an array of 1s (walls) and ...
1
vote
1answer
51 views
Breadth First Search actually require specifically Queue instead of any other type of Collection?
As far as I know, Breadth-First-Search [BFS] theory traditionally requires a Queue to process a given level of a graph (i.e: wiki seems to assume so).
But does BFS really actually require a Queue, ...
2
votes
1answer
102 views
Circular queue problem
In ciruclar queue the following command statement is very useful to use the determine the unused location. What is its importance? I know that without this line it won't be a circular queue. But how ...
0
votes
0answers
121 views
Find optimal path in BFS and DFS
In UCS it is clear that we find the cheapest cost path. In BFS and DFS we can get the order of output nodes. But How can we find the optimal path in BFS ans DFS in following cases?
3
votes
1answer
89 views
Analysis of the Banana Game
My computer science professor introduced an interesting game in order to get us (his students) more familiar with the Stack and Queue ADTs.
Game Description
The banana game is played with a ...
1
vote
1answer
92 views
Why isn't deque implemented as a dynamic array?
We know that std::vector in C++ is implemented as a dynamic array with specific pattern of reallocation (multiplying capacity by a constant), which allows it to ...
1
vote
0answers
8 views
Is there a special name for a queue that works with groups of elements
I have a data type that accepts and returns byte arrays. However, the input is from a network callback or loading a huge file in piecemeal and the output is CRLF-terminated lines. The internal storage ...
0
votes
1answer
239 views
Using Pascal's Triangle to implement queues and stacks using heaps
I have the following question as homework in an algorithms, analysis and data structures class:
And here's an answer I wrote up:
A queue is a first-in-first-out data structure. A heap is a data ...
1
vote
1answer
1k views
Size of Circular Queue [closed]
I am Implementing a Queue using circular arrays in C language .The Implementation uses one empty position to indicate that the queue is full.That is if the rear is two position behind front. The ...
0
votes
0answers
841 views
stack vs queue efficiency
Is there any literature / research on the average size efficiency of stacks vs queues? I asked because I was recently working on a problem where, if using a queue, the size quickly blew up and the ...
0
votes
0answers
24 views
Modelling a queue to a resource pool (children queueing for balls)
I want to develop an algorithm to serve the queue of children queueing to a basket full of balls of different colour, where each ball can be painted within a known time any colour (of several colours ...
19
votes
1answer
4k views
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?
I'm looking for a data structure that will push its oldest/last element out if a new element is inserted. For example, let D represent the structure. ...
1
vote
2answers
1k views
What's the advantage of two pointers linked list implementation of Queue versus one pointer circular list
Princeton Algorithms course shows the implementation of Queue using linked list and two pointers - head and tail. I've ...
0
votes
2answers
510 views
Why is average waiting time is the same for FIFO and LIFO
I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about FIFO and LIFO containers:
Support retrieval in first in, first out (FIFO) order. This is surely
...
-3
votes
1answer
86 views
Data Structure example
Name a data structure that you could use to implement a queue such that all of the standard queue operations are O(1). If you are thinking of a data structure based on Python's built in list, you need ...
0
votes
1answer
28 views
Preventing multiple threads from racing on a queue while not wastefully polling its size
I have a queue with 50 ints in it, and I have 3 threads that want to race at the queue to print the values in it, with a 2 second delay before trying to get the next int.
The queue is not thread safe,...
5
votes
3answers
271 views
Assigning a unique representation to equivalent circular queues
First, a few vague definitions:
Circular queues (or circular buffers) are data structures like normal queues but with their ends connected together (forming a "circle").
wikipedia
Let's say that 2 ...
0
votes
1answer
454 views
Can a queue automaton recognize palindromes?
Consider the language of even-length palindromes $L = \{ WW^R \mid W \in \{0,1\}^* \}$. This language is surely context free and I need an NPDA to recognize it.
But, what if we replace the stack with ...
0
votes
1answer
97 views
Queue implemented using stacks
I have this problem I'm trying to solve: Implement a queue with a constant number of stacks so that each queue operation takes a constant (worst-case) number of stack operations.
I don't want ...
0
votes
1answer
645 views
Queue, moving the element at the tail to the head
Suppose I have a queue where I pull from left and push to the right, and suppose I have the contents in the queue as $a b c @ d e$ (from left to right, left is head, right is tail).
Is there a simple ...
1
vote
3answers
320 views
Using Queues for a Stack and Stacks for a Queue
I was asked a question on how to use a pair of Queues to create a Stack and how to use a pair of Stacks to create a Queue. Any thoughts on how I would do this? Right now I don't even know where to ...
