Stacks

CSC 1052 Homework Stacks

1. I am going to execute this code with THREE pushes and ONE pop:

IntStack s = new IntStack( );

s.push(1);

s.push(2);

s.push(3);

System.out.println(s.pop( ));

Suppose that s is represented by a partially filled array. Draw the state of the private instance variables of s after the above code:

______

Count | | data | | | | |

|______| |_ ____|______|______|______|______|...

[0] [1] [2] [3] [4]

2. Assume myStack is an object of Class ArrayStack. You may call any of the public methods of ArrayStack.

Make a copy of myStack, leaving myStack unchanged.

3.Describe the state of an initially empty stack after each of the following sequences of operations. Indicate the values held by any variables that are declared; also indicate any errors that may occur You may assume stk represents a stack of integer objects.

a)

stk.push(new Integer(3));

Object a = stk.pop();
stk.push();
stk.pop();
b.

stk.push(new Integer(3));

stk.push(new Integer(4));
stk.pop();
stk.pop();
Object a = stk.pop();

4. In the linked-list version of the Stack class, which operations require linear time for their worst-case behavior?

  1. is_empty
  2. peek
  3. pop
  4. push
  5. None of these operations require linear time.

For the next questions assume a Stack class stores int values. Consider the following sequence of instructions.

Stack s = new Stack( );

s.push(16);

s.push(12);

s.push(19);

int x = s.pop( );

s.push(5);

s.push(9);

s.push(4);

int y = s.pop( );

int z = s.pop( );

5) After the instructions execute, x has the value

a)16

b)12

c)19

d)0

e)none of the above, the instruction int x = s.pop( ) results in an Exception being thrown

6) After the instructions execute, z has the value

a)4

b)9

c)5

d)12

e)16

7. A Stack s stores int values. Show what s will look like after each of the following instructions is executed.

s.push(5);

s.push(1);

s.push(4);

s.push(3);

s.pop( );

s.push(2);

s.pop( );

s.pop( );

s.push(8);

s.push(7);

s.pop( );

s.push(3);

15. Fill in the execution time for each operation:
Operation Array LinkedList
Push(); O( ) O( )
Pop(); O( ) O( )
Peek();O( ) O( )
Multiple Choice

1..Entries in a stack are "ordered". What is the meaning of this statement?

  1. A collection of Stacks can be sorted.
  2. Stack entries may be compared with the '<' operation.
  3. The entries must be stored in a linked list.
  4. There is a first entry, a second entry, and so on.

2.The operation for adding an entry to a stack is traditionally called:

  1. add
  2. append
  3. insert
  4. push

3. The operation for removing an entry from a stack is traditionally called:

  1. delete
  2. peek
  3. pop
  4. remove

5. Which of the following applications may use a stack?

  1. A parentheses balancing program.
  2. Keeping track of local variables at run time.
  3. Syntax analyzer for a compiler.
  4. All of the above.

6. Consider the following pseudocode:

declare a stack of characters

while ( there are more characters in the word to read )

{

read a character

push the character on the stack

}

while ( the stack is not empty )

{

pop a character off the stack

write the character to the screen

}

What is written to the screen for the input "carpets"?

  1. serc
  2. carpets
  3. steprac
  4. ccaarrppeettss

7.Here is an INCORRECT pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced:

declare a character stack

while ( more input is available)

{

read a character

if ( the character is a '(' )

push it on the stack

else if ( the character is a ')' and the stack is not empty )

pop a character off the stack

else

print "unbalanced" and exit

}

print "balanced"

Which of these unbalanced sequences does the above code think is balanced?

  1. ((())
  2. ())(()
  3. (()()))
  4. (()))()

8. Consider the usual algorithm for determining whether a sequence of parentheses is balanced. Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order). What is the maximum number of parentheses that will ever appear on the stack AT ONE TIME during the computation?

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5 or more

9. Consider the implementation of the Stack using a partially-filled array. What goes wrong if we try to store the top of the Stack at location [0] and the bottom of the Stack at the last used position of the array?

  1. Both peek and pop would require linear time.
  2. Both push and pop would require linear time.
  3. The Stack could not be used to check balanced parentheses.
  4. The Stack could not be used to evaluate postfix expressions.

10. In the linked list implementation of the stack class, where does the push method place the new entry on the linked list?

  1. At the head
  2. At the tail
  3. After all other entries that are greater than the new entry.
  4. After all other entries that are smaller than the new entry.

11 In the array version of the Stack class, which operations require linear time for their worst-case behavior?

  1. is_empty
  2. peek
  3. pop
  4. push when the stack is below capacity
  5. None of these operations require linear time.

QUEUES

Multiple Choice
  1. One difference between a queue and a stack is:
  2. A. Queues require linked lists, but stacks do not.
  3. B. Stacks require linked lists, but queues do not.
  4. C. Queues use two ends of the structure; stacks use only one.
  5. D. Stacks use two ends of the structure, queues use only one.
  6. If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a time, in what order will they be removed?
  7. A. ABCD
  8. B. ABDC
  9. C. DCAB
  10. D. DCBA
  1. Suppose we have a circular array implementation of the queue class, with ten items in the queue stored at data[2] through data[11]. The current capacity is 12. Where does the insert method place the new entry in the array?
  2. A. data[1]
  3. B. data[0]
  4. C. data[11]
  5. D. data[12]
  6. Consider the implementation of the Queue using a circular array. What goes wrong if we try to keep all the items at the front of a partially-filled array (so that data[0] is always the front).
  7. A. The constructor would require linear time.
  8. B. The remove method would require linear time.
  9. C. The insert method would require linear time.
  10. D. The isEmpty method would require linear time.
  1. In the circular array version of the Queue class, which operations require linear time for their worst-case behavior?
  2. A. remove
  3. B. insert when the capacity has not yet been reached
  4. C. isEmpty
  5. D. None of these operations require linear time.
  1. If data is a circular array of CAPACITY elements, and rear is an index into that array, what is the formula for the index after rear?
  2. A. (rear % 1) + CAPACITY
  3. B. rear % (1 + CAPACITY)
  4. C. (rear + 1) % CAPACITY
  5. D. rear + (1 % CAPACITY)
  1. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into a NONEMPTY queue?
  2. A. Neither changes
  3. B. Only front changes.
  4. C. Only rear changes.
  5. D. An exception is caused
  1. Suppose remove is called on a priority queue that has exactly two entries with equal priority. How is the return value of remove selected?
  2. A. One is chosen at random.
  3. B. The one which was inserted first.
  4. C. The one which was inserted most recently.
  5. D. This can never happen (violates the precondition)
  1. An array of queues can be used to implement a priority queue, with each possible priority corresponding to its own element in the array. When is this implementation not feasible?
  2. A. When the number of possible priorities is huge.
  3. B. When the number of possible priorities is small.
  4. C. When the queues are implemented using a linked list.
  5. D. When the queues are implemented with circular arrays.

10. To simulate people waiting in a line, which data structure would you use?

a)Vector

b)Queue

c)Stack

d)Set

e)List

For questions 11- 13, consider the following operations on a Queue data structure that stores int values.

Queue q = new Queue( );

q.enqueue(3);

q.enqueue(5);

q.enqueue(9);

System.out.println(q.dequeue( ));// d1

q.enqueue(2);

q.enqueue(4);

System.out.println(q.dequeue( ));// d2

System.out.println(q.dequeue( ));// d3

q.enqueue(1);

q.enqueue(8);

11. After the code above executes, how many elements would remain in q?

a)0

b)4

c)5

d)6

e)7

12. What value is returned by the last dequeue operation (denoted above with a d3 in comments)?

a)3

b)5

c)9

d)2

e)4

13. If we replace the System.out.println statements (denoted in comments as d1, d2 and d3) with the statement q.enqueue(q.dequeue( )); q would contain which order of int values after all instructions have executed?

a)3, 5, 9, 2, 4, 1, 8

b)3, 5, 9, 1, 8, 2, 4

c)5, 9, 2, 4, 1, 8, 3

d)3, 2, 4, 5, 9, 1, 8

e)2, 4, 1, 8, 3, 5, 9

T/F

1)__The push and enqueue operations are essentially the same operations, push is used for Stacks and enqueue is used for Queues.

2)__Queues and Stacks can be implemented using either arrays or linked lists.

3)___In order to input a list of values and output them in order, you could use a Queue. In order to input a list of values and output them in opposite order, you could use a Stack.

Free Form

1. A Queue q stores int values. Show what q will look like after each of the following instructions is executed.

q.enqueue(6);

q.enqueue(12);

q.enqueue(13);

q.dequeue( );

q.dequeue( );

q.enqueue(19);

q.enqueue(21);

q.enqueue(22);

q.dequeue( );

q.enqueue(20);

2. In implementing a Queue using an array, a problem might arise if the Queue is implemented in such a way that items in the Queue are inserted at the next available location and removed from the next leading position, but such that, once deleted, the emptied space is unused. The problem that arises is one where there is free space still in the array, but it is not usuable because it is not at the end. Demonstrate this problem with a Queue that is stored in an array of size 5 for the following instructions. Next, explain how you might resolve this problem.

Queue q = new Queue(5); // assume the Queue constructor takes 5 as the size of the array

q.enqueue(3);

q.enqueue(4);

q.enqueue(1);

q.dequeue( );

q.dequeue( );

q.enqueue(6);

q.enqueue(5);

q.dequeue( );// at this point, there are only 2 item2 in the queue

q.enqueue(7);// this enqueue can not occur, why??

1