Entry
Datastructure: Queue: Array: BBCBASIC: How to program a queue?
Feb 5th, 2005 10:24
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 05 February 2005 - 10:38 pm -------------------
Datastructure: Queue: Array: BBCBASIC: How to program a queue?
---
Method:
You use an array with 2 counters, one for the begin
and one for the end.
You add at the end of the array, by increasing the end counter.
You remove from the begin of the array, by increasing the begin
counter.
---
figure: example array showing the 2 counter
[ A B C D E F G H I J K L M N ... X Y Z ]
^ ^
| |
begin pointer end pointer
---
Steps: Overview:
1. -Create an array
2. -Create 2 counters
1. One counter pointing to the begin of the array
2. One counter pointing to the end of the array
3. -Initialize the counters
1. Give the begin counter an initial value minus one
2. Give the end counter the same value
4. -Operation: Queue: Get
1. To get a value
2. Get the value in the array at the begin counter position
5. -Operation: Queue: Set
1. To set a value
2. Set the value in the array at the begin counter position
6. -Operation: Queue: Add
1. To add a value
1. Increase the end counter with one
2. Set the value in the array at that position
7. -Operation: Queue: Remove
1. To remove a value
1. Increase the begin counter with one
8. -Operation: Queue: Check: Empty
1. To check if the queue is empty
1. Check if the begin counter has moved passed the end counter
9. -Operation: Queue: Check: Full
1. To check if the queue is full
1. Check if the end counter has moved passed the maximum rows
in array
IF ( queueendI% >= rowmaxI% ) THEN PRINT "queue full"
10. -Operation: Queue: View
1. For first to last row of the array
1. Print the content of the array at that row
---
---
Steps: Worked out:
1. -Create an array
rowminI% = 1
rowmaxI% = 100
DIM s$( rowmaxI% )
2. -Create 2 counters
1. One counter pointing to the begin of the array
2. One counter pointing to the end of the array
3. -Initialize the counters
1. Give the begin counter an initial value minus one
queuebeginI% = rowminI% - 1
2. Give the end counter the same value
queueendI% = queuebeginI%
4. -Operation: Add
1. To add a value
1. Increase the end counter with one
queueendI% = queueendI% + 1
2. Insert the value in the array at that position
s$( queueendI% ) = "A"
5. -Operation: Remove
1. To remove a value
1. Increase the begin counter with one
queuebeginI% = queuebeginI% + 1
2. Remove the value at the position of the begin counter
s$( queuebeginI% ) = ""
6. -Operation: Queue: Check: Empty
1. To check if the queue is empty
1. Check if the begin counter has moved passed the end counter
IF ( queuebeginI% >= queueendI% ) THEN PRINT "queue empty"
7. -Operation: Queue: Check: Full
1. To check if the queue is empty
1. Check if the end counter has moved passed the maximum rows
in array
IF ( queueendI% >= rowmaxI% ) THEN PRINT "queue full"
8. -Operation: Queue: View
1. For first to last row of the array
1. Print the content of the array at that row
FOR rowI% = rowminI% TO rowmaxI%
PRINT rowI%; " "; s$( rowI% ); " ";
NEXT rowI%
PRINT
---
---
Example:
--- cut here: begin --------------------------------------------------
rowminI% = 1
rowmaxI% = 3
:
DIM s$( rowmaxI% )
:
queuebeginI% = rowminI% - 1
queueendI% = queuebeginI%
:
REM add a value
IF ( queueendI% >= rowmaxI% ) THEN PRINT "queue full" ELSE queueendI%
= queueendI% + 1 : s$( queueendI% ) = "A"
:
REM view the queue
FOR rowI% = rowminI% TO rowmaxI%
PRINT rowI%; " "; s$( rowI% ); " ";
NEXT rowI%
PRINT
:
REM add a value
IF ( queueendI% >= rowmaxI% ) THEN PRINT "queue full" ELSE queueendI%
= queueendI% + 1 : s$( queueendI% ) = "B"
:
REM view the queue
FOR rowI% = rowminI% TO rowmaxI%
PRINT rowI%; " "; s$( rowI% ); " ";
NEXT rowI%
PRINT
:
REM add a value
IF ( queueendI% >= rowmaxI% ) THEN PRINT "queue full" ELSE queueendI%
= queueendI% + 1 : s$( queueendI% ) = "C"
:
REM view the queue
FOR rowI% = rowminI% TO rowmaxI%
PRINT rowI%; " "; s$( rowI% ); " ";
NEXT rowI%
PRINT
:
REM add a value
IF ( queueendI% >= rowmaxI% ) THEN PRINT "queue full" ELSE queueendI%
= queueendI% + 1 : s$( queueendI% ) = "D"
:
REM view the queue
FOR rowI% = rowminI% TO rowmaxI%
PRINT rowI%; " "; s$( rowI% ); " ";
NEXT rowI%
PRINT
:
REM remove a value
IF ( queuebeginI% >= queueendI% ) THEN PRINT "queue empty" ELSE
queuebeginI% = queuebeginI% + 1 : s$( queuebeginI% ) = ""
:
REM view the queue
FOR rowI% = rowminI% TO rowmaxI%
PRINT rowI%; " "; s$( rowI% ); " ";
NEXT rowI%
PRINT
:
REM remove a value
IF ( queuebeginI% >= queueendI% ) THEN PRINT "queue empty" ELSE
queuebeginI% = queuebeginI% + 1 : s$( queuebeginI% ) = ""
:
REM view the queue
FOR rowI% = rowminI% TO rowmaxI%
PRINT rowI%; " "; s$( rowI% ); " ";
NEXT rowI%
PRINT
:
REM remove a value
IF ( queuebeginI% >= queueendI% ) THEN PRINT "queue empty" ELSE
queuebeginI% = queuebeginI% + 1 : s$( queuebeginI% ) = ""
:
REM view the queue
FOR rowI% = rowminI% TO rowmaxI%
PRINT rowI%; " "; s$( rowI% ); " ";
NEXT rowI%
PRINT
:
REM remove a value
IF ( queuebeginI% >= queueendI% ) THEN PRINT "queue empty" ELSE
queuebeginI% = queuebeginI% + 1 : s$( queuebeginI% ) = ""
:
REM view the queue
FOR rowI% = rowminI% TO rowmaxI%
PRINT rowI%; " "; s$( rowI% ); " ";
NEXT rowI%
PRINT
:
--- cut here: end ----------------------------------------------------
---
If you run this program, you will get the following output:
--- cut here: begin --------------------------------------------------
1 A 2 3
---
1 A 2 B 3
---
1 A 2 B 3 C
---
queue full
1 A 2 B 3 C
---
1 2 B 3 C
---
1 2 3 C
---
1 2 3
---
queue empty
1 2 3
--- cut here: end ----------------------------------------------------
---
---
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
----------------------------------------------------------------------
