CS 305, Data Structures & Algorithms

Quiz 1, 23 February 2010

  1. Which of the following statements are false:
    1. A stack can implement a priority queue.
    2. A priority queue can implement a stack.
    Justify your answer.

    Statement 1: False. A priority queue doesn’t provide LIFO ordering, while a stack only provides LIFO ordering. Also, a priority queue uses priorities, while a stack doesn’t.

    Statement 2: Not false. If the priority queue stores values in LIFO order, then it’s effectively a stack. The priority queue keeps a separate counter that increases by one whenever a value is added to the queue. Each value added to the queue is assigned the priority shown by the counter. Because the newest value added has the highest priority among all values in the queue, it becomes the queue head, and the values are stored in LIFO order.

    The answers, in no particular order and approximately verbatim:
    1. The first one is false because a stack can only push/pop from the top. A queue can do either push/pop from both ends of the sequence.1 A priority queue can implement a stack because the stack can be acted upon completely by the queue’s methods.2 A stack could not implement a priority queue because it would need to be able to perform actions on the queue as a whole, from either end, which stacks cannot do.

      1: Dequeues can add or remove values at either end, not queues; it’s also not relevant because the question’s about priority queues, not queues.

      2: I don’t think “acted upon” is the phrase you want. Also, how do a priority queue’s methods act like (for example) a stack?

    2. A priority queue cannot implement a stack because a stack is more strict in its implementation.3 A priority queue lists values in the order they are received, meaning the first value inserted is higher than all the others. This logic is counterintuitive4 to a stack because the stack works almost opposite. The first value entered into the stack will the last accessible value.5

      3: Stacks are more strict than what? Priority queues? But why is that a problem for priority queues?

      4: I don’t think “acted upon” is the phrase you want. Also, how do a priority queue’s methods act like (for example) a stack?

      5: Does this answer deal with the statement 2?

    3. A priority queue can implement a stack is false because a priority queue is a more specific call for an ADT.6 A stack can implement a priority7 queue but not the other way around.

      6: What does it mean to be a more specific call?

      7: How is LIFO able to implement priority-queue ordering?

      1. False, a stack cannot implement a priority queue because stacks8 are placed in a specific order. Therefore could not move to create a priority queue because the order would change.
      2. True, a priority queue can implement a stack because each value could be pushed in one by one.9 It would then still be in order of highest priority at the head.10

      8: This should probably be “values”.

      9: That’s always the case for any linked-sequence ADT.

      10: Why is this true? What mechanism makes it so?

    5. A priority queue can implement a stack, but a stack cannot implement a priority queue. This11 is because the functions within a priority queue cannot be implemented,12 as they hold no references that would be necessary for implementation.13

      11: The previous sentence makes two claims; to which is “this” referring?

      12: Which priority-queue functions can’t be implemented, and where can’t they be implemented (the stack presumably).

      13: This takes care of stacks implementing priority queues (I guess); what about the other way around?

    6. The first statement is false because a priority queue can implement a stack by doing descending order of priority, essentially doing it backwards and having the most “important” highest priority element be last and therefore implementing the “FILO”14 behavior, or a stack. However, stacks are stubborn in that they can’t be changed from this FILO behavior and therefore could never implement a priority queue since it is a “FIFO” behavior.15

      14: Ha, FILO; I like it.

      15: Neither stacks nor priority queues have FIFO behavior, although priority queues could be made to have it.

    7. 1 is false. In order to implement an interface,16 the child class has to have all methods from the interface. This would mean your stack would have to implement all methods from queue,17 which would not be possible since queues must access the tail of the sequence and stacks are not allowed to do that.18

      16: And not be an abstract class.

      17: Priority queue.

      18: That’s true, but not too relevant because priority queues effectively insert anywhere in the queue due to priority ordering. Also, what about question 2?

    8. 1 is false. A priority queue allows for more dynamic traversal and less rigid value store.19 Thus, it cannot be implemented by a stack.20

      19: What does it mean for a value store to be less rigid?

      20: What about statement 2?

    9. The statement, a stack can implement a priority queue is false due to the fact that stacks are in a specific order (LIFO)21 while a priority queue places the higher priority objects at the top of the list. Priority queues rearrange stack order, and stacks can’t place priority on its values.22

      21: You mean that values in the stack are in a specific order.

      22: What about statement 2?

    10. Statement 1 is false. A stack cannot implement a priority queue. A stack is defined as being able only to push and pop from the top of the stack only. A priority queue is a queue which means what goes in first comes out first23 or you push in one end and pop from the other. Since a stack can only add and remove values from one end, it cannot implement any kind of queue which requires the ability to manipulate both ends of an array/linked list.24

      23: What about priority?

      24: What about the second statement?

    11. 1 is false. A stack can only add or remove the last element of its array. A priority queue can pick out the elements in any order it so chooses.25

      25: What about the second statement?

    12. 1. a stack can implement a priority queue is false because one of a stack’s properties is to add at the top whereas priority queues get from high priority (lower number) to low priority (high number) and values can be added anywhere by assigning the value the fitting priority number.26

      26: What about the second statement?

    13. A priority queue cannot implement a stack. It is very hard to determine why because the 2 seem to be very similar in nature.27 A stack has the ability to push and pop as well as the priority queue, but it seems that the priority queue would not have the functionality of a stack.28

      27: Also because a priority queue can implement a stack.

      28: What about the second statement?

  2. A sequence of 25 queue operations contains ten enqueue()s, seven see()s and eight dequeue()s in some unspecified order (and, in particular, not in the order given in this sentence). When the sequence is applied to an initially empty queue, all of the enqueue()s were successful, three of the see()s failed with a queue underflow and the rest were successful, and three of the dequeue()s failed with a queue underflow, the rest were successful. Assuming the errors were ignored, how many values where in the queue at the end of the sequence? Explain your answer.

    see() method calls don’t change the number of values in the queue and can be ignored. Three of the dequeue() method calls fail on an empty queue, which doesn’t change the queue; the other five calls remove an element each from the queue. All the enqueue() method calls succeed, adding ten elements to the queue. Ten go in, five come out, and five are left. The answers, in no particular order and approximately verbatim:

    1. Six operations were done on an empty queue. That leaves 19 operations left. Four of those are see()s, which do not affect the value count. Ten are enqueue()s and five are dequeue()s, which leaves five (5) values in the end.
    2. At the end of the sequence these was 1 value left. The enqueues added 10 values to the sequence. Having “queue underflow” means that the operation was trying to remove values from an already empty sequence. So, since 4 see()s were successful and 5 dequeue()s were successful this means 91 were removed from the 10 enqueues that were added to the sequence.

      1: A see() call doesn’t remove anything from the sequence.

    3. If three see()s and three dequeue()s were unsuccessful due to a queue underflow and the other methods were successful, then 5 values were in the queue once the sequence ended.

      Because the queue was initially empty we can go through, followed by enqueue() adding 10 values to the queue, with dequeue() successfully removing 5 once the queue was not empty.

    4. We start with n (number of values) = 0, then we insert 10 values successfully so n = 10. The see()s that were successful do not add or remove values so n is still 10. Only 5 of the dequeue()s succeeded, so 5 values were removed from the sequence, so n = 10 - 5 which means n = 5.
    5. There are 5 values at the end of the sequence because the enqueue()s and dequeue()s will end up canceling out2 and the see() is only to view the value at the top of the queue at the time.

      2: All of the dequeue()s cancel?

    6. About 5,3 because all 10 enqueues were successful but only 5 dequeues worked out of the 8.

      3: Plus or minus how many?

    7. If the queue was empty at the start and all of the enqueue()s were successful, we have 10 values. see() is a queue method and does not change the values. If 3 of the dequeue()s failed, 5 went through, giving us 15 values at the end of the sequence.4

      4: dequeue()s remove values; it should be 10 - 5 not 10 + 5.

    8. The queue would contain 5 values at the end of the sequence. Since there was a queue underflow at the time of the see()s and dequeue()s fail with a queue underflow, the queue had nothing to be seen or removed. Since the 10 enqueues were successful and the other 5 dequeues succeeded, by any combination of the sequences,5 five values would be removed, leaving 5. The see()s do not affect how many values are contained in the queue, merely peek inside.

      5: Any sequence not causing queue underflow.

    9. At the end of the queue it appears that there were 5 values. I say this because 5 dequeues worked, which would have taken whatever value that was enqueued (and at the head) out. Although only 4 see()s worked that doesn’t matter because it all depends on when the see() was called. For example the see() could have been looking for v, but v had just been dequeued before the see().6

      6: An see() don’t look for particular values, it just returns the sequence head, if it exists.

    10. At the end of the sequence, there were 5 values left in the queue because if you put in 10 values and attempted to take out 8 values, but only successfully took out 5 (because 3 dequeues failed), that leaves you with 5 values. The see()s do not effect the values in the queue, they only look at them.
    11. 5. In order to get 3 failed see()s and dequeue()s due to underflow the sequence must have been executed7 as such: enqueue, dequeue x 2, see, enqueue, dequeue x 2, see, enqueue, dequeue x 2, see, enqueue x 7, see x 4, dequeue x 2. Leaving 5 values remaining and all criteria met.

      7: It’s not clear why this sequence is necessary.

    12. There were 5 values left in the queue at the end of the sequence. Every enqueue adds a value to the queue and there were a max of 10 values that could possibly be in the queue. The see() method does not add or remove any values so it does not matter how many times it is called. There were 8 dequeues called which could remove up to 8 values, however 3 of them failed, therefore 5 were executed removing 5 of the 10 values in the queue leaving us with 5 remaining values.
    13. There must be 5 values at the end of the sequence. 10 adds and 8 removes leaves 2 values if there are 0 errors. Since there were 0 overflow errors all 10 values get added to the sequence at some point. Because there are 3 underflow errors that means only 5 values were actually removed and the other 3 dequeues didn’t remove any values because there were none to remove. 10 adds - ( 8 removes - 3 errors ) - 5.8

      8: And what about see()s?

  3. The method String whatADT(LinkedSequence ls) accepts an instance of a class implementing the linked-sequence interface, and returns a string describing the linked-sequence ADT implemented: "stack", "queue", or "linked list". Describe the smallest sequence of linked-sequence method calls that will determine if ls is a stack, a queue, or a linked list. Justify your answer. Assume ls is empty when passed into whatADT().

    Adding one element can’t distinguish anything. Adding a second, distinguished element differentiates queues: the head of the ADT will be the first element added. Adding an element after the first element distinguishes between stacks and linked lists: linked lists allow the addition and stacks don’t. The code sequence is 

    ls.insertAfter(null, 1)
if !ls.insertAfter(1, 2), return "stack"
if ls.insertAfter(1, 3), return "linked list"
return "queue"

    The answers, in no particular order and approximately verbatim:

    1. isEmpty() - check if it is empty.1
      add(T w)2 - add a value w of type T.
      push(T v) - add a value v of type T
      enqueue(T z) - add a value z of type T
      has(T w || z || v) - check if value w or z or v is return value. w if linked list. z if queue. v if stack.3

      1: Why? You can assume that.

      2: Is this a linked-sequence method?

      3: Perhaps you mean if has() == w,return "linked list"?

      • Add three values to the ADT.
      • Attempt to read 2nd value.
      • if you can’t, return stack.4
      • if you can, delete the first value
      • if you can’t delete the first value, return queue5
      • else return linked list
      • Delete all remaining values in appropriate manner.

      4: But you can’t read the 2nd value of a queue either. And how do you read the second value using linked-sequence methods?

      5: How can you not delete the first element?

    3. I would say the smallest sequence of method calls would be insertAfter(), enqueue(), and pop(). I chose these three because each has to do with a different linked sequence. If insertAfter does not give an error then ls would be a linked list because you can only insert after a random value in the sequence if it is a linked list.6 That leaves the other two methods,7 if enqueue() is called and value 2 is placed into the list and pop() is called, but returns value 2. Then you know it is a stack because enqueue placed 2 at the head. Queues go by FIFO and stacks go by LIFO.

      6: Why is it that insertAfter not failing mean that ls is a linked list?

      7: Are these linked-sequence methods?

    4. The easiest to determine would be the stack as by rule, only the value stored at the top can be accessed at any given time.8 boolean insertAfter(old, new) is an easy give away to stack because the only time you can “insertAfter” in a stack is when the old (top) value is null, in other cases the method returns false,9 meaning nothing can be isolated. Remove() can also determine this by the same properties.

      A linked list is less restrictive as one can fetch all values in the linked list. We can see this by checking remove(v). In a linked list we can cycle through all values in the list, find the value, remove it, and reset the pointers.

      A queue is similar to a stack only it contains FIFO properties. Give the top of the queue will be the first value is searched calling the see() method will return the first value inserted into the queue, not the last value.

      8: But isn’t that true for queues too?

      9: Is that how insertAfter() works? Can’t you insert after null for any linked-sequence ADT?

      1. insertAfter(null, value)
      2. insertAfter(value, value2)
        • will return false if ls is a stack because stacks do not support arbitrary insertions at random points.
      3. insertAfter(value, value3)
        • Will return false if ls is a queue because queues will only let the head and tail be changed, not the middle.
        • If neither of these returned false, then ls is a linked list since it supports insertion at every value.
      100
    6. You could call see() because you know that an empty linked list will be null10 where as a stack refers to the links between the indexes and is instantiated with a zero.11 You could also call size to get similar conclusions.12 75

      10: Won’t calling see() on any empty linked-sequence ADT return false?

      11: What?

      12: How? Won’t calling size() on any empty linked-sequence ADT return 0?

    7. whatADT() could possibly determine the ADT implemented by using methods that insert values into the otherwise empty ls and subsequently determine the ADT by checking the way in which a value is removed. Linked lists, for example will insert the values in the order they were entered13 and remove them by taking away the farthest one. Queues and stacks both insert values from the left side14 but differ in the way they are removed. Stacks are first in, first out whereas queues are last int, first out.15 Using a method to see how the values were implemented would ultimately determine the type of ADT.16 75

      13: That’s one possibility, but linked lists can insert values at any point in the list.

      14: Aren’t queues double-ended?

      15: Other way around: stacks are LIFO and queues are FIFO.

      16: Yes, but how? That’s the question.

    8. The smallest linked-sequence call that will determine if “ls” is a stack, a queue, or a linked list would be to call all of the methods17 to show you the variable.18 That way, it’ll show you the elements and whether it’s a stack, a queue, or a linked list. 75

      17: All of them? In what order? How do you interpret the results?

      18: What variable? ls?

    9. What one can do to determine if ls is a stack, a queue, or a linked list is to try to add the items before/after values in the middle of the sequence because that cannot be done is a stack or a queue. To determine the difference between a stack and a queue would be to add strings and remove them.19 Depending on the order they are removed in determines which ADT it is. Stacks are last in first out, queues are first in first out.

      19: What would go wrong if I tried to add and remove ints?

    10. To determine whether ls is a stack, queue or linked list first determine the methods used to add/remove values into the ADT.20 Each ADT has a specific method call so if you call add()21 and it doesn’t respond or reads as an error you know it is not linked list, therefore you call push and whether or not you get an error message will determine the ADT. So at most you need two method calls.

      20: Isn’t that insertAfter() and remove() for all linked-sequence ADTs?

      21: Is add() a linked-sequence method?

      • The first method insertAfter(), would determine if it is a linked list. If it works, it is a linked list. If it doesn’t it is either a queue or a stack.22
      • The method push()23 followed by another, and then a pop() would tell if it is a (LIFO) or a (FIFO) by using see(). If it is a LIFO, it is a stack. If it is a FIFO, it is a queue.

      22: But calling insertAfter(1, 2) on an empty linked list fails too.

      23: Is push() a linked-sequence method?

    12. You can use the method insertAfter(E old, E v) to determine what type of ADT is being used because if you pass in 2 arguments in this method, as opposed to 1 null and 1 argument, a stack | queue will return false for the method and a linked list would return true and insert the arguments into the ADT. (A stack | queue will return false because they can’t insert values between other values, only at one end of the ADT or the other.) To then determine if it is a stack or a queue, insert 2 values using the insertAfter() method,24 and then use the see() method. If the see method returns the first value inserted, it is a queue, if the see() method returns the second value inserted it is a stack, because stacks only have access to the top value.

      24: Insert them how? Presumably using null as the first argument.

    13. Call insertAfter(null, 1), then insertAfter(1, 2). If insertAfter(1, 2) returns true then it is a linked list because they are the only ones that let the user do an insert after a value. If it returns false then it must be a stack or queue. Continue with 

      insertAfter(null, 2)
remove(1);

      If remove(1) returns true it is a queue because it was the first value in, so it would be the first value allowed out of a queue. If it were a stack it would return false because stacks may only remove from the top of the stack which in this case would be 2.

  4. Many applications support an undo operation, which undoes the results of previous commands. Which of the linked-sequence ADTs is most appropriate for storing command undo information? Justify your answer.

    The most recently operation performed should be the operation undone; this is LIFO order and a stack is called for.

    1. A linked list using nodes would be the best choice to have an undo command if the program recycles.1 If you remove a node and recycle it, it is put onto a free list and only the pointers are changed. In order to undo that the program would have to just change the pointers back to where they were pointing before the remove command.2 If a new node was inserted and wanted to be undone the undo command would again just change the pointers back to before the command was made and put the node that was inserted into the free list to be recycled.

      1: Recycles what?

      2: How would the program know where the pointers pointed before?

    2. I think a stack ADT would be the most appropriate for storing command undo information because of its strictness with entering values and because of its FILO behavior. If you store undo commands in a stack, the first undo command will be the last to be accessed and the most recent undo command will be the one that is available on the top of the ADT, which makes sense because it wouldn’t be logical to look at an undo command that you did 5-undo-commands-ago be cause it wouldn’t match up which what your program | application is currently at. The strictness of stacks also helps this because it prevents users from jumping around the undo commands and having access to all of them at once, potentially causing confusion to themselves.3

      3: This is a good answer, but it’s way too long.

    3. A linked list would benefit best from an undo operation because it is an ADT where every element can be acted upon. A stack or queue can only act upon the first or last element, making an undo operation superfluous.4

      4: Not a good answer, but the explanation saved it.

    4. Queues are the best for storing the command undo information due to the fact that they can store values at both ends of the sequence, thus it is easier to undo what was done,5 and it is much faster because it has access to the head and tail.6

      5: Why is easier to undo what was done of values are stored at both ends?

      6: What is the it that is quick and has access?

    5. A stack ADT because after adding a value using push(), the only that you can do to undo or remove the value that was added is to pop() it out and it will remove the value from your sequence.7 You do not have to reference the value that you want to undo because pop() removes the last value that was added to the sequence.8

      7: True, but why is this useful behavior? Why isn’t queue behavior as useful?

      8: True, but why is referencing values important to undoing commands?

    6. A stack. A stack uses the “push()” command, which adds an element to the array, and the “pop()” command, which removes the last element added to the array.9

      9: True, but why is that behavior useful for undoing commands?

    7. The most appropriate linked-sequence ADT to use for storing command undo information would be a linked list. this is because a singly-linked list has the ability to move within the ADT, thus allowing for easier retrieval of command undo information. Using the linked list would allow for the application to access previous actions stored while removing recently added nodes.10

      10: This answer is rather more about undoing than about ADTs, but it’s still a good answer.

    8. It seems that linked lists would be very hard to implement an undo operation because of the fact that you replace the pointer value each time you move a node, without storing the previous value of the pointer.11 Queues seem to be a bit easier because you can enqueue or dequeue which makes for fewer options and possibly easier reversal of the operations.12

      11: But why would you want to do that?

      12: But do queues present command undo information in the order you would want to use them?

    9. I think the keyword here is ‘previous.’13 We want to be able to quickly access the previous command. I believe double-linked lists would be best because each element carries not only the next element, but the previous element, making it easily accessible.14

      13: True, but on the other hand, the only commands you can undo are commands which have been executed, and these are necessarily previous commands.

      14: True, but how does that help in undoing commands?

    10. A stack would be most appropriate for containing an undo operation because it’s use is the simplest.15 Since only one element can be seen or touched at a time, a basic undo command would be simple. Suppose the wrong value was inserted into the stack. The undo command would simply pop the value last entered (LIFO) and return it to the user. The same could be applied to accidentally popping a value.

      15: Simplest in what way? To operate or to implement?

    11. The doubly linked list would be most appropriate for storing command undo information because it is the only linked sequence that gives you the option of next and previous. You can use the previous value without going all the way through the list again.16

      16: True, but why is that an important property to have when implementing command undo?

    12. An undo could be implemented very easily in a stack. the pseudocode could look something like:17 

      if user used the push command18
  pop value pushed
else if user used the pop command
  push value popped
else 
  return

      17: But how does the code know the user used the push command. This is what’s known as “begging the question.”

      18: I could write similar pseudocode for a queue: just replace “push” with “enqueue” and “pop” with “dequeue”. Why is this harder than a stack?

    13. Stack because it is the most expensive and time consuming to fix errors19 over the other ADTs.20

      19: Why are stacks most expensive? Expensive in what way?

      20: Why is it appropriate to be the most expensive and time consuming ADT to use?

This page last modified on 2 March 2010.