//main.cpp

#include #include #include #include #include #include "queue.h"

using namespace std;

// Testing stuff; just ignore it :) inline void _test(const char* expression, const char* file, int line) { fprintf(stderr, "test(%s) failed in file %s, line %d. ", expression, file, line); abort(); }

#define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__)) // End of testing stuff

int main() { Queue q; test(q.size() == 0); cout << "5% earned." << endl;

q.pop(); q.front(); test(q.size() == 0); cout << "10% earned." << endl;

q.push("hello"); // Queue is now ["hello"] test(q.size() == 1); test(q.front() == "hello"); cout << "20% earned." << endl;

q.push("cat"); // Queue is now ["cat", "hello"] test(q.size() == 2); test(q.front() == "hello"); cout << "25% earned." << endl;

q.push("bird"); // Queue is now ["bird", "cat", "hello"] test(q.size() == 3); test(q.front() == "hello"); cout << "30% earned." << endl; q.push("goodbye"); // Queue is now ["goodbye", "bird", "cat", "hello"] test(q.size() == 4); test(q.front() == "hello"); cout << "35% earned." << endl;

q.pop(); // Queue is now ["goodbye", "bird", "cat"] test(q.size() == 3); test(q.front() == "cat"); cout << "40% earned." << endl;

q.pop(); // Queue is now ["goodbye", "bird"] test(q.size() == 2); test(q.front() == "bird"); cout << "45% earned." << endl;

q.pop(); // Queue is now ["goodbye"] test(q.size() == 1); test(q.front() == "goodbye"); cout << "55% earned." << endl;

q.pop(); // Queue is now [] test(q.size() == 0); cout << "65% earned." << endl;

// Test whether popping off empty queue // doesn't cause problems q.pop(); test(q.size() == 0); q.push("1"); test(q.size() == 1); q.pop(); test(q.size() == 0); cout << "70% earned." << endl;

// Push a few special things at the front q.push("first"); q.push("second"); q.push("third");

// Time how long about 1000000 pushes takes clock_t start = clock(); for (int i = 4; i <= 999999; ++i) { q.push("dog"); test(q.size() == i); } clock_t end = clock(); float push_elapsed = static_cast(end - start) / CLOCKS_PER_SEC; q.push("last"); test(q.size() == 1000000);

// Test that the queue contents at the front are ok test(q.front() == "first"); q.pop(); test(q.front() == "second"); q.pop(); test(q.front() == "third"); q.pop();

// Time how long about 100000 pops takes start = clock(); for (int i = 999997; i >= 2; --i) { test(q.size() == i); q.pop(); } end = clock(); float pop_elapsed = static_cast(end - start) / CLOCKS_PER_SEC; test(q.front() == "last"); cout << "100% earned." << endl;

// Print a score (just for fun) cout << "Pushing ~1000000 elements took " << push_elapsed << " seconds." << endl; cout << "Popping ~1000000 elements took " << pop_elapsed << " seconds." << endl; } //**********************************************************************************************

//queue.cpp

#include "queue.h"

Queue :: Queue() { // This already works head = tail = 0; count = 0; }

void Queue :: push(string s) { // EDIT HERE }

void Queue :: pop() { // EDIT HERE }

string Queue :: front() { // This already works if (head != 0) return head->s; return ""; }

int Queue :: size() { // This already works return count; } //**************************************************************

//queue.h

#ifndef QUEUE_H #define QUEUE_H

#include

using namespace std;

class Queue { public: Queue(); void push(string s); void pop(); string front(); int size();

private: class Node { public: string s; Node* next; };

Node* head; Node* tail; int count; };

#endif