Implementing Lists, Stacks, Queues, and Priority Queues


Download Implementing Lists, Stacks, Queues, and Priority Queues


Preview text

Implementing Lists, Stacks, Queues, and Priority Queues
Paul Fodor CSE260, Computer Science B: Honors
Stony Brook University http://www.cs.stonybrook.edu/~cse260
1

Objectives
 To design common features of lists in an interface and provide skeleton implementation in an abstract class for Collections.
 To design and implement a dynamic list using an array.
 To design and implement a dynamic list using a linked structure.
 To design and implement a stack class using an array list and a queue class using a linked list.
 To design and implement a priority queue using a heap.
2
(c) Paul Fodor (CS Stony Brook) & Pearson

Lists

 A list is a popular data structure to store data in

sequential order For example, a list of students, a list of available rooms,

a list of cities, and a list of books, etc. can be stored

using lists

 The common operations on a list are usually the following:

 Insert a new element to the list

 Delete an element from the list

 Retrieve an element from the list

 Find how many elements are in the list

 Find if an element is in the list

Find if the list is empty 
3

(c) Paul Fodor (CS Stony Brook) & Pearson

Two Ways to Implement Lists
 There are two ways to implement a list:  Using arrays to store the elements: the array is dynamically expanded:  If the capacity of the array is exceeded, create a new larger array and copy all the elements from the current array to the new array  Using linked list consisting of nodes  Each node is dynamically created to hold an element  All the nodes are linked together to form a list
 For convenience, let’s name these two classes: MyArrayList and MyLinkedList
4
(c) Paul Fodor (CS Stony Brook) & Pearson

Design of ArrayList and LinkedList
 The two classes have common operations, but different data fields  The common operations can be generalized in an interface or an abstract class  A good strategy is to combine the virtues of interfaces and abstract classes by providing both interface and abstract class in the design so the user can use either the interface or the abstract class whichever is convenient -> Such an abstract class is known as a convenience class
5
(c) Paul Fodor (CS Stony Brook) & Pearson

MyList Interface and MyAbstractList Class
6
(c) Paul Fodor (CS Stony Brook) & Pearson

public interface MyList extends Iterable { /** Add a new element at the end of this list */ public void add(E e);
/** Add a new element at the specified index in this list */ public void add(int index, E e);
/** Clear the list */ public void clear();
/** Return true if this list contains the element */ public boolean contains(E e);
/** Return the element from this list at the specified index */ public E get(int index);
/** Return the index of the first matching element in this list. * Return -1 if no match. */
public int indexOf(E e);
/** Return true if this list contains no elements */ public boolean isEmpty();
/** Return the index of the last matching element in this list * Return -1 if no match. */
7 public int lastIndexOf(E e); (c) Paul Fodor (CS Stony Brook) & Pearson

/** Remove the first occurrence of the element o from this list. * Shift any subsequent elements to the left. * Return true if the element is removed. */
public boolean remove(E e);
/** Remove the element at the specified position in this list * Shift any subsequent elements to the left. * Return the element that was removed from the list. */
public E remove(int index);
/** Replace the element at the specified position in this list * with the specified element and returns the new set. */
public E set(int index, E e);
/** Return the number of elements in this list */ public int size();
}
8
(c) Paul Fodor (CS Stony Brook) & Pearson

public abstract class MyAbstractList implements MyList { protected int size = 0; // The size of the list

/** Create a default list */ protected MyAbstractList() { }

/** Create a list from an array of objects */ protected MyAbstractList(E[] objects) {
for (int i = 0; i < objects.length; i++) add(objects[i]);
}

/** Add a new element at the end of this list */ public void add(E e) {
add(size, e); // add an element at index size }

/** Return true if this list contains no elements */ public boolean isEmpty() {
return size == 0; }

/** Return the number of elements in this list */

public int size() {

9 return size; }

(c) Paul Fodor (CS Stony Brook) & Pearson

/** Remove the first occurrence of the element * Shift any subsequent elements to the left. * Return true if the element is removed. */
public boolean remove(E e) { int i = indexOf(e); if (i >= 0) { remove(i); return true; } else return false;
}

from

this

list.

}

10
(c) Paul Fodor (CS Stony Brook) & Pearson

Preparing to load PDF file. please wait...

0 of 0
100%
Implementing Lists, Stacks, Queues, and Priority Queues