Portfolio Milestone II

This is the second portfolio milestone for my class, where I will demonstrate knowledge of queues, stacks, and basic algorithm design.

I have chosen to use Guile Scheme as my form of (pseudo)code, as I am familiar with it and it is quite brief. Using an executable language as one’s pseudocode allows for a confirmation of whether specific program flows will work.

In order to keep things brief, I’ve also used global variables and mutability to simplify the assignment and comparison functions. This would be avoided if this were not a pseudocode-level work: The important thing here was to show the algorithms and the program flow, not the overall structure.

And in order to quell confusion, I am using the queue library provided by Guile as my stack and queue objects, rather than implementing my own. For the stack-based operations, I have ensured a LIFO operative restriction remains throughout.

There are four tasks put forth for this milestone:

• 1. Write an algorithm that sets last equal to the last element in a queue, leaving the queue unchanged.

• 2. Write an algorithm to create a copy of myQueue, leaving myQueue unchanged.

• 3. Write an algorithm Replace that takes a stack and two items. If the first item is in the stack, replace it with the second item, leaving the rest of the stack unchanged.

• 4. Write an algorithm Replace that takes a queue and two items. If the first item is in the queue, replace it with the second item, leaving the rest of the queue unchanged.

Last Element of Queue

This is much more straightforward than it was for a Stack, which really does highlight the major difference between a Stack and a Queue: With a queue, You can access the head and the tail.

As we are not changing this queue at all, it is really just two function calls: The first, to return the tail of the queue. And the second, to assign that value to last.

Here is an implementation in GNU Guile:

   (define *last* (q-rear my-queue))

Copy Queue

Rather than using recursion as was needed for the non-destructive stack copy in the previous milestone, we can instead use a simple loop to complete this task.

The basic structure of this algorithm will be to make a new, empty queue, pop the first member of the original queue off, and then enqueue that same member onto both the new and the original structure. This sequence is repeated until both the original queue and the new queue are the same length, at which point the new queue is returned. Storing the return of this algorithm in a variable effectively copies the original queue while leaving it in its original state.

The reason to create a new queue within the algorithm (as opposed to taking a pre-existing, empty queue) is to ensure there is no state transferred in: a new queue will always be empty, whereas a queue that is passed in has the change of not starting as a clean slate.

   (define (copy-q original)
      (let ((members (q-length original))
           (new (make-q)))
       (while (< (q-length new) members)
         (enq! new (q-pop! original))
         (enq! original (q-rear new)))
         new))

Replace Item in Stack

Both of these replace functions are heavily based on the Copy functions formerly presented: What is replacing an item in a stack or queue, aside from making a copy of it, in place, with a specific modification?

For the stack version, we will recurse again, but without the second stack this time: Each item of the stack will be popped off of it until the stack is empty. Then, we’ll push each item back on to the stack, checking at each push whether the item matches our first (original) argument. If it does, we push our second (new) argument instead of the original item, which effectively is discarded.

This leaves us with a stack that has a single item replaced.

   (define (replace-item-in-stack stack original new)
      (let ((curr-value (q-pop! stack)))
       (unless (q-empty? stack)
         (replace-item-in-stack stack original new))
       (if (= curr-value original)
           (q-push! stack new)
           (q-push! stack curr-value))))

Replace Item in Queue

For the queue version of this function, we will base our flow on the copy function presented above.

We will loop through a sequence the same number of times as there are items in the queue. In that sequence, we will pop the first member off of the queue, and compare it to our first (original) argument. If there’s a match, we will then enqueue the second (new) argument instead. Otherwise, we will re-enqueue the member that was popped.

   (define (replace-item-in-queue queue original new)
      (let ((members (q-length queue)))
       (do ((current-member 0 (1+ current-member)))
           ((= current-member members))
         (let ((curr-value (q-pop! queue)))
           (if (= curr-value original)
                 (enq! queue new)
                 (enq! queue curr-value))))))

Conclusion

It’s worth mentioning here how these last two algorithms could be broken down into a few simpler ones: The check could be its own function, as it is always (regardless of whether in the stack or queue version) comparing curr-value to original. We could also make these implementations more functional by building a new data structure within the context of the algorithm and returning it, as opposed to mutating the original functions. There is lots of room for optimization.

This demonstrates the requested tasks in an abstract, algorithmic form, however, and should suffice.