CS 131 LECTURE 7 - STACKS AND QUEUES

GENERIC STACK PACKAGE

Stack Package Specification

GENERIC
  TYPE Elements IS PRIVATE;
PACKAGE Stack_Package IS
  TYPE Stacks IS LIMITED PRIVATE;
  FUNCTION Empty(Stack: Stacks)
    RETURN Boolean;
  PROCEDURE Push(Stack: IN OUT Stacks;
    Item: IN Elements);
  PROCEDURE Pop(Stack: IN OUT Stacks;
    Item: OUT Elements);
  Empty_Stack, Full_Stack: EXCEPTION;
PRIVATE
  Size: CONSTANT := 100;
  TYPE Lists IS ARRAY(1..Size) OF Elements;
  TYPE Stacks IS
    RECORD
      Top: Integer RANGE 0..Size:= 0;
      List: Lists;
    END RECORD;
END Stack_Package;

Important Points:

1. This Package Implements Stacks With Arrays

2. In The Next Lecture, We Will Study An Implementation Of A Stack That Uses Linked Lists

GENERIC STACK PACKAGE

Stack Package Body

PACKAGE BODY Stack_Package IS
  FUNCTION Empty(Stack: Stacks)
    RETURN Boolean IS
  BEGIN
    RETURN Stack.Top = 0;
  END Empty;
  PROCEDURE Push(Stack: IN OUT Stacks;
    Item: IN Elements) IS
  BEGIN
    IF Stack.Top < Size THEN
      Stack.Top := Stack.Top + 1;
      Stack.List(Stack.Top) := Item;
    ELSE
      RAISE Full_Stack;
    END IF;
  END Push;
  PROCEDURE Pop(Stack: IN OUT Stacks;
    Item: OUT Elements) IS
  BEGIN
    IF Stack.Top > 0 THEN
      Item := Stack.List(Stack.Top);
      Stack.Top := Stack.Top - 1;
    ELSE
      RAISE Empty_Stack;
    END IF;
  END Pop;
END Stack_Package;

REVERSAL APPLICATION

Reverse Integers Procedure:

WITH Text_IO,Stack_Package;
PROCEDURE Reverse_Integers IS
  Number: Integer;
  PACKAGE Int_IO IS NEW
    Text_IO.Integer_IO(Integer);
  PACKAGE Integer_Stack IS NEW
    Stack_Package(Integer);
  Stack: Integer_Stack.Stacks;
BEGIN
  WHILE NOT Text_IO.End_Of_File LOOP
    Int_IO.Get(Number);
    Integer_Stack.Push(Stack, Number);
  END LOOP;
  WHILE NOT Integer_Stack.Empty(Stack) LOOP
    Integer_Stack.Pop(Stack, Number);
    Int_IO.Put(Number);
  END LOOP;
EXCEPTION
  WHEN Integer_Stack.Full_Stack =>
    Text_IO.Put_Line("Stack Overflow");
END Reverse_Integers;

Important Points:

1. The Reverse Integers Procedure Will Work Equally Well With Any Stack Implementation

2. It Is Loosely Coupled To Stack Package

EXPRESSION REPRESENTATIONS

Terminology:

Infix Expression: An Expression Representation In Which The Operator Is Between Both Operands

Prefix Expression: An Expression Representation In Which The Operator Precedes Both Operands

Postfix Expression: An Expression Representation In Which The Operator Follows Both Operands

Prefix Expression Evaluation

* + 3 1 5 = * 4 5 = 20

+ - 8 + 2 3 2 = + - 8 5 2 = + 3 2 = 5

Postfix Expression Evaluation

2 3 + 1 - = 5 1 - = 4

8 3 1 + 4 2 / - - = 8 4 4 2 / - - = 8 4 2 - - = 8 2 - = 6

Important Points:

1. Prefix And Postfix Expressions Never Require Parentheses

2. Stacks Are Useful For The Evaluation Of Expressions Because Expressions Are Nested Structures, They Can Contain Subexpressions

FIFO QUEUE PACKAGE

FIFO Queue Package Specification

GENERIC
  TYPE Elements IS PRIVATE;
PACKAGE FIFO_Queue_Package IS
  TYPE Queues IS LIMITED PRIVATE;
  FUNCTION Empty(Queue: Queues)
    RETURN Boolean;
  PROCEDURE Enqueue(Queue: IN OUT Queues;
    Item: IN Elements);
  PROCEDURE Dequeue(Queue: IN OUT Queues;
    Item: OUT Elements);
  Empty_Queue, Full_Queue: EXCEPTION;
PRIVATE
  Size: CONSTANT := 100;
  TYPE Lists IS ARRAY(1..Size) OF Elements;
  TYPE Queues IS
    RECORD
      Back: Integer RANGE 0..Size := 0;
      List: Lists;
    END RECORD;
END FIFO_Queue_Package;

Important Point:

1. The Big-O For The Enqueue Operation Is O(1) But The Big-O For The Dequeue Operation In This Implementation Is O(n)

LINEAR IMPLEMENTATION

FIFO Queue Package Body

PACKAGE BODY FIFO_Queue_Package IS
  -- Empty Function
  PROCEDURE Enqueue(Queue: IN OUT Queues;
    Item: IN Elements) IS
  BEGIN
    IF Queue.Back < Size THEN
      Queue.Back := Queue.Back + 1;
      Queue.List(Queue.Back) := Item;
    ELSE
      RAISE Full_Queue;
    END IF;
  END Enqueue;
  PROCEDURE Dequeue(Queue: IN OUT Queues;
    Item: OUT Elements) IS
  BEGIN
    IF Queue.Back > 0 THEN
      Item := Queue.List(1);
      FOR I IN 2..Queue.Back LOOP
        Queue.List(I-1) := Queue.List(I);
      END LOOP;
      Queue.Back := Queue.Back - 1;
    ELSE
      RAISE Empty_Queue;
    END IF;
  END Dequeue;
END FIFO_Queue_Package;

EFFICIENT FIFO QUEUE PACKAGE

FIFO Queue Package Specification

GENERIC
  TYPE Elements IS PRIVATE;
PACKAGE FIFO_Queue_Package IS
  TYPE Queues IS LIMITED PRIVATE;
  FUNCTION Empty(Queue: Queues)
    RETURN Boolean;
  PROCEDURE Enqueue(Queue: IN OUT Queues;
    Item: IN Elements);
  PROCEDURE Dequeue(Queue: IN OUT Queues;
    Item: OUT Elements);
  Empty_Queue, Full_Queue: EXCEPTION;
PRIVATE
  Size: CONSTANT := 100;
  TYPE Lists IS ARRAY(1..Size) OF Elements;
  TYPE Queues IS
    RECORD
      Front: Integer RANGE 1..Size := 1;
      Back: Integer RANGE 1..Size := 1;
      List: Lists;
    END RECORD;
END FIFO_Queue_Package;

Important Points:

1. The Big-O For Both Enqueue And Dequeue Is O(1)

2. Modular Arithmetic Is Used To Create A Circular Array

CIRCULAR QUEUE DIAGRAM

Circular Queue Diagram

Important Points:

1. In The Original Implementation The Server Is Fixed And The Queue Shifts On Each Dequeue

2. In This Implementation The Server Rotates And The Members Of The Queue Remain Fixed

CIRCULAR ARRAY IMPLEMENTATION

FIFO Queue Package Body

PACKAGE BODY FIFO_Queue_Package IS
  -- Empty Function
  PROCEDURE Enqueue(Queue: IN OUT Queues;
    Item: IN Elements) IS
  BEGIN
    IF Queue.Back MOD Size + 1 /=
    Queue.Front THEN
      Queue.List(Queue.Back) := Item;
      Queue.Back := Queue.Back MOD Size+ 1;
    ELSE
      RAISE Full_Queue;
    END IF;
  END Enqueue;
  PROCEDURE Dequeue(Queue: IN OUT Queues;
    Item: OUT Elements) IS
  BEGIN
    IF Queue.Back /= Queue.Front THEN
      Item := Queue.List(Queue.Front);
      Queue.Front :=
        Queue.Front MOD Size + 1;
    ELSE
      RAISE Empty_Queue;
    END IF;
  END Dequeue;
END FIFO_Queue_Package;

FIFO QUEUE APPLICATION

Duplicate Procedure

WITH Text_IO,FIFO_Queue_Package;
PROCEDURE Duplicate IS
  Number: Integer;
  PACKAGE Integer_Queue IS NEW
    FIFO_Queue_Package(Integer);
  PACKAGE Int_IO IS NEW
    Text_IO.Integer_IO(Integer);
  Queue: Integer_Queue.Queues;
BEGIN
  WHILE NOT Text_IO.End_Of_Line LOOP
    Int_IO.Get(Number);
    Int_IO.Put(Number);
    Integer_Queue.Enqueue(Queue,Number);
  END LOOP;
  WHILE NOT Integer_Queue.Empty(Queue) LOOP
    Integer_Queue.Dequeue(Queue,Number);
    Int_IO.Put(Number);
  END LOOP;
END Duplicate;

Important Points:

1. Queues Are Used Extensively By Operating Systems For Scheduling Of Resources

2. FIFO Queues Provide First-Come First-Served Scheduling

PRIORITY QUEUE PACKAGE

Priority Queue Package Specification

GENERIC
  TYPE Elements IS PRIVATE;
  TYPE Priorities IS PRIVATE;
  WITH FUNCTION Get_Rank(Element: Elements)
    RETURN Priorities;
  WITH FUNCTION "<"(Left,Right: Priorities)
    RETURN Boolean IS <>;
PACKAGE Priority_Queue_Package IS
  TYPE Queues IS PRIVATE;
  FUNCTION Empty(Queue: Queues)
    RETURN Boolean;
  PROCEDURE Enqueue(Queue: IN OUT Queues;
    Item: IN Elements);
  PROCEDURE Dequeue(Queue: IN OUT Queues;
    Item: OUT Elements);
  Empty_Queue, Full_Queue: EXCEPTION;
PRIVATE
  Size: CONSTANT := 100;
  TYPE Lists IS ARRAY(Integer RANGE <>)
    OF Elements;
  TYPE Queues IS
    RECORD
      Highest: Integer RANGE 0..Size := 0;
      List: Lists(1..Size);
    END RECORD;
END Priority_Queue_Package;

PRIORITY QUEUE IMPLEMENTATION

Priority Queue Package Body

PACKAGE BODY Priority_Queue_Package IS
  PROCEDURE Enqueue(Queue: IN OUT Queues;
    Item: IN Elements) IS
    I: Integer := Queue.Highest;
  BEGIN
    IF Queue.Highest = Size THEN
      RAISE Full_Queue;
    END IF;
    WHILE I > 0 LOOP
      EXIT WHEN Get_Rank(Queue.List(I)) <
        Get_Rank(Item);
      Queue.List(I+1) := Queue.List(I);
      I := I - 1;
    END LOOP;
    Queue.List(I+1) := Item;
    Queue.Highest := Queue.Highest + 1;
  END Enqueue;
  PROCEDURE Dequeue(Queue: IN OUT Queues;
    Item: OUT Elements) IS
  BEGIN
    IF Queue.Highest = 0 THEN
      RAISE Empty_Queue;
    END IF;
    Item := Queue.List(Queue.Highest);
    Queue.Highest := Queue.Highest - 1;
  END Dequeue;
END Priority_Queue_Package;

PRIORITY QUEUE APPLICATION

Alphabetize Procedure

WITH Text_IO,Priority_Queue_Package;
PROCEDURE Alphabetize IS
  Char: Character;
  FUNCTION Position(Char: Character)
  RETURN Integer IS
  BEGIN
    RETURN Character'Pos(Char);
  END Position;
  PACKAGE Character_Queue IS NEW
    Priority_Queue_Package(Character,
    Integer,Position);
BEGIN
  DECLARE
    Queue: Character_Queue.Queues; 
  BEGIN
    WHILE NOT Text_IO.End_Of_Line LOOP
      Text_IO.Get(Char);
      Character_Queue.Enqueue(Queue,Char);
    END LOOP;
    WHILE NOT Character_Queue.Empty(Queue)
    LOOP
      Character_Queue.Dequeue(Queue,Char);
      Text_IO.Put(Char);
    END LOOP;
    Text_IO.New_Line;
  END;
END Alphabetize;

/ Top of Page /