CHAPTER 3
Lists, Stacks, and Queues
3.1
template <typename Object>
void printLots(list <Object> L, list<int> P)
{
typename list < int > ::const_iterator pIter ;
typename list < Object >::const_iterator lIter ;
int start = 0;
lIter = L.begin();
3.2 (a) Here is the code for single linked lists:
// beforeP is the cell before the two adjacent cells that are to be
// swapped
// Error checks are omitted for clarity
void swapWithNext(Node * beforep)
}
(b) Here is the code for doubly linked lists:
// p and afterp are cells to be switched. Error checks as before
{
Node *beforep, *afterp;
beforep = p–>prev;
afterp = p–>next;
p->next = afterp–>next;
3.3
template <typename Iterator, typename Object>
Iterator find(Iterator start, Iterator end, const Object& x)
{
Iterator iter = start;
3.4
// Assumes both input lists are sorted
template <typename Object>
list<Object> intersection( const list<Object> & L1,
const list<Object> & L2)
{
list<Object> intersect;
3.5
// Assumes both input lists are sorted
template <typename Object>
list<Object> listUnion( const list<Object> & L1,
const list<Object> & L2)
{
list<Object> result;
typename list<Object>:: const_iterator iterL1 = L1.begin();
typename list<Object>:: const_iterator iterL2= L2.begin();
while(iterL1 != L1.end() && iterL2 != L2.end())
3.6 This is a standard programming project. The algorithm can be sped up by setting M
t
=M mod N,
so that the hot potato never goes around the circle more than once. If M
t
>N/2, the potato should
be passed in the reverse direction. This requires a doubly linked list. The worst case running time
is clearly O(N min(M, N)), although when the heuristics are used, and M and N are comparable,
the algorithm might be significantly faster. If M = 1, the algorithm is clearly linear.
#include <iostream>
#include <list>
using namespace std;
int main()
mPrime = mPrime % numLeft;
if (mPrime <= numLeft/2) // pass forward
for (j = 0; j < mPrime; j++)
{
iter++;
if (iter == L.end())
iter = L.begin();
}
3.7 O(N2). The trim method reduces the size of the array, requiring each add to resize it. The resize takes O(N)
time, and there are O(N) calls.
3.8
iterator insert(iterator pos, const Object& x)
{
Object * iter = &objects[0];
Object *oldArray = objects;
theSize++;
int i;
if (theCapacity < theSize)
theCapactiy = theSize;
3.10 The changes are the const_iterator class, the iterator class and changes to all Vector functions that
use or return iterators. These classes and functions are shown in the following three
(a)
class const_iterator
{
public:
}
bool operator== ( const const_iterator & rhs ) const
{ return current == rhs.current; }
bool operator!= ( const const_iterator & rhs ) const
(b)
class iterator : public const_iterator
{
public:
//iterator( )
// { } Force use of the safe constructor
Object & operator* ( ) { return retrieve( ); }
(c)
iterator begin( )
{ return iterator(*this ,&objects[ 0 ]); }
3.11
template <typename Object>
struct Node
{
Object data;
Node * next;
Node ( const Object & d = Object(), Node *n = NULL ) : data(d) , next(n) {}
};
}
bool add(Object x)
{
if (contains(x))
return false;
else
{
Node<Object> *ptr = new Node<Object>(x);
ptr–>next = head–>next;
head–>next = ptr;
theSize++;
}
int size() { return theSize;}
void print()
{
void init()
{
theSize = 0;
head = new Node<Object>;
head–> next = NULL;
}
void eraseList(Node<Object> * h)
3.12
template <typename Object>
struct Node
{
Object data;
Node * next;
Node ( const Object & d = Object(), Node *n = NULL ) : data(d) , next(n) {}
};
}
bool add(Object x)
{
if (contains(x))
return false;
else
{
Node<Object> *ptr = head->next;
Node<Object>* trailer = head;
}
bool remove(Object x)
{
if (!contains(x))
return false;
else
{
Node<Object>*ptr = head–>next;
Node<Object>*trailer;
while(ptr–>data != x)
{
trailer = ptr;
ptr=ptr–>next;
}
bool contains(const Object & x)
{
Node<Object> * ptr = head–>next;
while (ptr != NULL && ptr–>data <= x )
{
if (x == ptr–>data)
return true;
3.13 Add the following code to the const_iterator class. Add the same code with iterator replacing
const_iterator to the iterator class.
const_iterator & operator— ( )
3.14
const_iterator & operator+ ( int k )
3.15
void splice (iterator itr, List<Object> & lst)
{
itr.assertIsValid();
if (itr.theList != this)
throw IteratorMismatchException ();
3.16
The class const_reverse_iterator is almost identical to const_iterator while reverse_iterator is
almost identical to iterator. Redefine ++ to be − and vice versa for both the pre and post operators
for both classes as well as changing all variables of type const_iterator to const_reverse_iterator
and changing iterator to reverse_iterator. Add two new members in list for rbegin() and rend().
// In List add
const_reverse_iterator rbegin() const
3.17 changed functions listed below
For the class const_iterator
const_iterator( ) : current( nullptr )
}
const_iterator operator++ ( int )
{
assertIsValid();
const_iterator old = *this;
++( *this );
return old;
}
{
if (theList == nullptr || current == nullptr || current == theList->head)
throw IteratorOutOfBoundsException();
}
iterator & operator++ ( )
{
assertIsValid();
this->current = this->current->next;
return *this;
}
iterator operator++ ( int )
For the List class
iterator begin( )
{ iterator itr(*this, head);
return (++itr );
iterator insert( iterator itr, const Object & x )
{
itr.assertIsValid();
if (itr.theList != this)
throw IteratorMismatchException();
Node *p = itr.current;
theSize++;
return (*this, p->prev = p->prev->next = new Node( x, p->prev, p ) );
}
iterator insert( iterator itr, Object && x )
return retVal;
}
iterator erase( iterator from, iterator to )
{
for( iterator itr = from; itr != to; )
{
3.19 Without head or tail nodes the operations of inserting and deleting from the end becomes a O(N)
3.20 (a) The advantages are that it is simpler to code, and there is a possible saving if deleted keys are
(b) Add a int numDeleted to the list (initialized to 0) and a bool deleted to Node (initialized to false)
void garbageCollection()
}
iterator erase( iterator itr )
3.21 (b)
/*
Weiss Exercise 3_21 Balanced parenthesis for c++
*/
int main()
{
string fileName;
stack<char> match;
cout<<“what is the name of the file: “;
cin>>fileName;
in.open(fileName.c_str());
}
else if (x == ‘\”) // skip chars in single quotes
{
i++;
while (x != ‘\”)
x++;
}
else if (x == ‘\\’ && i < line.size()-1 && line[i+1] == ‘\\’)
getline(in, line);
else if (x == ‘(‘ || x == ‘[‘|| x == ‘{‘)
match.push(x);
else if (x == ‘)’)
3.22 The following function evaluates a postfix expression, using +, −, ∗, / and ^ ending in =. It requires
spaces between all operators and = and uses the stack, string and math.h libraries. It only recognizes
0 in input as 0.0.
double evalPostFix( )
{
stack<double> s;
string token;
double a, b, result;
cin>> token;
while (token[0] != ’=’)
{
case ’+’ : a = s.top(); s.pop(); b = s.top();
s.pop(); s.push(a+b); break;
case ’–’ : a = s.top(); s.pop(); b = s.top();
}
3.23 (a, b) This function will read in from standard input an infix expression of single lower case
characters and the operators, +, −, / , ∗, ^ and (, ), and output a postfix expression.
void inToPostfix()
{
stack<char> s;
char token;
{ cout<<s.top()<<” “; s.pop();}
s.pop(); break;
case ’(’ : s.push(token); break;
}
(c) The function converts postfix to infix with the same restrictions as above.
string postToInfix()
{
stack<string> s;
string token;
{
case ’+’ : a = s.top(); s.pop(); b = s.top(); s.pop();
s.push(“(“+ a+” + ” + b+”)”); break;
case ’–’ : a = s.top(); s.pop(); b = s.top(); s.pop();
3.24 Two stacks can be implemented in an y array by having one grow from the low end of the array up,
3.25 (a) Let E be our extended stack. We will implement E with two stacks. One stack, which we’ll call
3.26 Three stacks can be implemented by having one grow from the bottom up, another from the top
3.27 Stack space will not run out because only 49 calls will be stacked. However the running time is
3.28 This requires a doubly linked list with pointers to the head and the tail In fact it can be implemented
with a list by just renaming the list operations.
template <typename Object>
class deque
3.29 Reversal of a singly linked list can be done recursively using a stack, but this requires O (N) extra
space. The following solution is similar to strategies employed in garbage collection algorithms (first
represents the first node in the non-empty node in the non-empty list). At the top of the while loop
//Assuming no header and that first is not NULL
Node * reverseList(Node *first)
{
Node * currentPos, *nextPos, *previousPos;
previousPos = NULL;
3.31
template <typename Object>
struct node
template <typename Object>
class stack
{
Object top()
{return (head->data); }
void pop()
3.32
template <typename Object>
class queue
{
public:
queue () { front = NULL; rear = NULL;}
front = rear = NULL;
else
3.33 This implementation holds maxSize −1 elements.
template <typename Object>
class queue
{
public:
Object deque()
{
Object temp;
if (!empty())
private:
int front, rear;
3.34 (b) Use two iterators p and q, both initially at the start of the list. Advance p one step at a time,
