Talk:Queue (abstract data type)

Comment

I would have found a page on circular queues / ring buffers useful. (a queue implemented in an array). Programming in java, there doesn't seem to be a default implementation available, so others might find it useful, esp. with the new java IO model (java.nio.*, java.nio.channel.* etc)

Scheme advocacy?

How is the Scheme implementation O(1)? If I enqueue a bunch of things, then dequeue them one by one, the first call to dequeue will result in a call to (reverse (queue-back Q)) -- which isn't O(1). It might be amortized O(1), but that's very different for many applications.

I wonder if there isn't some Scheme/Lisp pure-functional style advocacy at play here. Purely functionally, it's not terribly easy to do an efficient queue.

Yes, the Scheme implementation is only amortized O(1), and frankly the placement creates unnecessary emphasis on it. I'm moving it. Deco 08:32, 31 January 2006 (UTC)

I will double check if the scheme implementation is popuar than the circular implementation. It smells like an advertisement to me. --Leo 02:17, 12 February 2006 (UTC)

Article Title vs Subject and content

I am wondering if Queue is the best name for this article. This appears to be much more about a computing article about the Queue (data structure), not one about the overall social concept of a Queue as people waiting to be served, either as a physical waiting line, traffic at an intersection or as a more abstract concept such as is encountered when waiting to be answered by a call centre, jobs being processed in a computer or factory. It perhaps also needs to be explained that a queue is more of an British term, where the social etiquette of a queue is highly developed. -- Cameron Dewe 09:06, 5 October 2006 (UTC)

I moved the article to Queue (data structure) --Sharcho 02:44, 28 November 2006 (UTC)

Several cites may be of interest

I just massaged LIFO this afternoon, and there are several quotes in the references which may be of use here if someone wants to mine those. Cheers! // FrankB 00:09, 25 October 2007 (UTC)

Java example code

I noticed that the node that is created in the example code for java is named "New". This is confusing (especially for the novice java coder) as it is easily confusable with the keyword "new", which follows soon afterwards. It is especially bad, as the wikipedia syntax highlighter seems to highlight both versions of "new". Maybe it would be good to rename the new Node to something like "NewNode" or "NewlycreatedNode" or other. Thanks —Preceding unsigned comment added by 141.89.226.149 (talk) 10:10, 16 June 2010 (UTC)

C++ Code

The C++ example doesn't help much when the code defining the queue is included as a header file. This code only shows how to declare a queue and not what it consists of. 68.54.104.18 (talk) 18:35, 12 October 2010 (UTC)

Well there is a primitive C language implementation for you. The standard library is only meant to be used, you generally can't see what is inside the library. Writing a good queue is actually a non-trivial task. Redhanker (talk) 23:16, 14 January 2011 (UTC)

In wich case does function enqueue return 0? Is it possible? — Preceding unsigned comment added by 46.42.37.49 (talk) 08:31, 18 June 2011 (UTC)

To abstract a bit from this note, the whole Queues and programming languages may need some consideration. Anyone know of standard practice to give examples and language implementation descriptions for ADTs on WP? I saw ruby and perl, so I thought it'd be worth it to add a note about Python. Now I'm thinking, we should resolve the section to include a fair number of examples in a reasonable number of languages to sufficiently depict the range of usage of the queue. Would be happy to do a bit of legwork on this, any thoughts? Mattsenate (talk) 20:06, 28 December 2011 (UTC)

Fixed array inefficient?

"Fixed length arrays are limited in capacity, and inefficient because items need to be copied towards the head of the queue." Eh? I've never seen an implementation of a bounded queue that copies items towards the head; instead, one uses head and tail indices that wrap around modulo the queue size--or rather, the array size, since they have an extra element so you can tell the difference between an empty queue and a full one, but that's a space inefficiency, not a time inefficiency. —Preceding unsigned comment added by 209.234.91.82 (talk) 15:56, 16 February 2011 (UTC)

C example output

The sample output given for the C example is just a list of 100 random numbers. The same output would be given if there were no queue used in the example at all, so how does it illustrate the function of a queue? Seems like wasted space to me. John lindgren (talk) 12:33, 10 June 2011 (UTC)

Queue implementation with a single-linked list

The following statement requires clarification "A regular singly linked list only has efficient insertion and deletion at one end. However, a small modification—keeping a pointer to the last node in addition to the first one—will enable it to implement an efficient queue."

In a single-linked list, a remove can only be done at the beginning of the list, never at the end; insertions can be done at the beginning of the list and (if a pointer to the last node is maintained) also at the end of the list; so, a queue can be implemented with a single-linked list (that maintains a last-node pointer) as follows: insertions are done at the end, removes at the start of the list. — Preceding unsigned comment added by Microbizz (talk • contribs) 08:55, 10 March 2019 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Queue (abstract data type). Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive http://web.archive.org/web/20110714000645/http://www.ludvikjerabek.com/downloads.html to http://www.ludvikjerabek.com/downloads.html

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 00:01, 21 July 2016 (UTC)

Purely functional implementation

I find these paragraphs quite impenetrable. Don't lead the reader into dead ends with "almost" statements. Refrain from prose. Use mathematical notation or pseudocode. Plainly state invariants, plainly state base cases and equations/transformations. Those are the objects under discussion. Only after you've presented them, talk about them. Anyone who cares to read the reference material, please feel free to improve this section. --87.78.216.47 (talk) 02:16, 24 April 2020 (UTC)

Move discussion in progress

There is a move discussion in progress on Talk:Associative array which affects this page. Please participate on that page and not in this talk page section. Thank you. —RMCD bot 00:32, 27 January 2022 (UTC)

Wiki Education assignment: ENG 102

This article was the subject of a Wiki Education Foundation-supported course assignment, between 10 January 2022 and 6 May 2022. Further details are available on the course page. Student editor(s): Bamblok (article contribs).

Entities, elements, items, nodes

At least four terms are used in the article to name the elements of a queue. This seems inconsistent. Using four different names could especially be confusing to "non-English" readers. Is there a standard convention in CS? Also to note, it appears queuing theory uses "node" to name an entire queue. Brianepaul (talk) 22:36, 21 November 2022 (UTC)

Queue implementation through single linked list

The article says

A regular singly linked list only has efficient insertion and deletion at one end. However, a small modification—keeping a pointer to the last node in addition to the first one—will enable it to implement an efficient queue.

Having a pointer to the last node, when you dequeue you need to update that pointer and the only way to do it is to traverse the whole linked list to get the last node. Hence a deletion in O(n) and not constant time. 2A01:E0A:932:1CE0:6461:AA51:70DB:F834 (talk) 20:53, 15 December 2023 (UTC)