?
Solved

Trouble Understanding Queue using Linked List

Posted on 2009-04-15
9
Medium Priority
?
531 Views
Last Modified: 2013-12-14
The problem I am having is figuring out to create my queue while using my list header file.  That is the minor problem, compared to my bafflement on how to get my input into the queue.  I have a text file with expressions in infix order. I need to get these expressions into my queue.  I am obviously new to data structures and have been trying to figure this out.  I think why I'm having such a hard time is that my instructor gave me the specific method enQueue(const Object &).  

I will include my attempts.....and the header and data file.

Edit: Changed my header methods posted below-
                      I now have my current main code posted.
#include <iostream>
#include "List.h"
 
using namespace std;
 
    List<string> listStack;             //initializing empty stack
    List<string> listQueue1;            //initializing empty Queue1
    List<string> listQueue2;            //initializing empty Queue1
 
int main()
{
    listQueue1.Input();
    listQueue1.print();
 
    return 0;
}

Open in new window

data.txt
0
Comment
Question by:b_acs
9 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 24154938
Ok, first question is, do you know how to implement and linked list? If you don't we'll need to go back a step. If you do then using it as a queue is pretty straight forward. When you enqueue you just add the node to the head of the list and when you dequeue you just remove and return the node at the tail of the list.

It would help if you could be more specific about what it is you are unsure of so we can target the right problems.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24155405
>>>> listQueue1.Input();

If Input is a valid member function of the List class it probably takes a string as argument like

   listQueue1.Input("John Smith");

If so, that that is the way to add entries to the queue.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24155436
FYI:

As List is a template class the member function to add entries would take the template type (in your case std::string) as argument. As std::string has a constructor which takes a literal, e. g. "John Smith", you can pass a literal instead of a std::string as well. Then the literal was turned to a std::string and the resulting string was passed to the Input member function (if that is the right member function, what we don't know as long as you don't post the list.h).
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24155460
>>>> as long as you don't post the list.h

Please post the contents of list.h in the Code Snippet box. I won't download with my current browser.
0
 
LVL 6

Expert Comment

by:bijopuli
ID: 24155464
0
 

Author Comment

by:b_acs
ID: 24161542
I appologize I meant to post the list.h but got busy and forgot.  Here it is.  As you can see I am trying to enqueue using the Input method.  I'm not sure if this is a good idea though.
#ifndef LIST_H
#define LIST_H
 
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <sstream>
 
using namespace std;
 
template <typename Object>
class List
{
  private:
    // The basic doubly linked list node.
    // Nested inside of List, can be public
    // because the Node is itself private
    struct Node
    {
        Object  data;
        Node   *prev;
        Node   *next;
 
        Node( const Object & d = Object( ), Node * p = NULL, Node * n = NULL )
          : data( d ), prev( p ), next( n ) { }
    };
 
  public:
    class const_iterator
    {
      public:
 
        // Public constructor for const_iterator.
        const_iterator( ) : current( NULL )
          { }
 
        // Return the object stored at the current position.
        // For const_iterator, this is an accessor with a
        // const reference return type.
        const Object & operator* ( ) const
          { return retrieve( ); }
 
        const_iterator & operator++ ( )
        {
            current = current->next;
            return *this;
        }
 
        const_iterator operator++ ( int )
        {
            const_iterator old = *this;
            ++( *this );
            return old;
        }
 
        const_iterator & operator-- ( )
        {
            current = current->prev;
            return *this;
        }
 
        const_iterator operator-- ( int )
        {
            const_iterator old = *this;
            --( *this );
            return old;
        }
 
        bool operator== ( const const_iterator & rhs ) const
          { return current == rhs.current; }
 
        bool operator!= ( const const_iterator & rhs ) const
          { return !( *this == rhs ); }
 
      protected:
        Node *current;
 
        // Protected helper in const_iterator that returns the object
        // stored at the current position. Can be called by all
        // three versions of operator* without any type conversions.
        Object & retrieve( ) const
          { return current->data; }
 
        // Protected constructor for const_iterator.
        // Expects a pointer that represents the current position.
        const_iterator( Node *p ) :  current( p )
          { }
 
        friend class List<Object>;
    };
 
    class iterator : public const_iterator
    {
      public:
 
        // Public constructor for iterator.
        // Calls the base-class constructor.
        // Must be provided because the private constructor
        // is written; otherwise zero-parameter constructor
        // would be disabled.
        iterator( )
          { }
 
        Object & operator* ( )
          { return this->retrieve( ); }
 
        // Return the object stored at the current position.
        // For iterator, there is an accessor with a
        // const reference return type and a mutator with
        // a reference return type. The accessor is shown first.
        const Object & operator* ( ) const
          { return const_iterator::operator*( ); }
 
        iterator & operator++ ( )
        {
            this->current = this->current->next;
            return *this;
        }
 
        iterator operator++ ( int )
        {
            iterator old = *this;
            ++( *this );
            return old;
        }
 
        iterator & operator-- ( )
        {
            this->current = this->current->prev;
            return *this;
        }
 
        iterator operator-- ( int )
        {
            iterator old = *this;
            --( *this );
            return old;
        }
 
      protected:
        // Protected constructor for iterator.
        // Expects the current position.
        iterator( Node *p ) : const_iterator( p )
          { }
 
        friend class List<Object>;
    };
 
  public:
    List( )
      { init( ); }
 
    ~List( )
    {
        clear( );
        delete head;
        delete tail;
    }
 
    List( const List & rhs )
    {
        init( );
        *this = rhs;
    }
 
    const List & operator= ( const List & rhs )
    {
        if( this == &rhs )
            return *this;
        clear( );
        for( const_iterator itr = rhs.begin( ); itr != rhs.end( ); ++itr )
            push_back( *itr );
        return *this;
    }
 
    // Return iterator representing beginning of list.
    // Mutator version is first, then accessor version.
    iterator begin( )
      { return iterator( head->next ); }
 
    const_iterator begin( ) const
      { return const_iterator( head->next ); }
 
    // Return iterator representing endmarker of list.
    // Mutator version is first, then accessor version.
    iterator end( )
      { return iterator( tail ); }
 
    const_iterator end( ) const
      { return const_iterator( tail ); }
 
    // Return number of elements currently in the list.
    int size( ) const
      { return theSize; }
 
    // Return true if the list is empty, false otherwise.
    bool empty( ) const
      { return size( ) == 0; }
 
    void clear( )
    {
        while( !empty( ) )
            pop_front( );
    }
 
//*****************************************************************************************************
//*************************************Added Stuff*****************************************************
//*****************************************************************************************************
 
 
 
    void enQueue(const Object& object)
    {
      //if the queue is full, print error
//       if (full ())
//        {
//            cout << "\n\nQueue is full!";
//        }else // OK to add an element
//        {
            this->push_back(object);
        //}
    }
 
    Object deQueue()
    {// if the queue is empty, print error
        if (empty ())
        {
            cout << "\nQueue is Empty!";
            return ' ';
        }else // OK to remove an element
        {
            Object temp = *this->begin();          // Building our temp value and setting it to the
                                                    // beginning node value.
            this->erase(this->begin());         // Erasing my beginning node since I have stored
                                                    // the value into my temp object
            return temp;
        }
    }
 
    void Input()
    {
        string strLine;
        //string strIn;
        ifstream inFile("data.txt");
        if(!inFile)
        {
            cout << "File not found" << endl;
            exit(1);
        }
        for(int i = 1; i < 4; i++)
        {
            while(!inFile.eof())
            {
                getline(inFile, strLine);
 
                stringstream iss(strLine);  //grab the line string to dissect
 
                while(iss >> strLine)
                {
                    cout << strLine << ' ';
                    enQueue(strLine); //this is sending our items into the queue
                }
            }
        }
    }
 
    void print()
    {
          if (theSize == 0)
            {
              cout << "Queue is empty\n";
            }else
            {
                for(int i = 0; i < theSize; i++)
                {
                    cout << i << endl;
                }
            }
    }
//   void print() //this one is now working
//    {
//        if(theSize == 0) //checks the size of the list to make sure its not empty
//        {
//            cout << "NULL" << endl << endl; //if the list is empty will print a null
//                                            //on the screen
//        }
//        else
//        {
//            for(iterator i=this->begin(); i != this->end();i++)
//            {
//                cout << *i << " ";  // added a space instead of endl so that it will
//                                    // print out on one line and not downwards
//                                    // individually
//            }
//        }
 
 
 
//*****************************************************************************************************
//*************************************Added Stuff Ends************************************************
//*****************************************************************************************************
 
 
 
 
 
 
 
    // front, back, push_front, push_back, pop_front, and pop_back
    // are the basic double-ended queue operations.
    Object & front( )
      { return *begin( ); }
 
    const Object & front( ) const
      { return *begin( ); }
 
    Object & back( )
      { return *--end( ); }
 
    const Object & back( ) const
      { return *--end( ); }
 
    void push_front( const Object & x )
      { insert( begin( ), x ); }
 
    void push_back( const Object & x )
      { insert( end( ), x ); }
 
    void pop_front( )
      { erase( begin( ) ); }
 
    void pop_back( )
      { erase( --end( ) ); }
 
    // Insert x before itr.
    iterator insert( iterator itr, const Object & x )
    {
        Node *p = itr.current;
        theSize++;
        return iterator( p->prev = p->prev->next = new Node( x, p->prev, p ) );
    }
 
    // Erase item at itr.
    iterator erase( iterator itr )
    {
        Node *p = itr.current;
        iterator retVal( p->next );
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
        theSize--;
 
        return retVal;
    }
 
    iterator erase( iterator start, iterator end )
    {
        for( iterator itr = start; itr != end; )
            itr = erase( itr );
 
        return end;
    }
 
  private:
    int   theSize;
    Node *head;
    Node *tail;
 
    void init( )
    {
        theSize = 0;
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prev = head;
    }
};
 
#endif

Open in new window

0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 2000 total points
ID: 24163442
Ok. The Input member reads from file data.txt.

It has a for loop incrementing i from 0 to 3 but inside the for loop the i counter wasn't used so that the loop runs just for fun more than one time.

Inside of the for loop is a while loop which would read all lines of data.txt (which were 3 lines) and each line would then be parsed word by word with another loop while(iss >> strLine) and added to the queue by calling push_back.

So, your queue contains after Input the following elements.

3
*
44
/
(
6
-
3
)
^
2
+
241
14
+
8
*
18
-
6
/
2
8
+
7
*
6
+
(
5
*
4
+
3
)
*
2

Note, that only works cause there are spaces between each element (what normaly cannot be assumed or guaranteed).

>>>> I'm not sure if this is a good idea though.
No, it is not a good idea. You  - at least - should pass the file name to the Input, drop the outer for loop, and make it robust regarding missing spaces. To do that you best drop the while loop where you read from stringstream and replace it by a loop which regards each single char of the input line. If a complete operand or operator was recognized it would enqueue it:

  int lastpos = 0;
  for (int j = 0; j <= (int)strLine.size(); ++j)
  {
      char c = strLine.c_str()[i];
      switch(c)
      {
      case ('0'): case ('1'): case ('2'): case ('3'): case ('4'):
      case ('5'): case ('6'): case ('7'): case ('8'): case ('9'):
           break;
      case '/': case '+': case '*': case '-': case '^': case '(': case ')':
           {
               if (j > lastpos)
              {
                 enqueue(strLine.substr(lastpos, j-lastpos));
                 lastpos = j;
              }
              enqueue(strLine.substr(lastpos++, 1));
           }
           break;
      case ' ':
      case '\0':
           if (j > lastpos)
          {
               enqueue(strLine.substr(lastpos, j-lastpos));
               lastpos = j+1;
          }      
          break;
      }      
  }  


Note the loop includes the terminating zero char of the line to have also the last operand enqueued.

0
 

Author Comment

by:b_acs
ID: 24238068
Here is what I came up with....

I used a header that uses a header.  As far as I can tell this seems to work correctly.
I would appreciate any comments.  I need to improve my understanding of these earlier data structures.

Thanks,
B_Acs

Note:  I have turned in this assignment, I am just looking to expand my working knowledge in this language.
#include "Input.h"
 
int main()
{
   Input();
   return 0;
}
 
 
//*********************************************************************
 
#ifndef INPUT_H
#define INPUT_H
 
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <sstream>
#include <math.h>
#include "List.h"
 
using namespace std;
 
List<string> listStack;             //initializing empty stack
List<string> listQueue1;            //initializing empty Queue1
List<string> listQueue2;            //initializing empty Queue2
 
int getOperator(string sOper)
{
    if(sOper == "+")
        return 1;
    else if(sOper ==  "-")
        return 1;
    else if(sOper == "*")
        return 2;
    else if(sOper == "/")
        return 2;
    else if(sOper == "%")
        return 2;
    else if(sOper == "^")
        return 3;
    else if(sOper == "(")
        return -1;
    else if(sOper == ")")
        return -2;
    else
        return 0;
}
template <class T>
string toString (const T& t)
{
    stringstream ss;            //stringstream used for conversion
    ss << t;                    //set the string stream to the value
    return ss.str();            // Return the value
}
//change string to int value for calculation
int toInt (string t)
{
    stringstream ss;            //stringstream used for conversion
    int x = 0;
    ss << t;                    //set the string stream to the value
    ss >> x;
    return x;            // Return the value in string format
}
void Evaluate()
{
    string Value = "";
    string stVal = "";
 
    while(listQueue1.size() != 0)
    {
        Value = listQueue1.deQueue();     //dequeue and store the value in Value string
 
        switch (getOperator(Value))   // Check the value to see if it is an operator or number
        {                             //run the returned value through a switch to perform the
                                      //correct operation
            case -1:
                listStack.pushStack(Value);
                break;
            case -2:
                while(listStack.size() != 0)
                {
                    stVal = listStack.popStack();
                    if (stVal != "(")
                        listQueue2.enQueue(stVal);
                    else
                        break;
                }
                break;
            case 0:
                listQueue2.enQueue(Value);
                break;
            default:
 
                while(getOperator(Value) < getOperator(listStack.top()))
                {
                    stVal = listStack.popStack();
                    if (getOperator(stVal) > getOperator(Value))
                        listQueue2.enQueue(stVal);
                }
                listStack.pushStack(Value);
                break;
        }
 
    }
    while(listStack.size() != 0)  //pop the stack into the second queue to print it out
        listQueue2.enQueue(listStack.popStack());
    // print the contents of the second queue
    cout << "Expression in postfix: ";
    listQueue2.print();
 
    //go through the second queue and perform mathmatical calculations
   while(listQueue2.size() != 0)
   {
 
        Value = listQueue2.deQueue();
 
 
        if (getOperator(Value) == 0)
            listStack.pushStack(Value);
        else
        {
            int rVal = toInt(listStack.popStack());
            int lVal = toInt(listStack.popStack());
            if(Value == "+")
                listStack.pushStack(toString(lVal + rVal));
            else if( Value ==  "-")
                listStack.pushStack(toString(lVal - rVal));
            else if(Value == "*")
                listStack.pushStack(toString(lVal * rVal));
            else if(Value == "/")
                listStack.pushStack(toString(lVal / rVal));
            else if(Value == "%")
                listStack.pushStack(toString(lVal % rVal));
            else if(Value == "^")
                listStack.pushStack(toString(pow(double(lVal), double(rVal))));
 
        }
   }
   //print out the only item left on the stack to display the results
    cout << "The result is " << listStack.popStack() << endl;
}
void Input()
{
    string strLine = "";
    string strIn;
    ifstream inFile("data.txt");
    if(!inFile)
    {
        cout << "File not found" << endl;
        exit(1);
    }
    while(getline(inFile, strLine))
    {
        stringstream iss(strLine);   //pass the readLine into the ss
        while(!iss.eof())             //execute following until ss is empty
        {
            iss >> strIn;             //pass item from ss to Value
            listQueue1.enQueue(strIn);  //put item on the queue
        }
        cout << "Expression in infix: ";
        listQueue1.print();
        Evaluate();
 
        system("pause");
    }
    inFile.close();
}
 
 
#endif
 
 
//*********************************************************************
 
#ifndef LIST_H
#define LIST_H
 
#include <stdlib.h>
#include <iostream>
 
using namespace std;
 
template <typename Object>
class List
{
  private:
    // The basic doubly linked list node.
    // Nested inside of List, can be public
    // because the Node is itself private
    struct Node
    {
        Object  data;
        Node   *prev;
        Node   *next;
 
        Node( const Object & d = Object( ), Node * p = NULL, Node * n = NULL )
          : data( d ), prev( p ), next( n ) { }
    };
 
  public:
    class const_iterator
    {
      public:
 
        // Public constructor for const_iterator.
        const_iterator( ) : current( NULL )
          { }
 
        // Return the object stored at the current position.
        // For const_iterator, this is an accessor with a
        // const reference return type.
        const Object & operator* ( ) const
          { return retrieve( ); }
 
        const_iterator & operator++ ( )
        {
            current = current->next;
            return *this;
        }
 
        const_iterator operator++ ( int )
        {
            const_iterator old = *this;
            ++( *this );
            return old;
        }
 
        const_iterator & operator-- ( )
        {
            current = current->prev;
            return *this;
        }
 
        const_iterator operator-- ( int )
        {
            const_iterator old = *this;
            --( *this );
            return old;
        }
 
        bool operator== ( const const_iterator & rhs ) const
          { return current == rhs.current; }
 
        bool operator!= ( const const_iterator & rhs ) const
          { return !( *this == rhs ); }
 
      protected:
        Node *current;
 
        // Protected helper in const_iterator that returns the object
        // stored at the current position. Can be called by all
        // three versions of operator* without any type conversions.
        Object & retrieve( ) const
          { return current->data; }
 
        // Protected constructor for const_iterator.
        // Expects a pointer that represents the current position.
        const_iterator( Node *p ) :  current( p )
          { }
 
        friend class List<Object>;
    };
 
    class iterator : public const_iterator
    {
      public:
 
        // Public constructor for iterator.
        // Calls the base-class constructor.
        // Must be provided because the private constructor
        // is written; otherwise zero-parameter constructor
        // would be disabled.
        iterator( )
          { }
 
        Object & operator* ( )
          { return this->retrieve( ); }
 
        // Return the object stored at the current position.
        // For iterator, there is an accessor with a
        // const reference return type and a mutator with
        // a reference return type. The accessor is shown first.
        const Object & operator* ( ) const
          { return const_iterator::operator*( ); }
 
        iterator & operator++ ( )
        {
            this->current = this->current->next;
            return *this;
        }
 
        iterator operator++ ( int )
        {
            iterator old = *this;
            ++( *this );
            return old;
        }
 
        iterator & operator-- ( )
        {
            this->current = this->current->prev;
            return *this;
        }
 
        iterator operator-- ( int )
        {
            iterator old = *this;
            --( *this );
            return old;
        }
 
      protected:
        // Protected constructor for iterator.
        // Expects the current position.
        iterator( Node *p ) : const_iterator( p )
          { }
 
        friend class List<Object>;
    };
 
  public:
    List( )
      { init( ); }
 
    ~List( )
    {
        clear( );
        delete head;
        delete tail;
    }
 
    List( const List & rhs )
    {
        init( );
        *this = rhs;
    }
 
    const List & operator= ( const List & rhs )
    {
        if( this == &rhs )
            return *this;
        clear( );
        for( const_iterator itr = rhs.begin( ); itr != rhs.end( ); ++itr )
            push_back( *itr );
        return *this;
    }
 
    // Return iterator representing beginning of list.
    // Mutator version is first, then accessor version.
    iterator begin( )
      { return iterator( head->next ); }
 
    const_iterator begin( ) const
      { return const_iterator( head->next ); }
 
    // Return iterator representing endmarker of list.
    // Mutator version is first, then accessor version.
    iterator end( )
      { return iterator( tail ); }
 
    const_iterator end( ) const
      { return const_iterator( tail ); }
 
    // Return number of elements currently in the list.
    int size( ) const
      { return theSize; }
 
    // Return true if the list is empty, false otherwise.
    bool empty( ) const
      { return size( ) == 0; }
 
    void clear( )
    {
        while( !empty( ) )
            pop_front( );
    }
 
// ********************************************************
//  insert_inorder function
//  Inserts the integer passed to it in order
//
// ********************************************************
 
    void insert_inorder(const Object & x)  	//followed by a list number and a value to be inserted
    {
        iterator itr;
        bool bplaced;
        bplaced = false;
        for(itr = this->tail; itr != this->head->next; itr--)
        {
            //if(x < *itr)
            {
                insert(itr, x);
                bplaced = true;
                break;
            }
        }
       // if(!bplaced)
        {
           // insert(end(), x);
        }
    }
 
// ********************************************************
// merge function
// Forms one list from two
//
// ********************************************************
 
   void merge(List ListMerge)
   {
      List<int>::iterator i;
 
      cout << "Before merge: \n";
      cout << "\t1st List Size: " << size() << endl;
      cout << "\t2nd List Size: " << ListMerge.size() << endl << endl;;
 
      cout << "Merge: \n\t";
 
          for(i = ListMerge.begin(); i != ListMerge.end(); i++)
        {
            insert_inorder(*i);
        }
 
        ListMerge.clear();
 
      cout << "After merge: \n";
      cout << "\t1st List Size: " << size() << endl;
      cout << "\t2nd List Size: " << ListMerge.size() << endl << endl;
 
   }
 
// ********************************************************
//  countOcc function
//  Returns the number of occurences of the integer passed
//
// ********************************************************
 
    int countOcc(const Object & x)
    {
        List<int>::iterator i;
        int RtnCnt = 0;
 
        for (i=begin(); i!=end(); i++)
        {
            if (i.current->data == x)
            {
                RtnCnt++;
            }
        }
      return RtnCnt;
    }
 
// ********************************************************
//  removeAll function
//  Deletes all instances of the integer passed
//
// ********************************************************
 
    double removeAll(const Object & x)
    {
        List<int>::iterator i;
        int Removed = 0;
 
        for (i=this->head; i!=this->tail; i++)
        {
            if (i.current->data == x)
            {
                Removed++;
                erase(i);
            }
        }
      return Removed;
    }
 
// ********************************************************
// print function
// Displays the list
//
// ********************************************************
 
//    void print()
//    {
//        List<int>::iterator i;
//
//        if (this->size() == 0)
//        {
//           cout << "This list is Empty!\n\n";
//        }
//        else
//        {
//           cout << "List: \t";
//           for (i=begin(); i!=end(); i++)
//           {
//             cout << "(" << *i << ")";
//           }
//           cout << endl << "\tEnd of List" << endl << endl;
//        }
//    }
 
// ********************************************************
//  sort function
//  Sorts the list in ascending order
//
// ********************************************************
 
    void sort()
    {
        if(theSize == 0)
        {
            cout << "Action not needed list is empty" << endl;
        }
        else
        {
           Node *node1; //node pointer to be used in sort
           Node *node2;//node pointer to be used in sort
 
           int temp = 0; //temp int to hold value during swap
 
           for(node1 = head->next; node1->next!=NULL; node1 = node1->next)
           {
               for(node2 = head->next; node2->next!=NULL; node2 = node2->next)
               {
                   if(node1->data < node2->data)
                   {
                       temp = node1->data;
                       node1->data = node2->data;
                       node2->data = temp;
                   }//end of if
               }//end of second for
           }//end of first for
        }
    }
// ********************************************************
//  reverse function
//  reverses the list
//
// ********************************************************
 
    void reverse()
     {
        iterator front; //iterator item to hold the location of the first node in the list
        if(theSize>=2);
        {
            for(front = this->head->next; front != this->tail->prev;)
            {
                  this->insert(front, this->tail->prev->data); //I used the insert function to push the last node in front of my marked point
                  this->pop_back();  //pop back takes the last node off of the list
            }                       //the marker serves not only as an insertion point but also to tell when the loop is done
 
        }
    }
 
//************************************************************************************
//**************************Start of Added Methods************************************
//************************************************************************************
 
    void List<Object>::enQueue(const Object& object)
    {
        this->push_back(object);
    }
 
    Object deQueue()
    {
        Object temp = *this->begin();          // Building our temp value and setting it to the
                                                    // beginning node value.
        this->erase(this->begin());         // Erasing my beginning node since I have stored
                                                    // the value into my temp object
        return temp;
    }
 
    void print()
    {
        if (theSize == 0)
        {
            cout << "Queue is empty\n";
        }else
        {
            for(iterator i=this->begin(); i != this->end();i++)
            {
                cout << *i << " ";
            }
            cout << endl;
        }
    }
 
    void pushStack( const Object & iData)
    {
        this->push_front(iData);
    }
    //popstack pops the first item off the list and returns that items value
    Object popStack()
    {
        Object top = *this->begin();
        this->erase(this->begin());
        return top;
    }
 
    //top returns the object at the front of the list
    Object top()
    {
        return *this->begin();
    }
//************************************************************************************
//**************************End Added Methods*****************************************
//************************************************************************************
 
    // front, back, push_front, push_back, pop_front, and pop_back
    // are the basic double-ended queue operations.
    Object & front( )
      { return *begin( ); }
 
    const Object & front( ) const
      { return *begin( ); }
 
    Object & back( )
      { return *--end( ); }
 
    const Object & back( ) const
      { return *--end( ); }
 
    void push_front( const Object & x )
      { insert( begin( ), x ); }
 
    void push_back( const Object & x )
      { insert( end( ), x ); }
 
    void pop_front( )
      { erase( begin( ) ); }
 
    void pop_back( )
      { erase( --end( ) ); }
 
    // Insert x before itr.
    iterator insert( iterator itr, const Object & x )
    {
        Node *p = itr.current;
        theSize++;
        return iterator( p->prev = p->prev->next = new Node( x, p->prev, p ) );
    }
 
    // Erase item at itr.
    iterator erase( iterator itr )
    {
        Node *p = itr.current;
        iterator retVal( p->next );
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
        theSize--;
 
        return retVal;
    }
 
    iterator erase( iterator start, iterator end )
    {
        for( iterator itr = start; itr != end; )
            itr = erase( itr );
 
        return end;
    }
 
  private:
    int   theSize;
    Node *head;
    Node *tail;
 
    void init( )
    {
        theSize = 0;
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prev = head;
    }
};
 
#endif

Open in new window

0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 2000 total points
ID: 24246998
>>>> using namespace std;
The using clause shouldn't be used in header files. Instead use the std:: prefix, e. g. std::string , for any STL object.

In cpp files you can add the 'using namespace std;'  if there is no name conflict. But if you have the using clause in the header duplicate names of different namespaces couldn't be resolved in cpp.

>>>> int getOperator(string sOper)
>>>> {

If you put the implementation of non-template and non-inline functions into a header file, that header can be included by one cpp only. If a second cpp file also includes the header, the linker would compülain about duplicate modules. So, you better move the function implementation like for getOperator into a .cpp file.

>>>>     if(sOper == "+")
>>>>         return 1;
>>>>     else if(sOper ==  "-")

as long as the operators have only one single char you could do

   char c = s.c_str()[0];  // that also covers empty strings
   switch(c)
   {
     case '+':
     case '-':   return 1;
     case '*':
     case '/':
     case %:   return 1;
     case '^':  return 3;
     case '(':   return -1;
     case ')':   return -2;
   }
   return 0;


>>>> while(!iss.eof())
 
Better do

    while (iss >> strIn)
    {
        listQueue1.enQueue(strIn);  //put item on the queue
    }

That also handles errors of the streaming while your code may run infinitely on error.

FYI: the operator>> (istream& is, const string& s)  which does the iss>>strIn  returns a reference to the is argument after streaming. You can test that return object on 'bool' which will return 'false' on eof or fail condition.  

0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
Suggested Courses

850 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question