Queues and Stacks
Queue is just another word for line.
Think of a line at Burger King
Also called a First-In, First-Out or FIFO structure
This structure fits well with many Computer Science concepts, such as communication lines, files, pipes, etc.

Operations on Queues
Major operations:
Enqueue( ): Add an item to the queue
Dequeue( ): Remove and item from the queue
Peek( ): Look at the next item
MakeEmpty( ): Initialize the queue
IsFull( ): See if queue is full
IsEmpty( ): See if queue is empty

Abstract Design
We’ll say a queue has a head, a tail, and CurLength
Items are added to the tail
Items are removed from the head
The head item is examined by peek( )
We can use CurLength to determine IsFull( ) and IsEmpty( )

Array Implementation

We can use an array with a “cursor” to indicate the tail.
Just like in a line, when the first person is serviced, everyone else moves up one position in line.
All we do is copy all the elements forward one space, overwriting the one at the head.
Example: Cool Animation!
Ada Queue Specification
GENERIC
  TYPE Element IS PRIVATE;
PACKAGE Queues_Generic IS
  TYPE Queue( Capacity : Positive ) IS
    LIMITED PRIVATE;

  PRIVATE List IS ARRAY( Positive RANGE <> )
    OF Element;
  TYPE Queue( Capacity : Positive ) IS RECORD
    Tail  : Natural := 0;
    Store : List( 1..Capacity );
  END RECORD;
END Queues_Generic;
Better Approach
What is the runtime complexity of the Enqueue( ) operation?
What about the Dequeue( ) operation?
How can we improve on this?
Example: More Cool Animation!
Circular Array
We can visualize this as a circular array (Circular Buffer)
Stacks
Stack is just another word for pile.
Think of a stack of newspapers
Also called a Last-In, First-Out or LIFO structure
This structure also fits well with many Computer Science concepts, such as execution stacks, memory management, etc.

Operations on Stacks
Major operations:
Push( ): Add an item to the stack
Pop( ): Remove and item from the stack
Peek( ): Look at the next item
MakeEmpty( ): Initialize the stack
IsFull( ): See if stack is full
IsEmpty( ): See if stack is empty

Abstract Design
We’ll say a stack has a top
Items are added to the top
Items are removed from the top
The top item is examined by peek( )
Example: Reverse Polish Notation
Infix Notation:

( 5 * 2 ) - ((( 3 + 4 * 7 ) + 8 / 6 ) * 9 )

Reverse Polish Notation:

5 2 * 3 4 7 * + 8 6 / + 9 * -

Example: More Animation!
Ada Stack Specification
GENERIC
  TYPE Element IS PRIVATE;
PACKAGE Stacks_Generic IS
  TYPE Stack( Capacity : Positive ) IS
    LIMITED PRIVATE;

  PRIVATE List IS ARRAY( Positive RANGE <> )
    OF Element;
  TYPE Stack( Capacity : Positive ) IS RECORD
    Top   : Natural := 0;
    Store : List( 1..Capacity );
  END RECORD;
END Stack_Generic;