Thread: Queue and Stack: Comparing help!!! (palindrome)

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    34

    Queue and Stack: Comparing help!!! (palindrome)

    This may be a little long, but please bear with me. I really need help on this.
    I have excluded my header files for space (as you can tell probably whats in them anyway, if you need them let me know)
    Code:
    //----------------------------------------------------------------------
    //  IMPLEMENTATION FILE (Queue.cxx)
    //  This module exports an ADT for a bounded queue of ItemType.
    //  The maximum queue length is MAX_LENG.
    //  Queue representation: a ring buffer in a vector of
    //                        size MAX_LENG + 1
    //----------------------------------------------------------------------
    #include <iostream.h>
    #include "queue.h"
    const int VEC_SIZE = MAX_LENG + 1;
    
    // Private members of class:
    //     int data[MAX_LENG+1];  // Vector representing the queue
    //     int front;             // (Subscript of queue front) - 1
    //     int rear;              // Subscript of queue rear
    //
    // NOTE:  At all times, at least one element of the data vector
    //        remains unused
    
    
    void Queue::MakeEmpty()
         //.................................................................
         // Poat: front and rear have been reset to the empty state
    {
         front = rear = VEC_SIZE - 1;
    }	
    
    Queue::Queue()
        //..................................................................
        // Constructor
        // POST: front == 0  &&  rear == 0
        //..................................................................
    {
        front = rear = VEC_SIZE - 1;
    }
    
    bool Queue::IsEmpty() const
        //..................................................................
        // POST: FCTVAL == (rear == front)
        //..................................................................
    {
        return (rear == front);
    }
    
    bool Queue::IsFull() const
        //..................................................................
        // POST: FCTVAL == ((rear + 1) MOD VEC_SIZE == front)
        //..................................................................
    {
        return ((rear + 1) % VEC_SIZE == front);
    }
    
    void Queue::Enqueue(ItemType newItem)
        //..................................................................
        // PRE:  (rear + 1) MOD VEC_SIZE != front
        //    && Assigned(newItem)
        // POST: rear == (rear<entry> + 1) MOD VEC_SIZE
        //    && data[rear] == newItem
        //..................................................................
    {
        rear = (rear + 1) % VEC_SIZE;
        data[rear] = newItem;
    }
    
    void Queue::Dequeue(ItemType& itemInQueue)
        //..................................................................
        // PRE:  rear != front
        // POST: front == (front<entry> + 1) MOD VEC_SIZE
        //..................................................................
    {
        front = (front + 1) % VEC_SIZE;
        itemInQueue = data[front];
    }
    
    
    void Queue::PrintFandR()
    {
        cout << "F: " << front << endl;
        cout << "R: " << rear << endl;
        cout << endl << endl;
    }
    
    
    //IMPLEMENTATION FILE FOR STACK (STACK.CXX)
    #include "stack.h"
    
    StackType::StackType( )
    //------------------------------------------------
    // Default Constructor
    //------------------------------------------------
    {
    	top = -1;
    }
    
    void StackType::MakeEmpty( ) 
    //---------------------------------------------------
    // PRE:   None.
    // POST:  Stack is empty.
    //---------------------------------------------------
    {
    	top = -1;
    }
    
    bool StackType::IsEmpty( ) const
    //---------------------------------------------------
    // PRE:   Stack has been initialized.
    // POST:  Function value = (stack is empty)
    //---------------------------------------------------
    {
    	return ( top == -1 );
    }
    
    bool StackType::IsFull( ) const
    //---------------------------------------------------
    // PRE:   Stack has been initialized.
    // POST:  Function value = (stack is full)
    //---------------------------------------------------
    {
    	return  ( top == MAX_ITEMS-1);
    }
    
    void StackType::Push ( ItemType newItem )
    //------------------------------------------------------
    // PRE:  Stack has been initialized and is not full.
    // POST: newItem is at the top of the stack.
    //------------------------------------------------------
    {
    	top++;
    	items[top] = newItem;	
    }
    
    void StackType::Pop ( ItemType&  item )
    //------------------------------------------------------
    // PRE:  Stack has been initialized and is not empty.
    // POST: Top element has been removed from stack.
    //	  item is a copy of removed element.
    //------------------------------------------------------
    {
      	item = items[top];
      	top--;
    }
    
    //IMPLEMENTATION FILE FOR ITEMTYPE
    #include "ItemType.h"
    
    void ItemType::ReadInStackQueue(ifstream inFile)
    {
       char c;
       inFile >> c;
    }
    
    void ItemType::ReadCharacter(ifstream& inFile)
    {
       inFile >> newItem;
    }
    
    void ItemType::WriteOut(ofstream& outFile)
    {
       outFile << newItem;
    }
    
    /////MAIN!!!!!
    
    #include "stack.h"
    #include <fstream>
    
    using namespace std;
    
    int main()
    {
       ifstream inFile;
       ofstream outFile;
       inFile.open("in.data");
       outFile.open("out.data");
    
       Queue q;
       StackType s;
       ItemType data;
       ItemType copy;
       int counter = 0;
       int mismatch = 0;  
    
       char ch;
       data.ReadCharacter(inFile);
       copy = data;
       while (inFile)
       {
          s.Push(data);
          q.Enqueue(copy);
          data.ReadCharacter(inFile);
          copy = data;
          counter++;   
       }
    
       while (counter > 0)
       {
          s.Pop(data);
          q.Dequeue(copy);
          if (copy == data)
             mismatch++;
          copy.WriteOut(outFile);
          counter--;
       }   
    
       if (mismatch > 0)
          outFile << ": >>> This is not a palindrome!" << endl;
       else
          outFile << ": >>> This is a palindrome!" << endl;
    
       return 0;
    }
    The part in red i cannot due as it gives me an error. But I need to pop an element from the top of the stack, dequeue, and then compare those two till it is done to figure out if it is a palindrome or not. Any help I would GREATLY appreciate. Thank you,
    Aaron

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Well, I don't see any overloaded equality operator (==) defined for the ItemType class. I'd be willing to bet that's probably the problem with that one line you highlighted in red above.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User
    Join Date
    Mar 2005
    Posts
    34
    How do i define that operator in the class? Or, is there a better way of comaparing the two items after they have been popped and dequeued? I have tried if (s.Pop(data) == q.Dequeue(copy)) but then i get an illegal use of void error.

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Quote Originally Posted by advocation
    How do i define that operator in the class? Or, is there a better way of comaparing the two items after they have been popped and dequeued?
    I'm only guessing as to the contents of your ItemType class but...

    Code:
    // In ItemType header file...
    class ItemType
    {
        char newItem;  // Is this a member of your class?
    public:
        friend bool operator==(const ItemType& lhs, const ItemType& rhs);
    };
    
    // In ItemType implementation file...
    bool operator==(const ItemType& lhs,const ItemType& rhs)
    {
        return lhs.newItem == rhs.newItem;
    }
    Quote Originally Posted by advocation
    I have tried if (s.Pop(data) == q.Dequeue(copy)) but then i get an illegal use of void error.
    That might work if those functions both returned comparable types (i.e. chars). As is, they currently both seem to return type void so in essence you are saying if( void == void ), hence the error.

    My 1000th post WooHoo!
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    Registered User
    Join Date
    Mar 2005
    Posts
    34
    But you are correct in saying that because i get this error
    Code:
    error: no match for 'operator=='

  6. #6
    Registered User
    Join Date
    Mar 2005
    Posts
    34
    WooHoo!! It works...almost It is probably something else, but it works with a four letter work, such as abab, but not any 3 letter word, such as dad.

  7. #7
    Registered User
    Join Date
    Mar 2005
    Posts
    34
    nevermind, my own stupidity, i should be able to get it to work. But one last question; Right now i am reading each character in one by one, while that works great for one string in the input file, it doesn't work for multiple strings. IE: dad (return) kitty (return) mom (return). Any idea on how i should go about fixing this (character string?). Thanks so much for your help.

  8. #8
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Quote Originally Posted by advocation
    nevermind, my own stupidity, i should be able to get it to work. But one last question; Right now i am reading each character in one by one, while that works great for one string in the input file, it doesn't work for multiple strings. IE: dad (return) kitty (return) mom (return). Any idea on how i should go about fixing this (character string?). Thanks so much for your help.
    Why do you need to use the ItemType class at all? Can't you simply have a stack and queue of chars instead of a stack and queue of ItemTypes? I say this because it is adding needless complexity to the issue if it doesn't need to be there. It would much simpler doing this without the ItemType class in the way of things. Also, both the stack and queue containers have always both used the same pop/push syntax for adding/removing elements... none of this Enqueue/Dequeue business (bleh).

    What is the purpose of this palindrome program? Is it an exercise on simply testing whether a given set of strings is a palindrome or not and you just happened to choose to implement it using a stack and queue? If so then there is a one or two line solution to the "Is this string a palindrome?" question using the STL equal function. Or... why not use the STL stack and queue containers.

    If it is an exercise in implementing the queue and stack containers and it just happens to be using a palindrome program as a test bed, then I still might suggest first implementing the program using the built in STL stack and queue containers to see how it should work and then (without changing any of the logic in the code itself) remove the STL objects and replace them with your own and see how you fair then.

    That said, in answer to your question on how to handle multiple strings from a file I would have a basic structure as follows:

    Code:
    string word;
    ifstream infile("in.data");
    // Also declare your stack and queue containers here
    
    ...
    
    // Loop through the file a line of data at a time
    while( getline(infile,word) )
    {
        // Go through the string "word" one char at a time and push the
        // characters onto both the stack and the queue
    
        ...
    
        // After the whole string has been push onto both the stack and queue
        // you must now pop them both and do the compare
    
        ....
    
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  9. #9
    Registered User
    Join Date
    Mar 2005
    Posts
    34
    Actually, the reason why I am doing it this way is because my professor told our class too :P. This was an assignment that I was stuck on, and it was basically a test to see if we could implement both a stack and queue. But thank you for your help.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  2. Pushing a Queue onto a Stack?
    By MiroMage in forum C Programming
    Replies: 5
    Last Post: 10-14-2008, 09:23 PM
  3. Queue Stack Palindrome
    By silicon in forum C++ Programming
    Replies: 20
    Last Post: 07-15-2004, 03:38 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. queue / stack
    By smd in forum C++ Programming
    Replies: 2
    Last Post: 07-26-2002, 01:30 PM