Stacks and Queues

Question 1

Stacks

Answer 1

A stack of data. Last-in first-out ordering. It uses pop, push, peek and isEmpty. No constant-time access to ith item, but constant-time for adds and removes. Good for recursive algorithms.

Question 2

pop()

Answer 2

Remove the top item from a stack

Question 3

push(item)

Answer 3

Add an item to the top of the stack

Question 4

peek()

Answer 4

Return the top of the stack or first in the queue

Question 5

isEmpty()

Answer 5

Return true if and only if the stack/queue is empty.

Question 6

Implementing a stack

Answer 6

A Stack class contains a static StackNode inner class with data and next fields. The Stack class contains a top field, and a pop, push, peek and isEmpty method. They can be implemented as linked list if items are added and removed from the same side: null .– node 1 .– node 2 .– … .– top

Question 7

implement pop()

Answer 7

Ensure stack is not empty. Collect top node’s data. Set top to top.next. Return popped data.

Question 8

implement push()

Answer 8

Create new node. Set new node next to top. Set top to new node.

Question 9

implement peek()

Answer 9

Ensure stack or queue is not empty. return top.data or first.data.

Question 10

implement isEmpty

Answer 10

return true if top or first is null.

Question 11

Queue

Answer 11

First-in first-out ordering. Items are removed from the data structure in the same order that they are added. It uses add, remove, peek, and isEmpty methods. Good for caches and breadth first searches.

Question 12

add(item)

Answer 12

Add an item to the end of the queue

Question 13

remove()

Answer 13

Remove the first item from the queue

Question 14

Implementing a queue

Answer 14

A queue class contains a inner static QueueNode class with a data and next field. The Queue class has first and last fields and add, remove, peek and isEmpty methods. A queue can be implemented as a linked list with items added and removed from opposite sides: first–>1–>2–>…–>last–>null.

Question 15

Implement add(item) (Linked Lists)

Answer 15

Create new node. If last not null, last.next is new node. Last becomes new node. If first is null, first becomes last.

Question 16

Implement remove() (Linked List)

Answer 16

Ensure queue is not empty. Collect first.data. Set first equal to first.next. If first is now null, set last to null. Return collected data.