C++ Ch 19 Stacks and Queues

19.1 - Describe what LIFO means.

19.1 Last-in, first-out. The last item stored in a LIFO data structure is the first item extracted.

19.2 - What is the difference between static and dynamic stacks? What advantages do dynamic stacks have over static stacks?

19.2 A static stack has a fixed size, and is implemented as an array. A dynamic stack grows in size as needed, and is implemented as a linked list. Advantages of a dynamic stack: There is no need to specify the starting size of the stack. The stack automatically grows each time an item is pushed, and shrinks each time an item is popped. Also, a dynamic stack is never full (as long as the system has free memory).

19.3 - What are the two primary stack operations? Describe them both.

19.3 Push: An item is pushed onto, or stored in the stack. Pop: An item is retrieved (and hence, removed) from the stack.

19.4 - What STL types does the STL stack container adapt?

19.4 vector, list, or deque.

The STL stack container is an adapter for the __________, __________, and __________ STL containers.

vectors, lists, and deques

The two ADTs in the Standard Template Library that exhibit queue-like behavior are __________ and __________.

deque and queue

The queue ADT, by default, adapts the __________ container.

deque

Suppose the following operations are performed on an empty stack:
push(0);
push(9);
push(12);
push(1);
Insert numbers in the following diagram to show what will be stored in the static stack after the operations above have executed.

1,12,9,0

Suppose the following operations are performed on an empty stack:
push(8);
push(7);
push();
push(19);
push(21);
push();
Insert numbers in the following diagram to show what will be stored in the static stack after the operations above have executed.

19,8

Suppose the following operations are performed on an empty stack:
enqueue(5);
enqueue(7);
enqueue(9);
enqueue(12);
Insert numbers in the following diagram to show what will be stored in the static stack after the operations above have executed.

12,9,7,5

Suppose the following operations are performed on an empty stack:
enqueue(5);
enqueue(7);
dequeue();
enqueue(9);
enqueue(12);
dequeue();
enqueue(10);
Insert numbers in the following diagram to show what will be stored in the static stack after the operations above have executed.

,9,12,10

What problem is overcome by using a circular array for a static queue?

26. It allows the queue elements to "wrap around" the end of the array. This, in turn, makes the queue more efficient by eliminating the need to copy the queue elements forward each time an item is enqueued.

Write two different code segments that may be used to wrap an index back around to the beginning of an array when it moves past the end of the array. Use an if/else statement in one segment and modular arithmetic in the other.

27. Code segment using an if/else statement:

if (rear == queueSize - 1)
rear = 0;
else
rear++;


Code segment using modular arithmetic:

rear = (rear + 1) % queueSize;