#pragma once #include "list.h" #include "magicqueue.h" template <typename T> class QueueList : public List<T> { private: MagicQueue <T> values; public: QueueList(); ~QueueList(); void insertAtHead(T item); void insertAtTail(T item); int getSize(); bool isEmpty(); // ...etc. all List methods are declared here }; #include "queuelist-inl.h"
Using the above declarations, complete an implementation for the methods getSize(), insertAtHead(T item), and removeTail(). Your answers should be written as they would appear in queueList-inl.h, paying attention to the scope and template operators. Once complete, describe the O() of each of your methods. Again, the details of MagicQueue are not important; you should assume it implements a Queue interface properly in O(1) time.
wackyMergeSort(A, n): if (n <= 1) return A1 = new array A2 = new array copy first two-thirds (2n/3) of A into A1 copy last one-third (n-2n/3) of A into A2 wackyMergeSort(A1, 2n/3) wackyMergeSort(A2, n-2n/3) // merges sorted A1, A2 back into A merge(A1, 2n/3, A2, n-2n/3, A)
Algorithm sum(A, n): Input: An array of n numbers Output: The sum of all elements in the array toReturn = 0 for i=0...n-1 toReturn = toReturn + A[i] return toReturn
Algorithm isSorted(A, n) Input: An array A of n elements Output: true if A is sorted, false otherwise for i =0...n-2: if(A[i] > A[i+1]): return false return true
Algorithm binarySearch(A,n, x): Input: A sorted array of size n, an element of x we wish to find Output: Position of x, or -1 if not found low=0, high=n-1 while(low < high): mid = (low+high)/2 if(A[mid] == x) : return mid else if (A[mid] < x): low = mid+1 else: high = mid-1 return -1;