EECE 330 Chapter, Fall 2011

EECE 330 Data Structures & Algorithms Doubly-Linked Lists Doubly-Linked Lists Stacks & Queues Stacks & Queues © Hassan Artail American University of Beirut Doubly Linked Lists Simplify insertion and deletion: Add a prev pointer. // Doubly-linked list link node template <class Elem> class Link { public: Elem element; // Value for this node Link *next; // Pointer to next node Link *prev; // Pointer to previous node Link(const Elem& e, Link* prevp =NULL, Link* nextp =NULL) { element=e; prev=prevp; next=nextp; } Link(Link* prevp =NULL, Link* nextp =NULL) { prev = prevp; next = nextp; } }; Doubly Linked Lists Doubly Linked Insert Doubly Linked Insert // Insert at front of right partition template <class Elem> bool LList<Elem>::insert(const Elem& item) { fence->next = new Link<Elem>(item, fence, fence->next); if (fence->next->next != NULL) fence->next->next->prev = fence->next; if (tail == fence) // Appending new Elem tail = fence->next; // so set tail rightcnt++; // Added to right return true; } Doubly Linked Remove Doubly Linked Remove // Remove, return first Elem in right part template <class Elem> bool LList<Elem>::remove(Elem& it) { if (fence->next == NULL) return false; it = fence->next->element; Link<Elem>* ltemp = fence->next; if (ltemp->next != NULL) ltemp->next->prev = fence; else tail = fence; // Reset tail fence->next = ltemp->next; // Remove delete ltemp; // Reclaim space rightcnt--; // Removed from right return true; } Dictionary Often want to insert records, delete records, search for records. Required concepts: • Search key: Describe what we are looking for • Key comparison – Equality: sequential search – Relative order: sorting • Record comparison Comparator Class How do we generalize comparison? • Use ==, <=, >=: Disastrous • Overload ==, <=, >=: Disastrous • Define a function with a standard name – Implied obligation – Breaks down with multiple key fields/indices for same object • Pass in a function – Explicit obligation – Function parameter – Template parameter Comparator Example class intintCompare { public: // static functions so they can be used without // having an instantiated object (see later slides) static bool lt(int x, int y) { return x < y; } static bool eq(int x, int y) { return x == y; } static bool gt(int x, int y) { return x > y; } }; Comparator Example (2) class Payroll { public: int ID; char* name; }; // The examples below only show the lt method for brevity class IDCompare { public: static bool lt(Payroll& x, Payroll& y) { return x.ID < y.ID; } }; class NameCompare { public: static bool lt(Payroll& x, Payroll& y) { return strcmp(x.name, y.name) < 0; } }; Dictionary ADT // The Dictionary abstract class – Template (interface) parameters: // Key=search key: record, record element, or record sub-element // Elem=record: simple element or a group of elements // KEComp=key to record or sub-record comparator // EEComp=record to record (sub-record to sub-record) comparator template <class Key, class Elem, class KEComp, class EEComp> class Dictionary { public: virtual void clear() = 0; virtual bool insert(const Elem&) = 0; virtual bool remove(const Key&, Elem&) = 0; virtual bool removeAny(Elem&) = 0; virtual bool find(const Key&, Elem&) const = 0; virtual int size() = 0; }; Comparator Example A Dictionary that contains Employee Records: First Name // string Last Name //string Address //array of strings Position //integer (code) Years of Service //short integer … KEComp: Years of Service comparison (with the supplied Key) Compares two integers (eq, gt, lt) EEComp: Employee Record comparison, used to detect identical records it suffices to compare first names and last names Application: produce a list of employees who are eligible for retirement (based on years of service) but exclude duplicate records Comparator Example (2) A Dictionary that contains Employee Records: First Name // string Last Name //string Address //array of strings Position //integer (code) Years of Service //short integer … KEComp: Position comparison (same as in the previous example) EEComp: Last Name comparison (different than the previous example) Application: produce a list of employees who are eligible for a bonus and sort it by last name Unsorted List Dictionary template <class Key, class Elem, class KEComp, class EEComp> class UALdict : public Dictionary<Key,Elem,KEComp,EEComp> { private: AList<Elem>* list; public: bool remove(const Key& K, Elem& e) { for(list->setStart(); list->getValue(e); list->next()) if (KEComp::eq(K, e)) { list->remove(e);// ::AList remove method return true; } return false; } }; Moves the fence Removes from the right of the fence Note that we are not passing the value of e to remove(). The function remove() supplies us with the value It is the same value obtained from getValue() above Stacks LIFO: Last In, First Out. Restricted form of list: Insert and remove only at front of list. Notation: • Insert: PUSH • Remove: POP • The accessible element is called TOP. Array-Based Stack // Array-based stack implementation template <class Elem> class AStack: public Stack<Elem> { private: int size; // Maximum size of stack int top; // Index for top element Elem *listArray; // Array holding elements public: AStack(int sz =DefaultListSize) { size = sz; top = 0; listArray = new Elem[sz]; } ~AStack() { delete [] listArray; } void clear() { top = 0; } Array-Based Stack (2) bool push(const Elem& item) { if (top == size) return false; // full else { listArray[top++] = item; return true; } } bool pop(Elem& it) { // Pop top element if (top == 0) return false; else {it = listArray[--top]; return true;} } // Return top element bool topValue(Elem& it) const { if (top == 0) return false; else {it = listArray[top-1]; return true;} } int length() const { return top; } Linked Stack (1) template <class Elem> class LStack: public Stack<Elem> { private: Link<Elem>* top; // Pointer to first elem int size; // Count number of elems public: LStack(int sz =DefaultListSize) { top = NULL; size = 0; } bool push(const Elem& item) { top = new Link<Elem>(item, top); size++; return true; } Linked Stack (2) bool pop(Elem& it) { if (size == 0) return false; it = top->element; Link<Elem>* ltemp = top->next; delete top; top = ltemp; size--; return true; } bool topValue(Elem& it) const { if (size == 0) return false; it = top->element; return true; } Queues FIFO: First in, First Out Restricted form of list: Insert at one end, remove from the other. Notations: • Insert: Enqueue • Delete: Dequeue • First element: Front • Last element: Rear Queue Implementation (1) Queue Implementation (2)