Queues and Stacks

Queues

It's common in computing to have a device or software module that has more work than it can handle - think of a class of 20 students all trying to print their outcome at the same time. Just as in any civilised place where demand outstrips supply, clients form a queue and wait to be served: first in, first served. This is sometimes called a FIFO (First in-first out) data structure. As new clients arrive to be processed, they join the end of the queue and wait for their turn.

This is the process used by print queues to handle print jobs. It is also the system used by operating systems to handle events in the order in which they happen: if they got out of order, operations could be disastrous.

For example, you click a text box to select it, then you type a few characters. If those events were handled in the wrong order, the typed text could be entered into whatever the active control was, leading to big, unpredictable problems.

Stacks

See the theory slideshow!

A stack is a simple yet powerful data structure that is used to store data to be used during computation. Stacks are fundamental to CPU processing and calculators.

Stacks obey a few primitive commands as simple as PUSH (to put data onto the top of the stack) and POP (retrieve data from the top of the stack and return it to the caller).

Some stack implementations also allow commands like these:

PEEP - retrieve a value from anywhere within the stack without removing it.

DUP(licate) - push the value at the top of the stack onto the stack again.

SWAP - swap the 2 values at the top of the stack

ROTATE n - shift the first n stack items one place (so if a stack contained 1,2,3 then ROTATE 3 would change the stack to 2,3,1). ROTATE might come in flavours like left rotate and right rotate.

Stacks can be easily implemented with a one-dimenstional array or a linked list and a simple stack pointer (a variable to keep track of the size of the stack). Stacks naturally form orderly queues.

Stacks come in basic flavours:

• First in, last out (LIFO) - consider a stack of books where added books sit on top, and only the top book can be removed.
• First in, first out (like a queue) (FIFO)

A FILO stack in action:

Implementing a stack in Basic

DIM StackSize AS INTEGER 'global variable accessible to any subprogram
StackSize=15 'how many items can be put in the stack
DIM Stack(0 TO StackSize) AS INTEGER 'global array
DIM StackPointer AS INTEGER 'global pointer to current stack item
StackPointer=0

SUB PUSH(value)
IF Stackpointer < Stacksize THEN 'test if stack is full
StackPointer = StackPointer + 1
Stack(StackPointer) = value
ELSE
MSGBOX "Stack overflow"
END IF
END SUB

FUNCTION POP( )
IF StackPointer > 0 THEN 'test if stack is already empty
RETURN Stack(StackPointer)
StackPointer = StackPointer - 1
ELSE
MSGBOX "Stack is empty"
END IF
END FUNCTION