Entry
Datastructure: Queue: What is a queue?
Dec 23rd, 2004 11:20
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 22 December 2004 - 08:40 pm -------------------
Datastructure: Queue: What is a queue?
---
A queue is a structure in which you can store data.
It is one of the simplest (linear) structures for storing information
available.
To add data you store it on the one side of this structure.
To remove data you remove it from the other side of this structure.
(The common thing here is thus you only touch the 'sides' of the
structure, instead of also adding, removing or getting data from the
'interior' of the structure.
A stack is still simpler, there any 'one sided' structure will do.
So in general any 'twosided' structure in which you can store will do.
If you remove only from one side it is a stack.
If you remove from one side and add to the other side it is queue.
If you remove and add from both sides it is a dequeue).
---
Using a string as a queue:
One of the most simple structures to use as a queue is a string.
To store data you put it on the left side of the string.
To remove data you remove it from the right side of the string.
(or similarly store on the right and remove from the left of the
string)
---
original:
"a b c d e f g"
---
adding:
"z a b c d e f g"
---
removing:
"a b c d e f"
---
Using a file as a queue:
Another possibility to store the information is using a file.
To add new information (e.g. lines) you put it in the top of the
file.
To remove information (e.g. lines) you remove it from the bottom
of the file.
(or similarly store on the bottom and remove from the top of the
file)
a
b
c
d
e
f
g
---
Using a computer memory as a queue:
Other possibilities to store the information is computer memory.
To add new information (e.g. a variable) you put it in the top of the
memory range.
To remove information (e.g. a variable) you remove it from the bottom
of the memory range.
(or similarly store on the bottom and remove from the top of the
memory range)
[ a ]
[ b ]
[ c ]
[ d ]
[ e ]
[ f ]
[ g ]
---
Using an array as a queue:
Other possibilities to store the information is an array.
To add new information (e.g. a variable) you put it in the top of the
array.
To remove information (e.g. a variable) you remove it from the bottom
of the array.
(or similarly store on the bottom and remove from the top of the
array)
[ a ]
[ b ]
[ c ]
[ d ]
[ e ]
[ f ]
[ g ]
---
---
This method of storing and removing data means that what you put
first in (e.g. on top of the file) and then removing from the bottom
means that it will be removed the first (as it is closest to the
bottom while you add new elements).
Or in other words it is 'F'irst 'I'n 'F'irst 'O'ut, or thus
abbreviated it is FIFO.
(or similarly 'L'ast 'I'n 'L'ast 'O'ut, or thus LILO).
---
---
Internet: see also:
---
Datastructure: Link: Overview: Can you give an overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/32054/fid/1264
----------------------------------------------------------------------
