Computer Science II -- Week 6
Introduction
Note that the links from this page are to handouts that will be distributed the night of class. Only print out those handouts if you could not attend class.
Main topics this week:
Simple Linked Lists
Queues
In-class exercise
Standard Template Library queue
Vectors
Iterators
Algorithms
We won't really talk about linked lists until week 8, but for the purposes of talking about queues, we need to talk about a simple type of linked list.
Describe layout of linked list.
Linked list operations:
bool isEmpty ()
int getFront ()
void insertAtEnd (int)
void removeFront ()
Don't worry about how these work for now.
Queues are a data structure. Like all other data structures, queues hold a collection of things. Describe the general layout of a queue.
How do you put things into a queue?
How do you take things out of a queue?
Queue operations:
enqueue (data)
dequeue ()
data front ()
bool isEmpty ()
Walk through the following operations and show what the queue will look like after each operation:
enqueue (1)
enqueue (2)
enqueue (3)
front ()
dequeue ()
front ()
enqueue (4)
What data structures could we use to implement a queue? Check each data structure to see what happens when we need to enqueue or dequeue an item from the queue.
Show examples of enqueuing and dequeueing from different data structures.
This handout lists one possibility for a queue header file (queue.h), assuming we are using a linked list class to implement the queue.
Walk through the implementation of the isEmpty method:
bool queue::isEmpty () const
{
return myList.isEmpty ();
}
The frontMethod:
int queue::front () const
{
return myList.getFront ();
}
Write the implementation for the queue methods, enqueue and dequeue.
Standard Template Library queue
The standard template library has a queue class available for your use. The enqueue function is called push and the dequeue function is called pop. Otherwise the STL queue functions like the queues we've discussed.
#include <iostream>
#include <queue>void main ()
{
queue<int> aQueue;aQueue.push (50);
cout << aQueue.front () << endl;
aQueue.pop ();
}
Vectors are a part of the C++ standard template library. What is a vector? (Section 6.4 in your book describes vectors)
Common operations:
int size ()
bool empty ()
void push_back (value)
void pop_back ()
value front ()
value back ()
You can also use array syntax to look at the value of an item in the vector. Do not use to add new items to the vector!
Usage:
#include <vector>
void main ()
{
vector<int> x;x.push_back (5);
cout << x.front () << endl; // outputs 5
cout << x [0] << endl; // also outputs 5
}
You can think of an iterator as an index into a C++ standard template library collection. An iterator gives you a single item out of a collection of items. Iterators work with most standard template library collections.
If a collection supports iterators, it has a begin () and end () method.
begin () returns an iterator which points to the first item in the collection.
end () returns an iterator which points to just past the last item in the collection.
Other operations on iterators:
++ Move to the next item in the collection
-- Move to the previous item in the collection
* Get the value of the item the iterator points to
Example using vector:
#include <vector>
void main ()
{
vector<int> x;x.push_back (10);
x.push_back (5);vector<int>::iterator iter = x.begin ();
while (iter != x.end ())
{
cout << (*iter) << endl;
iter++;
}
}
The C++ standard template library provides some generic algorithms that work with the provided collections. The algorithms work by taking iterators, which work the same regardless of what type of collection is used. These generic algorithms are provided as functions you can call from C++.
Usage:
#include <algorithm>
The find algorithm locates a specific value in an unsorted list.
#include <vector>
#include <algorithm>void main ()
{
vector<int> x;...put some values into x...
vector<int>::iterator iter = find (x.begin (), x.end (), 5);
if (iter == x.end ())
cout << "The value 5 was not found" << endl;
}
The find algorithm uses == and != to see if individual elements are equal to value. So if I have a vector of classes, then the operator== and operator!= methods in my class will be called, and the parameter will be the value passed into find. For example:
#include <vector>
#include <algorithm>
#include "foo.h"void main ()
{
vector<Foo> aVector;
Foo aFoo;aFoo.setData (5);
aVector.push_back (aFoo);
aFoo.setData (6);
aVector.push_back (aFoo);
aFoo.setData (7);
aVector.push_back (aFoo);vector<Foo>::iterator iter;
// This one calls Foo::operator!= (const Foo &)
// and Foo::operator== (const Foo &)
iter = find (aVector.begin (), aVector.end (), aFoo);// This one calls Foo::operator!= (int)
// and Foo::operator== (int)
iter = find (aVector.begin (), aVector.end (), 10);
}
The moral is that if you want to be able to find items in a vector by using something other than the type of item actually stored in the vector, you must write appropriate operator== and operator!= methods to make it work.
The count algorithm counts how many times a specific value appears in the collection.
#include <vector>
#include <algorithm>void main ()
{
vector<int> x;...put some values into x...
int numTimes = count (x.begin (), x.end (), 5);
cout << "The value 5 appeared " << numTimes << endl;
}
There are many other algorithms available. (Section 7.5 in your book has a discussion of some of the available algorithms.)