David Zaragoza
CS/EE 51
HW 3 Problem 1


QueInit()

Description: initializes and prepares a queue of size 2^n.  If for
example a queue of
size 10 elements is needed, a queue of size 16 elements is made, with n=4.

Inputs: integer n

Outputs: none

Arguments: none

User Interface: the user is prompted for an integer n.

Error Handling: error message if n <= 0.

Algorithms: an array of size 2^n is made, with all elements initialized to 0. Then 
both head and tail pointers are pointed to the first element of the array.

Data Structures: an array.

Known Bugs: the value 0 is considered empty, so 0 cannot be stored.

Limitations: cannot store values of 0.

PSEUDO-CODE

output(prompt)
n = get_input()
   IF (n > 0) THEN
       ARRAY A[power(2, n)]
       FOR (i=1 to power(2, n) every i+1)
          A[i]=0
       ENDFOR
       PTR T = A[1]
       PTR H = A[1]
   ELSE
      output(error message n <= 0)
   ENDIF
exit


QueueEmpty()

Description: returns zero flag reset if queue is empty, zero flag set otherwise.

Inputs: none

Output: none

Arguments: none

User Interface: none

Error Handling: none

Algorithms: if the head and tail pointers point to the same element and that element 
is zero resets returns zero flag reset, otherwise returns zero flag set. 

Data Structures: array 

Known Bugs: 0 considered a non-value

Limitations: none

PSEUDO-CODE

n = VALUE OF H
m = VALUE OF T
   IF (H=T) AND (n=0) AND (m=0) THEN 
      zero_flag_reset()
   ELSE
      zero_flag_set()
   ENDIF
exit


QueueFull()

Description: retuns zero flag reset if queue if full and zero flag set otherwise.

Inputs: none

Outputs: none

Arguments: none

User Interface: none

Algorithms: if the tail pointer points to the last element of the array the queue is
full.

Data Structures: an array

Error Handling: none

Known Bugs: none

Limitations: none

PSEUDO-CODE

   IF (T=A[power(2, n)]) THEN
      zero_flag_resest()
   ELSE
      zero_flag_set()
   ENDIF
exit



Dequeue()

Description: removes an 8-bit value form the head of the queue.  If the queue is empty
will wait until the queue as a value to retun.  Will not retun until queue has 
something to retun.

Input: none

Output: none

Arguments: none

User Interface: none

Error Handling: none

Algorithms: if the queue has at least one element return the vale pointed to by H then
increment H.  If the queue is empty wait until it has a value to return.

Data Structures: none

Known Bugs: none

Limitations: none

PSEUDO-CODE

n=0
QueueEmpty() 
   IF (zero_flag=reset) THEN
      n=VALUE OF H
      incr H
   ELSE
         REPEAT
            QueueEmpty()
         UNTIL(zero_flag=set)
      n=VALUE OF H
      incr H    
   ENDIF
return n




Enqueue(b)

Description: adds an 8-bit value (assuming integer) to head of the queue.  If the 
queue is full it waits until a spot is open.

Input: none

Output: none

Arguments: value b

User Interface: none

Error Handling: none

Algorithms: if the queue is NOT full increment T then put its value to b, otherwise
wait until the queue is not full then do the same.

Data Structures: none

Known Bugs: none

Limitations: none

PSEUDO-CODE
   
QueueFull()
   IF (zero_flag=set) THEN
      incr T
      VALUE OF T = b
   ELSE
         REPEAT
            QueueFull()
         UNTIL(zero_flag=set)
      incr T
      VALUE OF T = b
   ENDIF
exit