L18 - Queues and Ordered Linked Lists

#ece244

queues

Queues are FIFO (First-In, FIrst-Out). Consists of two main functions:

• enqueue(): inserts a new node at the end (tail) of the list
• dequeue(): removes the node that was first added, at the head (front) of the lsit
  Unlike a stack, we need to track two pointers - the head and the tail - because we need to remove from the bottom of the list too.

queue class implementation

Note: we are still using the Node class definition from L17.

class Queue {
	private:
		Node *head;
		Node *tail;
	public:
		Queue() {
			// constructor creates NULL head and tail
			// because there are no items in list
			head = NULL;
			tail = NULL;
		}
		
		~Queue() {
			// destructor is same as Stack; recursively deletes all nodes
			delete head;
		}
		
		void enqueue(int d) { // add new node to end of list (tail)
			// 1. create a new node, whose 'next' is NULL
			Node *p = new Node(d, NULL);
			// 2. If list is NOT empty (tail exists), link current tail
			// to this node
			if (tail != NULL) {
				tail->setNext(p);
			}
			// 3. update 'tail' pointer to the new node
			tail = p;
			// 4. IF queue is empty previously, then we must also point
			// the head pointer to this new node as well.
			if (head == NULL) {
				head = p;
			}
		}
		
		int dequeue() { // remove the node at the head and return its value
			// 1. check for empty queue
			if (head == NULL) { // could also check tail == NULL
				return -1;
			}
			// 2. create temp pointer to head
			Node *p = head;
			//3. retrieve data from node that we're removing
			int d = p->getData();
			// 4. reassign head pointer to point to next node in queue
			head = p->getNext();
			// 5. IF head is now NULL (i.e., the queue only had one item)
			// then set both head and tail to NULL bc otherwise tail would
			// point to node we are removing, and then become a dangling ptr
			if (head == NULL) {
				tail = NULL;
			}
			// 6. isolate the pointer we are removing by assigning its next
			// to be NULL
			p->setNext(NULL);
			// 7. delete the isolated node
			delete p;
			// 8. return the data
			return d;
		}
}

example main function using queue implementation

int main(void) {
	Queue q;
	q.enqueue(0);
	q.enqueue(1);
	q.enqueue(2);
	// create queue such that 0 is at head, 1 is in middle, and 2 is at tail
	
	cout << q.dequeue() << q.dequeue() << endl;
	// prints "012" bc 0 is first in (head), then 1, and 2 is last (tail)
}

ordered linked lists

An ordered linked list is a linked list where the data members are ordered. They contain the following 4 basic operations:

1. insert in sorted order
2. search
3. delete
4. copy and operator=
   Thus, they generally follow this class definition. Note: this once again uses the Node definition from L17.

#include 'Node.h'

class List {
	private:
		Node* head;
		int data;
	public:
		List() { head = NULL; } // default constructor; set head to NULL
		~List() { delete head; } // destructor; deallocate head node
		void insertData(int d); // insert data into the linked list
		bool dataExists(int d); // search list for data and return bool
		bool deleteData(int d);
		// delete data from list; returns bool for existence of data
		List (const& List); // copy constructor
		List& operator=(const& List); // operator= definition
}

searching linked lists: bool dataExists(int d);

Basic operation:

• iterate through linked list until you find node with value d
• if found, return true
• if you reach the end of the list without finding it, return false

bool List::dataExists(int d) {
	
	if (head != NULL) {
		List* curr = head;
		while (curr != NULL && curr->getData() <= d) {
			if (curr->getData() == d) {
				return true;
			}
			curr = curr->getNext();
		}
	}
	return false;
}

Notes:

• we check curr->getData() <= d in the while loop as a time saving measure because then we don't have to check the rest of the list, where the values will 100% not be equal to d (since it's ordered)
• technically we don't need the if (head != NULL) check because while (curr != NULL ... checks that already