Fall 2001, CSE 520: Solution of Assignment 6

One possible solution is to modify the definition of the cell C(x), so that when the operation in(y) is performed, the datum y is passed immediately to the next component on the right, using the "i" link. When the next component on the right is B, it will create another cell containing y. This is already in the definition of B. 
   Queue(e) =def=  B
  
      B =def= in(x).(C(X)--B) + empty.B
   
   C(x) =def= in(y).^i(y).C(x) + ^out(x).D
      D =def= o(y).C(y) + ^e.B
The operation "--" is the usual concatenation between components along the "i", "e" and "o" links.

Some students wrote the following solution, which is slightly less elegant, but still correct: 

   Queue(e) =def=  B

      B =def= in(x).(C(X)--B) + empty.B

   C(x) =def= in(y).A + ^out(x).D
      A =def= ^i(y).C(x) + ^e.(C(x)--C(y)--B) 
      D =def= o(y).C(y) + ^e.B