What is a queue?

What is a queue?

[Joshua Shriver]

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

Re: What is a queue?

[dennison]

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    

Re: What is a queue?

[Nick Roberts]

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
-------------------------------------------

Re: What is a queue?

[Michael F Brenner]

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.

Re: What is a queue?

[adam]

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    

Re: What is a queue?

[Jeff Carter]

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

Re: What is a queue?

[Fraser Wilson]

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.

Re: What is a queue?

[Michael F Brenner]

    > 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

Re: What is a queue?

[robert_dewar]

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    

Re: What is a queue?

[Jeff Carter]

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