Stacks and Queues

Question 1

Name 3 places where stacks are directly applied and why they are suitable for these tasks

Answer 1

1. Undoing in a text editor. Because the last change is the one you’d mostly want to disappear the stack works efficiently in popping the last change you made
2. History in browser, the last page you visited will be the first one the is accessible.
3. A chain of methods in the JVM

Question 2

How does recursion happen with the JVM?

Answer 2

• JVM keeps track of all the active methods by pushing in a frame containing the local variables and the return values in the stack. The program counter will keep track of the statement being executed.
• WHen a method is finished, it’s frame will be popped off the stack and control goes to the method that is at the top of the list.

Question 3

What is the performance and limitation of the array based stack

Answer 3

• space is O(N), with N being the size of the array
• Operations run at O(1)
• limitations is that the size of the stack has to be determined before, it is not dynamic

Question 4

Name 3 direct applications of queues

Answer 4

1. shared resources
2. waiting lists
3. multiprogramming (a computer running 2 or more opertation/ programs at the same time)

Question 5

performance and limitation of the array based queue

Answer 5

• enqueue is O(1) and dequeue is O(1)