ADS2 2021 1 Lab Sheet 3
Algorithms and Data Structures (ADS2)
Laboratory Sheet 3
This lab sheet contains material based on Lectures 10-12. This exercise is not assessed but
should be completed to gain sufficient experience in the implementation of elementary
abstract data types, and the testing thereof.
Exercise
You are to implement the Dequeue abstract data type (ADT) using two different data structures.
Then, you will use this ADT to define generic Stack and Queue ADTs. Finally, you will use a
stack to implement a non-recursive quicksort.
Part 1
a) Implement in Java the merge sort algorithm for linked lists introduced in Lecture 10
(slide 36). Use the following class structure to implement linked lists.
public class LinkedList<Item>{
private Node<Item> head;
private static class Node<Item>{
private Item key;
private Node<Item> next;
}
public LinkedList(){
head = null;
}
…
Part 2
a) Implement in Java the Dequeue abstract data type introduced in Lecture 12 (slide 35).
Use resizable arrays in a circular fashion (slide 26) in the class below. What is the time
complexity of each operation (i.e. PUSH-BACK, PUSH-FRONT, POP-BACK, POPFRONT)?
public class ResizingDequeue<Item>{
private Item[] q;
private int n; // number of elements in the dequeue
private int tail;
private int head;
public ResizingDequeue (){
q = (Item[]) new Object[2];
n = 0;
head = 0;
tail = 0;
}
…
ADS2 2021 2 Lab Sheet 3
b) Implement the Dequeue abstract data type using a circular doubly linked list. Modify
the class structure given in 1a for singly linked lists to include prev pointers and a
sentinel. What is the time complexity of each operation?
Part 3
a) Implement the Stack ADT using the Dequeue you implemented in 2b.
b) Implement the Queue ADT using the Dequeue you implemented in 2b.
c) Implement the Queue ADT using two stacks. What is the time complexity of each
operation?
Part 4
Using an auxiliary stack, implement an iterative version of quicksort. To reduce the stack size,
first push the indexes of the smaller subarray.