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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
6 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
228 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
1 vote
1 answer
52 views

Choice of data structure to contain last 5 minutes of long continuous data stream

Let's assume that I am continuously receiving big amount of data. For example, this millisecond I get 100 numbers, next millisecond I get another 500 numbers, after that I might get nothing for a ...
Haldot's user avatar
  • 111
-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
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
3 votes
1 answer
207 views

Designing a Queue that efficiently tracks position

Suppose we want to construct a queue with the following properties: The priority of each member of the queue must be known. For example, for the head node, their priority is 1, for the next node, ...
Newb's user avatar
  • 314
0 votes
1 answer
60 views

Queue for two types using 2 queues?

I'm reading the book Cracking the Code. The answer for this question suggests a solution using timestamps and two separate queues. This is straightforward and involves simply enqueuing into the ...
sprajagopal's user avatar
0 votes
1 answer
37 views

`STACK-FULL` and `QUEUE-FULL` with worst-case $\Theta(1)$

There are two problems in CLRS about implementing stacks and queues with singly linked lists. I know the solutions, I know how STACK-EMPTY and ...
Emad's user avatar
  • 411
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
6 votes
0 answers
869 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
1 vote
1 answer
48 views

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

As I was preparing for the CCC this year, I am quite confused as to why a certain code modification was able to speed up my code for CCC Seniors Problem 2. Here was the C++ source code for my first ...
Aarony Jamesys'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
1 answer
274 views

Is it possible to uniformly shuffle N items into a deque of size N where you can only modify the first or last elements?

I had a question about random shuffling. Given a sorted list, is it possible to design an algorithm to return a uniformly random arrangement of the items in a deque with the following operations: ...
Subhasish Mukherjee's user avatar
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
1 answer
103 views

Monotonic queues recurrence relation

I'm looking at the following explanation of monotonic queues and their applications in problem solving. Monotonic Queue Summary I have a reasonable understanding of this data structure and the ...
DMW's user avatar
  • 15
0 votes
0 answers
638 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
2 answers
998 views

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

I was wondering why do we need to do the topological sort before performing relaxing of edges. Wouldn't it'd be better if we do : if starting vertex is "s" ...
vivek gupta's user avatar
1 vote
0 answers
77 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
1 answer
190 views

Category theory structures to describe topics and queues

What are the category theory structures describing queues and topics? By queues and topics I mean the ones described in systems like Apache Kafka, AcriveMQ or Java Messaging Service. Where I can find ...
Vitaly Olegovitch'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
2 votes
2 answers
685 views

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

I am confused why we can't simply use a normal queue instead of a priority queue for Dijkstra's. I agree that you can find the shortest path in fewer iterations of the while loop using a priority ...
A. Akella's user avatar
0 votes
2 answers
4k 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 ...
Surya Teja Vemparala's user avatar
4 votes
1 answer
3k 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....
Meem's user avatar
  • 43
1 vote
1 answer
887 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 ...
cgcgbcbc's user avatar
  • 123
9 votes
2 answers
73k 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 ...
Appe's user avatar
  • 91
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
3 votes
1 answer
591 views

Understanding basic queue and dequeue operations

CLRS gives the following implementation for a queue's enqueue and dequeue operations ...
Curious's user avatar
  • 273
1 vote
1 answer
971 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 ...
Robin Andrews's user avatar
3 votes
1 answer
433 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, ...
cellepo's user avatar
  • 150
2 votes
1 answer
262 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 ...
Kalana Mihiranga's user avatar
3 votes
1 answer
174 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 ...
antonky's user avatar
  • 133
1 vote
1 answer
548 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 ...
Tigran Saluev'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
0 votes
1 answer
506 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 ...
StudentsTea's user avatar
1 vote
1 answer
4k 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 ...
Pradeep Kumar'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 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
21 votes
1 answer
5k 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. ...
Greg M's user avatar
  • 313
1 vote
2 answers
3k 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 ...
Max Koretskyi's user avatar
0 votes
2 answers
1k 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 ...
Max Koretskyi's user avatar
-2 votes
1 answer
98 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 ...
user avatar
0 votes
1 answer
32 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,...
Dmytro's user avatar
  • 193
5 votes
3 answers
300 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 ...
A. Sallai's user avatar
  • 243
0 votes
1 answer
927 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 ...
Garrick's user avatar
  • 462