CSE 1384 Intermediate Programming, Fall 2018

Homework 3, Stack/Queue Problems

Instructions:

Answer the following questions and submit your answers as a .pdf by 9/21/2018 before 12:00 a.m. You may work together on these assignments, but every student is required to submit a copy of their work. Provide the NetIDs of the group members you worked with. If you have any questions, contact the instructor or TAs or meet during office hours/by appointment.

1. Answer True/False for the following statements (4 points each):

a. The Stack follows the LILO principle.

b. The Queue follows the FIFO principle.

c. The Deque follows the FILO principle.

d. The Stack needs two references to achieve a worst case complexity of O(1).

e. The Queue needs two references to achieve a worst case complexity of O(1).

f. The Stacks always adds a node to the top.

g. The Queue always adds a node to the top.

h. The Deque only adds to one place in the structure.

i. The Deque can remove any node in the structure, the first, last or any middle node.

j. The Deque is considered a hybrid of the stack.

2. Demonstrate the following operations on an empty stack. DO NOT simply show the final stack diagram, show what the stack looks like after each operation.

a. Push(20)

b. Push(30)

c. Pop()

d. Push(20)

e. Push(30)

f. Push(1)

g. Push(5)

h. Pop()

i. Push(8)

j. Push(16)

3. Demonstrate the following operations on an empty queue. DO NOT simply show the final stack diagram, show what the stack looks like after each operation. a. Enqueue(20)

b. Enqueue(30)

c. Dequeue()

d. Enqueue20)

e. Enqueue(30)

f. Enqueue(1)

g. Enqueue(5)

h. Dequeue()

i. Enqueue(8)

j. Enqueue(16)

4. Demonstrate the following operations on an empty deque. DO NOT simply show the final stack diagram, show what the stack looks like after each operation. a. Add_Front(20)

b. Add_Front(30)

c. Remove_Back()

d. Add_Back(20)

e. Add_Back(30)

f. Add_Front(1)

g. Add_Front(5)

h. Remove_Front()

i. Add_Back(8)

j. Add_Back(16)