Write a stack class using two STL lists. Naturally, a single STL list is more th

Question

Write a stack class using two STL lists. Naturally, a single STL list is more than enough to represent a stack. However, you are only limited to the following STL list methods:

(a) void push back(const Object & x); //adds x to the end of list

(b) void pop front(); //removes the object at the front of the list

(c) Object & front(); //returns the object at the front of the list

(d) bool empty() const; //true if empty container

Limited to these methods alone, our STL list essentially becomes a queue (enqueue is basically push back while dequeue is a combination of front and pop front). At the minimum, your stack class needs to have the following:

(a) An STL list is stored as an instance member of the stack class. You can think of this main list as storing your stack.

(b) A pop method that returns an Object at the top of the stack.

(c) A push method that takes an Object and places it at the top of the stack.

(d) If your list is empty, your pop method should throw an exception (any exception will do).

(e) Inside your push method, you can create a temporary list. As you are only limited to placing items at the back of your list (enqueue / push back), you can use this temporary list as storage to help move items from your main list to this list, add the new item to your main list, and then move back the items from the temporary list back to your main list.

Explanation / Answer

void reverse(string & x)
    //Afterwards x will have the same elements in the opposite order.
    {
        stack<char> s;
        const int n = x.length();
   //Put characters from x onto the stack
        for(int i=0; i<n; ++i)
            s.push(x[i]);
   //take characters off of stack and put them back into x
        for(int i=0; !s.empty(); ++i, s.pop())
            x[i]=s.top();

    }

**********************
void reverse(string & x) //INOUT: x is a string of characters
    //Afterwards x will have the same elements in the opposite order.
    {
        stack< vector<char> > s;

        const int n = x.length();
        for(int i=0; i<n; ++i)
            s.push(x[i]);
        for(int i=0; !s.empty(); ++i, s.pop())
            x[i]=s.top();
    }

*-**

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.