Stacks and Queues

Question 1

Describe a Stack

Answer 1

Container of objects with a last in first out (LIFO) policy

Question 2

What ordering do stacks follow?

Answer 2

LIFO (last in first out)

Question 3

What methods are needed to implement a stack?

Answer 3

• push
• pop
• top
• size
• isEmpty
• clear

Question 4

What exception will the push method in stack throw?

Answer 4

StackOverflowException

Question 5

What exception will the pop and top methods in stack throw?

Answer 5

StackEmptyException

Question 6

What are some test cases for stack?

Answer 6

• Creating a new stack
• Push on element
• Push on element then pop
• Pop an empty stack
• Push two elements
• Clear

Question 7

What are the two ways you could implement a stack?

Answer 7

Linked list

Unsorted arrays

Question 8

State some applications of stacks

Answer 8

• Reversing a list
• Evaluating reverse Polish expression
• Executing programs
• Web browser history

Question 9

Write the basis of code for a pop method

Answer 9

if(isEmpty()){
   throw new StackEmptyException();
ListNode node = list.getNode(0);
list.remove(node);
return node.element;

Question 10

Write the basis of code for a push method

Answer 10

list.insertAfter(element,null)

Question 11

What are the two main methods in stack?

Answer 11

Push and pop

Question 12

What are the complexities of all the stack methods apart from clear?

Answer 12

Constant

Question 13

Describe a queue

Answer 13

A container of objects with a first in first out (FIFO) policy

Question 14

What is the only available element in a queue?

Answer 14

The one added earliest

Question 15

What is the only available element in a stack?

Answer 15

The first element

Question 16

What are the methods required for implementing a queue?

Answer 16

enqueue
dequeue
front
size
isEmpty
clear

Question 17

State some of the test cases for JUnit testing of a queue

Answer 17

• Create a new queue
• Queue an element
• Queue an element then remove
• Remove from an empty queue
• Queue two elements
• Clear a queue

Question 18

What are the two ways that a queue can be implemented?

Answer 18

Linked list

Unsorted array

Question 19

Write the basis for an enqueue method

Answer 19

if(current_size < elements.length){
   elements[(front+current.size++)%elements.length] = element;
}else{
   throw new QueueFullException();
}

Question 20

Write the basis for a dequeue method

Answer 20

if(!isEmpty()){
   currentSize--;
   return elements[(front++ % elements.length)];
}else{
   throw new QueueEmptyException();
}

Question 21

Give some applications for queues

Answer 21

• Decouple threads passing data between them
• Producer/Consumer problems
• Operating systems (ready_queue)

Question 22

What is the complexity of all the queue methods apart from clear?

Answer 22

Constant