* What is a queue? @ 1999-01-25 0:00 Joshua Shriver 1999-01-26 0:00 ` dennison 1999-02-09 0:00 ` Michael F Brenner 0 siblings, 2 replies; 10+ messages in thread From: Joshua Shriver @ 1999-01-25 0:00 UTC (permalink / raw) I'm taking and ADA class now that teaches OOP. What is a queue and how do you use it? Sincerely, Joshua Shriver zeppelin@access.mountain.net ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What is a queue? 1999-01-25 0:00 What is a queue? Joshua Shriver @ 1999-01-26 0:00 ` dennison 1999-02-02 0:00 ` Nick Roberts 1999-02-09 0:00 ` Michael F Brenner 1 sibling, 1 reply; 10+ messages in thread From: dennison @ 1999-01-26 0:00 UTC (permalink / raw) In article <36accbc1.0@news.mountain.net>, zeppelin@access2.mountain.net (Joshua Shriver) wrote: > I'm taking and ADA class now that teaches OOP. > What is a queue and how do you use it? For an answer to a basic question like this, you should really ask your instructior. That's what you are paying them for after all.. T.E.D. -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What is a queue? 1999-01-26 0:00 ` dennison @ 1999-02-02 0:00 ` Nick Roberts 0 siblings, 0 replies; 10+ messages in thread From: Nick Roberts @ 1999-02-02 0:00 UTC (permalink / raw) It's a commonly used kind of data structure, which you (or someone else) would create using the Ada language (or other language). It allows several items to be stored and retrieved in a queue-like way. There are various other commonly-used data structures, e.g. stacks. To find out more about these structures, you need to either ask an instructor (or other knowledgeable person), or look in a library or bookshop for an Ada textbook. If you have genuinely exhausted all these avenues, or if you have a specific tricky question, then ask again in comp.lang.ada, and we will do our best :-) Happy hunting! ------------------------------------------- Nick Roberts ------------------------------------------- ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What is a queue? 1999-01-25 0:00 What is a queue? Joshua Shriver 1999-01-26 0:00 ` dennison @ 1999-02-09 0:00 ` Michael F Brenner 1999-02-10 0:00 ` Jeff Carter 1999-02-10 0:00 ` adam 1 sibling, 2 replies; 10+ messages in thread From: Michael F Brenner @ 1999-02-09 0:00 UTC (permalink / raw) It is sometimes hard to find answers to questions in a particular field. In computer science, a queue is an abstract data type (sometimes called a class) which can be implemented by, for example, an Ada package, in this case. The package would have a type statement like the following: type queues is limited private; and a bunch of methods for that type, such as the following: procedure add_to_left (object: objects; to: queues); procedure add_to_right (object: objects; to: queues); function take_from_left (queue: queues); function take_from_right (queue: queues); function image(queue: queues); no_more_objects_in_queue: exception; as well as the constructors and destructors: procedure initialize (queue: in out queues); procedure finalize (queue: in out queues); procedure copy (queue: queues; target: in out queues); procedure "&" (left, right: queues) return queues; As you can see, the basic methods permit you to add and things to the left and right of the queue, and to take things from the left and right of the queue. If you attempt to take something that does not have anything left, then you get a fatal error that tells you there are no more objects in the queue. Queues are used to handle situations where two processes are going at different speeds. Then the queue acts like a buffer between the two processes. The faster process can put stuff on the queue and the slower processor can take it off the queue at its own rate. The word queue derives from the British cultural tradition of people lining up to get some service. The service is represented mathematically by a giant circle, and the people lining up look like a straight or curly line. Thus, the two together look like a giant letter Q, which was then spelt queue to make it sound difficult to spell, which it is. Some Americans believe in queueing up, also. However, there are sometimes advantages to chaos, so do not use type queues for every situation you program! There is an interesting mathematical discipline of partial differential equations called queuing theory that looks at interesting effects on various queue configurations at different rates of arrivals and departures of the elements of the queues, building up, in the discrete case to something very interesting called finite state machines and their enhancements called Colored Petri Nets. But for your initial assignment, you need to implement a body for the package queue_management. In this body, you will code the procedures whose interfaces are given above. In addition, you will need to have some sort of heap management tool, such as an unlimited sized vector (a modification of the in-RAM array structures built into the Ada language, but extended so that your doubly linked list has no upper limit, but overflows to virtual storage). Programming these things are fun, and will get you into interesting things in dataflow control of distributed processes and the mathematics of shape theory before you know it. Good luck and enjoy queueing up. ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What is a queue? 1999-02-09 0:00 ` Michael F Brenner @ 1999-02-10 0:00 ` Jeff Carter 1999-02-17 0:00 ` Michael F Brenner 1999-02-10 0:00 ` adam 1 sibling, 1 reply; 10+ messages in thread From: Jeff Carter @ 1999-02-10 0:00 UTC (permalink / raw) Michael F Brenner wrote a long message about queues, which he defined as having such operations as Add_To_Left and Add_To_Right. All additions to a queue go on the tail, and all removals come from the head. A structure which allows additions and removals from both ends is a dequeue (pronounced deck). The concept of a queue comes from the way people engage in ordered waiting for something, such as service from a teller at a bank. The first person to arrive is served and the others wait in order. Most non-American English speakers call this collection of waiting people a queue, and say the people are standing in a queue. Americans call it a line, and say the people are waiting in line. Of course, people waiting in [a queue | line] behave more like a list than a (software) queue because people can leave the queue from any position at any time, sometimes people cut in ahead of the tail of the queue, and so on. Brenner gives a derivation of the word queue from mathematical diagrams; however, I think this is incorrect. Queue derives from the French word queue, which means tail and predates the diagrams in question. -- Jeff Carter E-mail: carter commercial-at innocon [period | full stop] com "You tiny-brained wipers of other people's bottoms!" Monty Python & the Holy Grail ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What is a queue? 1999-02-10 0:00 ` Jeff Carter @ 1999-02-17 0:00 ` Michael F Brenner 1999-02-18 0:00 ` robert_dewar 1999-02-19 0:00 ` Jeff Carter 0 siblings, 2 replies; 10+ messages in thread From: Michael F Brenner @ 1999-02-17 0:00 UTC (permalink / raw) > Mike wrote a long message about queues, which he defined as > having such operations as Add_To_Left and Add_To_Right. > > All additions to a queue go on the tail, and all removals come from the > head. A structure which allows additions and removals from both ends is > a dequeue (pronounced deck). Thanks for the alternative to the first definition, which has some strengths. However, there is nothing wrong with implementing a general-purpose extensible array of data and putting and taking from either end, so you get two-sided queue, which can serve as the implementation of both of your definitions (dequeue and queue), as well as the implementation of a stack. When three structures are this closely related, it makes sense to do the extensible data structures with my more flexible definition, and then provide application-level restricted packages that provide only certain operations. In one sense, the exclusive definition is written for that higher level and the inclusive defintion was intended for that lower implementation level, because the programmer may spend quite a bit more time on that level than on the outer levels. I was at the grocery store today and the clerk opened up an new line and the back half of the queue wound around to that new line, effectively taking from both ends of the queue at the same time. And many algorithms require PEEKING at various intermediate elements of a two-sided queue without deleteing them from the queue. For example, a 10-line windowed grep, which searches for a pattern and prints the file name and the previous 10 lines and the next 10 lines for each line that matches the pattern. Thanks again for pointing out that there are several ways of defining things, and several ways of implementing various data structures. Mike ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What is a queue? 1999-02-17 0:00 ` Michael F Brenner @ 1999-02-18 0:00 ` robert_dewar 1999-02-19 0:00 ` Jeff Carter 1 sibling, 0 replies; 10+ messages in thread From: robert_dewar @ 1999-02-18 0:00 UTC (permalink / raw) In article <7afgd8$fnj@top.mitre.org>, mfb@mbunix.mitre.org (Michael F Brenner) wrote: > Thanks for the alternative to the first definition, which > has some strengths. > > However, there is nothing wrong with implementing > a general-purpose extensible array of data and > putting and taking from either end No, but there is a lot wrong with calling this a queue. As was pointed out this is a dequeue, and confusing the two data structures and their terminology is a bad idea. Also, although conceptually a queue is a special case of a dequeue with only a limited subset of the functionality in use, it is a bad idea to use it this way for two reasons. If you really want a queue, it is merely confusing and error prone to provide operations that have nothing to do with a queue. It may be substantially less efficient to implement a general dequeue than a queue. In particular there are data structures suitable for queue implementation that are not suitable for dequeue use. , so you get two-sided queue, > which can serve as the implementation of both of your definitions > (dequeue and queue), as well as the implementation of a stack. > > When three structures are this closely related, it makes sense > to do the extensible data structures with my more flexible > definition, and then provide application-level restricted > packages that provide only certain operations. > > In one sense, the exclusive definition is written for that > higher level and the inclusive defintion was intended for that > lower implementation level, because the programmer may spend > quite a bit more time on that level than on the outer levels. > > I was at the grocery store today and the clerk opened up an > new line and the back half of the queue wound around to that > new line, effectively taking from both ends of the queue > at the same time. > > And many algorithms require PEEKING at various intermediate > elements of a two-sided queue without deleteing them from the > queue. For example, a 10-line windowed grep, which searches > for a pattern and prints the file name and the previous > 10 lines and the next 10 lines for each line that matches > the pattern. > > Thanks again for pointing out that there are several ways of > defining things, and several ways of implementing various > data structures. > > Mike > > -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What is a queue? 1999-02-17 0:00 ` Michael F Brenner 1999-02-18 0:00 ` robert_dewar @ 1999-02-19 0:00 ` Jeff Carter 1 sibling, 0 replies; 10+ messages in thread From: Jeff Carter @ 1999-02-19 0:00 UTC (permalink / raw) Michael F Brenner wrote: > > > Mike wrote a long message about queues, which he defined as > > having such operations as Add_To_Left and Add_To_Right. > > > > All additions to a queue go on the tail, and all removals come from the > > head. A structure which allows additions and removals from both ends is > > a dequeue (pronounced deck). > > Thanks for the alternative to the first definition, which has some > strengths. > > However, there is nothing wrong with implementing > a general-purpose extensible array of data and > putting and taking from either end, so you get two-sided queue, > which can serve as the implementation of both of your definitions > (dequeue and queue), as well as the implementation of a stack. > > When three structures are this closely related, it makes sense > to do the extensible data structures with my more flexible > definition, and then provide application-level restricted > packages that provide only certain operations. > > In one sense, the exclusive definition is written for that > higher level and the inclusive defintion was intended for that > lower implementation level, because the programmer may spend > quite a bit more time on that level than on the outer levels. Well, at a low level, queues, dequeues, and stacks are all I/O-limited lists, but that does not make a list a queue. It means that a list may used to implement a queue. Similarly, a dequeue may be used to implement a queue, but a dequeue is not a queue. > > I was at the grocery store today and the clerk opened up an > new line and the back half of the queue wound around to that > new line, effectively taking from both ends of the queue > at the same time. I think I mentioned the same kind of discrepencies between ideal software queues and the people queues one encounters in the real world. > > And many algorithms require PEEKING at various intermediate > elements of a two-sided queue without deleteing them from the > queue. For example, a 10-line windowed grep, which searches > for a pattern and prints the file name and the previous > 10 lines and the next 10 lines for each line that matches > the pattern. > > Thanks again for pointing out that there are several ways of > defining things, and several ways of implementing various > data structures. > > Mike -- Jeff Carter E-mail: carter commercial-at innocon [period | full stop] com "I unclog my nose towards you." Monty Python & the Holy Grail ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What is a queue? 1999-02-09 0:00 ` Michael F Brenner 1999-02-10 0:00 ` Jeff Carter @ 1999-02-10 0:00 ` adam 1999-02-10 0:00 ` Fraser Wilson 1 sibling, 1 reply; 10+ messages in thread From: adam @ 1999-02-10 0:00 UTC (permalink / raw) In article <79q1qc$blj@top.mitre.org>, mfb@mbunix.mitre.org (Michael F Brenner) wrote: > The word queue derives from the British cultural tradition of > people lining up to get some service. The service is represented > mathematically by a giant circle, and the people lining up look > like a straight or curly line. Thus, the two together look like a > giant letter Q, which was then spelt queue to make it sound > difficult to spell, which it is. . . . Hmmm, my Merriam-Webster's Ninth New Collegiate (1984) gives "French, literally, tail" as the origin of the word. -- Adam -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What is a queue? 1999-02-10 0:00 ` adam @ 1999-02-10 0:00 ` Fraser Wilson 0 siblings, 0 replies; 10+ messages in thread From: Fraser Wilson @ 1999-02-10 0:00 UTC (permalink / raw) I nearly cried when adam@irvine.com said: >Hmmm, my Merriam-Webster's Ninth New Collegiate (1984) gives "French, >literally, tail" as the origin of the word. Oh, wow. No wonder I've seen 'queue' used to denote that pony tail that guys sometimes have. And they say the internet can't teach us anything. Ha! Fraser. ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~1999-02-19 0:00 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1999-01-25 0:00 What is a queue? Joshua Shriver 1999-01-26 0:00 ` dennison 1999-02-02 0:00 ` Nick Roberts 1999-02-09 0:00 ` Michael F Brenner 1999-02-10 0:00 ` Jeff Carter 1999-02-17 0:00 ` Michael F Brenner 1999-02-18 0:00 ` robert_dewar 1999-02-19 0:00 ` Jeff Carter 1999-02-10 0:00 ` adam 1999-02-10 0:00 ` Fraser Wilson
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox