Written Exercise:
Chapter 7:
#13, 14, 15, 16, 18, 19, 21, 22, 23, & 24 on pages 377 to 381
Chapter 8:
#7, 8, 9, 10, 11, 12, 13, 15, 16, 17, & 18 on pages 426 to 429

stack<int> intStack;
int x, y=3;

intStack.push(8);
intStack.push(9);
intStack.push(y);
x = intStack.top();
intStack.pop();
intStack.push(18);
x = intStack.top();
intStack.pop();
intStack.push(22);
while(!intStack.empty())
{
   y = intStack.top();
   intStack.pop();
   cout<<y<<" ";
}
cout<<x<<endl;

stack<int> intStack;
int i;

intStack.push(8);
intStack.push(5);
intStack.push(3);
intStack.push(intStack.top());
intStack.push(intStack.top() * 2);
i = intStack.top();
intStack.pop();
intStack.push(2*i);

template <typename T>
void stackClear(stack<T>& s);

16. What is the action of the following code segment?

stack<T> s1, s2, tmp;
T x;
...
while(!s1.empty())
{
    x = s1.top();
    s1.pop();
    tmp.push(x);
}
//assume s2 is empty
while(!tmp.empty())
{
    x = tmp.top();
    tmp.pop();
    s1.push(x);
    s2.push(x);
}

template <typename T>
void f(stack<T>& s, const T& item)
{
    stack<T> tmpStack;
    T tmpVal;
    bool have = true;

    while(!s.empty() && s.top() != item)
    {
        tmpVal = s.top();
        s.pop();
        tmpStack.push(tmpVal);
    }

    if (s.empty() == true)
        have = false;
    else
        s.pop();

    while(!tmpStack.empty())
    {
        s.push(tmpStack.top());
        tmpStack.pop();
    }

    if(have)
        s.push(item);
}

while(!s.empty())
{
    cout<<s.top()<<" ";
    s.pop();
}

template <typename T>
void f(stack<T>& s)
{
    vector<T> v;
    int i;

    while(!s.empty())
    {
        v.push_back(s.top());
        s.pop();
    }
    for(i=0; i < v.size(); i++)
        s.push(v[i]);
}

Assume that s has the values 3  4  9  12  15  8  3  5, where 5 is on the top of the stack.
What is the output from the following statements?

f(s);
while(!s.empty())
{
    cout<<s.top()<<" ";
    s.pop();
}

23. Draw the sequence of stack configurations in the evaluation of the following postfix expression:

4  5  *  6  3  +  /  8  +

7  *  (5  +  2  *  3)  -  2

8. A queue is an applicable data structure for (circle all that apply)
    (a) expression evaluation
    (b) an operating-system job scheduler
    (c) simulation of waiting lines
    (d) printing a list in reverse order

9. What is the output from the following sequence of queue operations?

queue<int> q;
int x = 5, y = 3;

q.push(8);
q.push(9);
q.push(y);
x = q.front();
q.pop();
q.push(18);
x = q.front();
q.push(22);
while(!q.empty())
{
    y = q.front();
    q.pop();
    cout<<y<<" ";
}
cout<<x<<endl;

queue<int> intQueue;

intQueue.push(18);
intQueue.push(2);
intQueue.push(intQueue.front());
intQueue.push(intQueue.front());
intQueue.pop();

template<typename T>
void f(queue<T>& q)
{
    stack<T> s;
    T elt;

    while(!q.empty())
    {
        elt = q.front();
        q.pop();
        s.push(elt);
    }

    while(!s.empty())
    {
        elt = s.top();
        s.pop();
        q.push(elt);
    }
}

12. What is the action of the following code segment?

queue<int> q1, q2;
int x;
int n = 0, i;
  ...
//assume q2 is empty and n = 0
while (!q1.empty())
{
    x = q1.front();
    q1.pop();
    q2.push(x);
    n++;
}

for(i=0; i < n; i++)
{
    x = q2.front();
    q2.pop();
    q1.push(x);
    q2.push(x);
}

template<typename T>
T f(const queue<T>& q)
{
    queue<T> qtmp;
    int i, qsize = q.size();

// assign q to qtmp
qtmp = q;

for(i=0; i<qsize-1; i++)
  qtmp.pop();

return qtmp.front();
}

priority_queue<int> pq;
int arr[] ={10, 50, 30, 40, 60};
int i, x, y;

for(i=0; i<5; i++)
   pq.push(arr[i]);

pq.push(25);
x = pq.top();
pq.pop();
pq.push(35);
y = pq.top();
pq.pop();
cout<<x<<" "<<y<<endl;
while(!pq.empty())
{
    cout<<pq.top()<<" ";
    pq.pop();
}
cout<<endl;

priority_queue<int> intPQ;  //empty priority queue

intPQ.push(5);
intPQ.push(27);
intPQ.push(25);
intPQ.pop();
intPQ.push(intPQ.top() * 2);
intPQ.push(intPQ.top() * 5);
while (!intPQ.empty())
{
    cout<< intPQ.top()<<" ";
    intPQ.pop();
}
cout <<endl;

stack<int> s;
queue<int> q;
priority_queue<int> pq;

while( !s.empty())
{
    cout<<setw(5)<<s.top()<<setw(5)
        <<q.front() <<setw(5)
        <<pq.top() <<endl;
    s.pop();
    q.pop();
    pq.pop();
}