Stacks and Queues Flashcards
Describe a Stack
Container of objects with a last in first out (LIFO) policy
What ordering do stacks follow?
LIFO (last in first out)
What methods are needed to implement a stack?
- push
- pop
- top
- size
- isEmpty
- clear
What exception will the push method in stack throw?
StackOverflowException
What exception will the pop and top methods in stack throw?
StackEmptyException
What are some test cases for stack?
- Creating a new stack
- Push on element
- Push on element then pop
- Pop an empty stack
- Push two elements
- Clear
What are the two ways you could implement a stack?
Linked list
Unsorted arrays
State some applications of stacks
- Reversing a list
- Evaluating reverse Polish expression
- Executing programs
- Web browser history
Write the basis of code for a pop method
if(isEmpty()){
throw new StackEmptyException();
ListNode node = list.getNode(0);
list.remove(node);
return node.element;Write the basis of code for a push method
list.insertAfter(element,null)
What are the two main methods in stack?
Push and pop
What are the complexities of all the stack methods apart from clear?
Constant
Describe a queue
A container of objects with a first in first out (FIFO) policy
What is the only available element in a queue?
The one added earliest
What is the only available element in a stack?
The first element
What are the methods required for implementing a queue?
enqueue dequeue front size isEmpty clear
State some of the test cases for JUnit testing of a queue
- Create a new queue
- Queue an element
- Queue an element then remove
- Remove from an empty queue
- Queue two elements
- Clear a queue
What are the two ways that a queue can be implemented?
Linked list
Unsorted array
Write the basis for an enqueue method
if(current_size < elements.length){
elements[(front+current.size++)%elements.length] = element;
}else{
throw new QueueFullException();
}Write the basis for a dequeue method
if(!isEmpty()){
currentSize--;
return elements[(front++ % elements.length)];
}else{
throw new QueueEmptyException();
}Give some applications for queues
- Decouple threads passing data between them
- Producer/Consumer problems
- Operating systems (ready_queue)
What is the complexity of all the queue methods apart from clear?
Constant
