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.

21 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6 votes
0 answers
866 views

How to sort a queue using a temporary stack?

Suppose we have N natural numbers in a queue. ex queue = [3, 14, 1, 20] and an empty stack We are allowed to make only two actions: Action "x": Dequeue an element from the queue and push it ...
entropyfever's user avatar
2 votes
0 answers
48 views

Equivalence of input-restricted and output-restricted deques

There is a question in Art of Computer Programming by Knuth which needs us to prove that input-restricted deques and output-restricted deques can form the same number of (and possibly individually ...
sonu's user avatar
  • 121
1 vote
0 answers
22 views

How can there be an enqueue event outside the function range of enqueue events?

I'm trying to understand Figure 1 in this theoretical description for queues: https://www.cs.bgu.ac.il/~abraham/courses/Concurrency14/2(Logic)/3.Qexample.pdf Key excerpts from the PDF: I grasp ...
Paul's user avatar
  • 113
1 vote
0 answers
100 views

Is there a known way to make an efficient, compact, and fully persistent stack or queue?

In the world of mutable/ephemeral data structures and imperative programming languages, one of the classic ways to implement a stack or queue is to use array doubling: use mutation to fill up or empty ...
dfeuer's user avatar
  • 409
1 vote
0 answers
76 views

How many possibilities of merging two queues?

Say there're two queues of numbered items of different kinds (e.g. color), now we need to merge them into one queue so that each item maintains its order in the original queue, regardless of its kind. ...
mzoz's user avatar
  • 113
1 vote
0 answers
65 views

n thread consensus queues

Its generally agreed that wait free queues have a consensus number of 2. But what about this following code for a consensus protocol for a queue. How is it that this does not go against the idea above?...
muha's user avatar
  • 11
1 vote
0 answers
27 views

How would the queueing delay in an LCFS queue change for different queue sizes?

Here we differentiate between the informative and non-informative packets. In FCFS, all packets are informative as they are sent in sequence, and so queueing delay rises with queue size. But i LCFS, ...
user3656142's user avatar
1 vote
0 answers
13 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 ...
CTMacUser's user avatar
  • 121
1 vote
0 answers
73 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 ...
Sergey Mikhanov's user avatar
0 votes
0 answers
2 views

Papers on durable queue design with multiple distributed workers

What's the state of the art for a durable, distributed worker queue on top of a consistent, transactional database (such as SQL)? More concretely, the problem I'm trying to investigate is the ...
Miguel Ping's user avatar
0 votes
2 answers
219 views

What is the order of items being popped and pushed from a stack?

...
BeanieBaby's user avatar
0 votes
0 answers
58 views

Queue system with 2 parallel servers that works one at a time. Mean waiting time?

Consider a queueing system where customers arrive according to a Poisson process with rate $\lambda$, but the service facility consists of two parallel servers. A customer upon entry into the service ...
Alex_DeLarge's user avatar
0 votes
0 answers
14 views

M/G/1 (?) with server vacations

I'm asking your help to solve this: Consider a time-division multiplexor that multiplexes $30$ input packet streams onto a outgoing link with a slot time of $4 \mu s$. Assume that the packet arrival ...
Alex_DeLarge's user avatar
0 votes
0 answers
39 views

M/M/1 priority queueing system (?), an exercise

can someone help me please solving this? Consider a switch with two input links and one outgoing transmission link. Data packets arrive at the first input link according to a Poisson process with mean ...
Alex_DeLarge's user avatar
0 votes
0 answers
51 views

Can anyone explain how a circular buffer array works?

I'm currently learning about Data Structures and Abstractions and one particular problem has been very confusing to me, and that is the concept of Circular ArrayDeque. In particular, how can we add or ...
Droid's user avatar
  • 101
0 votes
0 answers
37 views

Are arrays “more abstract” than stacks or queues?

It seems to me that an array can be used as a stack or a queue and for various other things. In my mind this makes an array a higher order abstraction compared to those other two. Is this an ...
John Vandivier's user avatar
0 votes
0 answers
123 views

Create a potential function for an abstract queue data structure to show constant amortized-time complexity

Consider a variation of a Queue called MaxQueue, Q, that has the following operations: dequeue(Q): removes and returns the first element of Q enqueue(Q, s): Appends the integer s to the end of Q ...
felicef885's user avatar
0 votes
0 answers
636 views

Monotone priority queues

I'm a little confused about how monotone priority queues work. As far as I understand: A queue is a FIFO data structure A priority queue is a queue where the current element of highest (or lowest) ...
Amelio Vazquez-Reina's user avatar
0 votes
0 answers
35 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 ...
Saurabh's user avatar
0 votes
0 answers
2k 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 ...
dashnick's user avatar
  • 101
-1 votes
1 answer
189 views

Algorithmic Complexity of Enqueue and Dequeue of a Special Queue

The Canteen Queue Problem There is a common canteen for K hostels. Each hostel (co-ed) has some $N_1,N_2,...,N_K$ students. These students line up to pick up their trays in the common canteen, in a ...
Kunind Sahu's user avatar