Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › C++ How to create a Queue that is implemented using a List?
New Posts  All Forums:Forum Nav:

C++ How to create a Queue that is implemented using a List?

post #1 of 4
Thread Starter 
Yes this is for a beginning level Comp Sci course I am taking at college... We are learning about Queues and implementing them using linked listed. I have already created my own class for both List and Queue from the text book (I'm not using the STL). I need to test the program but i'm not sure of the correct syntax to use in the main.

I basically want to do something like this but using my Queue and List classes...
Code:
queue<int, list<int> > myQueue;


Here is my main() basically empty now... Warning: Spoiler! (Click to show)
Code:
/** @file Main.cpp */

#include <iostream>
#include "QueueL.h"

using namespace std;

int main()
{
        List aList;

        Queue aQueue;


        system("pause");
        return 0;
} // end main

The header files... Warning: Spoiler! (Click to show)
Code:
#include "ListP.h"  //  ADT list operations
//#include "QueueException.h"
typedef ListItemType QueueItemType;
 
/** @class Queue
 * ADT queue - ADT list implementation. */
class Queue
{
public:
// constructors and destructor:
 
   /** Default constructor. */
   Queue();
 
   /** Copy constructor.
    * @param Q  The Queue to copy. */
   Queue(const Queue& Q);
 
   /** Destructor. */
   ~Queue();
 
// Queue operations:
   bool isEmpty() const;
   void enqueue(const QueueItemType& newItem);
   void dequeue();
   void dequeue(QueueItemType& queueFront);
   void getFront(QueueItemType& queueFront) const;
 
private:
   List aList;  // list of queue items
}; // end Queue
// End of header file.

Code:
/** @file ListP.h */
 
typedef int ListItemType;

class List
{
public:
// Constructors and destructor:
 
   /** Default constructor. */
   List();
 
   /** Copy constructor.
    * @param aList The list to copy. */
   List(const List& aList);
 
   /** Destructor. */
   ~List();
 
// List operations:
   bool isEmpty() const;
   int getLength() const;
   void insert(int index, const ListItemType& newItem);
   void remove(int index);
   void retrieve(int index, ListItemType& dataItem) const;
 
private:
   /** A node on the list. */
   struct ListNode
   {
      /** A data item on the list. */
      ListItemType item;
      /** Pointer to next node. */
      ListNode    *next;
   }; // end ListNode
 
   /** Number of items in list. */
   int size;
   /** Pointer to linked list of items. */
   ListNode *head;
 
   ListNode *find(int index) const;
}; // end List
// End of header file.

And the other .cpp files... Warning: Spoiler! (Click to show)
Code:
/** @file QueueL.cpp */

#include "QueueL.h"  // header file

Queue::Queue()
{
}  // end default constructor
 
Queue::Queue(const Queue& Q): aList(Q.aList)
{
}  // end copy constructor
 
Queue::~Queue()
{
}  // end destructor
 
bool Queue::isEmpty() const
{
   return (aList.getLength() == 0);
}  // end isEmpty
 
void Queue::enqueue(const QueueItemType& newItem)
{
   //try
   //{
      aList.insert(aList.getLength()+1, newItem);
   //}
   //catch (ListException e)
   //{
   //   throw QueueException("QueueException: cannot enqueue item");
   //}
   //catch (ListIndexOutOfRangeException e)
   //{
   //   throw QueueException("QueueException: cannot enqueue item");
   //}  // end try
}  // end enqueue
 
void Queue::dequeue()
{
   if (aList.isEmpty())
   {
                //"Error";
   }
   else
   {
      aList.remove(1);
   }
}  // end dequeue
 
void Queue::dequeue(QueueItemType& queueFront)
{
   if (aList.isEmpty())
   {
                //"Error";
   }
   else
   {
      aList.retrieve(1, queueFront);
      aList.remove(1);
   }
}  // end dequeue
 
void Queue::getFront(QueueItemType& queueFront) const
{
   if (!aList.isEmpty())
   {
                //"Error";
   }
   else
   {
      aList.retrieve(1, queueFront);
   }
}  // end getFront
// End of implementation file.

Code:
/** @file ListP.cpp
 *  ADT list - Pointer-based implementation. */

#include <iostream>
#include <cstddef>     // for NULL
#include <new>         // for bad_alloc
#include "ListP.h"     // header file
 

// definitions of methods follow:
//   . . .

List::List()
{
}

List::List(const List& aList): size(aList.size)
{
   if (aList.head == NULL)
   {
      head = NULL;  // original list is empty
   } 
   else
   {  // copy first node
      head = new ListNode;
      head->item = aList.head->item;
 
      // copy rest of list
      ListNode *newPtr = head;  // new list pointer
      // newPtr points to last node in new list
      // origPtr points to nodes in original list
      for (ListNode *origPtr = aList.head->next; origPtr != NULL; origPtr = origPtr->next)
      {  
                 newPtr->next = new ListNode;
         newPtr = newPtr->next;
                 newPtr->item = origPtr->item;
      }  // end for
 
      newPtr->next = NULL;
   }  // end if
}  // end copy constructor

List::~List()
{
   while (!isEmpty())
      remove(1);
}  // end destructor

bool List::isEmpty() const
{
   return size == 0;
}  // end isEmpty
 
int List::getLength() const
{
   return size;
}  // end getLength
 
List::ListNode *List::find(int index) const
{
   if ( (index < 1) || (index > getLength()) )
   {
      return NULL;
   }
 
   else  // count from the beginning of the list.
   {  
           ListNode *cur = head;
       for (int skip = 1; skip < index; ++skip)
           {
         cur = cur->next;
           }
      return cur;
   }  // end if
}  // end find
 

void List::retrieve(int index,ListItemType& dataItem) const
{
   if ( index < 1 || index > getLength() )
   {
           //error
   }
   else
   {  // get pointer to node, then data in node
      ListNode *cur = find(index);
      dataItem = cur->item;
   }  // end if
}  // end retrieve


void List::insert(int index, const ListItemType& newItem)
{
   int newLength = getLength() + 1;
 
   if ((index,1)||(index > newLength))
   {
           //error
   }
   else
   {
                ListNode *newPtr = new ListNode;
                size = newLength;
                newPtr->item = newItem;

         // attach new node to list
                if (index == 1)
                {  // insert new node at beginning of list
                        newPtr->next = head;
                        head = newPtr;
                }
                else
                {  ListNode *prev = find(index-1);
            // insert new node after node
            // to which prev points
            newPtr->next = prev->next;
                        prev->next = newPtr;
                }  // end if
   } //end if
}  // end insert


void List::remove(int index)
{
   ListNode *cur;
   if ((index < 1) || (index > getLength()))
   {
           //error
   }
   else
   {
     --size;
      if (index == 1)
      {  // delete the first node from the list
         cur = head;  // save pointer to node
         head = head->next;
      }
 
      else
      {  ListNode *prev = find(index - 1);
         // delete the node after the node to which prev points
         cur = prev->next;  // save pointer to node
                 prev->next = cur->next;
      }  // end if
 
      // return node to system
      cur->next = NULL;
      delete cur;
      cur = NULL;
   }  // end if
}  // end remove

The other stuff should be correct I'm just not sure how to declare it in the main headscratch.gif ...as you can see all I did was create a list and queue but not a Queue implemented using the list. I assume it has something to do with the way the constructors are setup.
Edited by Accuracy158 - 4/2/12 at 1:09am
Main Desktop PC
(23 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i7 5820k ASUS x99 Deluxe EVGA GTX 1080 FTW 4 x 4GB 2800 DDR4 Corsair Vengeance 
Hard DriveHard DriveHard DriveHard Drive
256GB Samsung 840 Pro 240GB OCZ ARC100 3TB 7200 RPM Seagate Barracuda 2TB 7200 RPM Seagate Barracuda 
Optical DriveCoolingOSOS
ASUS 24x DVD/Burner Custom Loop Windows 10 Pro 64bit Debian Linux Distro 
MonitorMonitorKeyboardPower
Acer Predator XB270HU ACHIEVA Shimian QH2700 IPSMS Ducky Shine 2 (White LED/Brown Switches) EVGA 1300w G2 + Individually sleeved cables 
CaseMouseMouse PadAudio
Gun Metal NZXT Switch 810 EVGA Troq x10 Logitech G440 Onkyo TX-NR646 
Other
Bitfenix Recon Fan Controller 
  hide details  
Reply
Main Desktop PC
(23 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i7 5820k ASUS x99 Deluxe EVGA GTX 1080 FTW 4 x 4GB 2800 DDR4 Corsair Vengeance 
Hard DriveHard DriveHard DriveHard Drive
256GB Samsung 840 Pro 240GB OCZ ARC100 3TB 7200 RPM Seagate Barracuda 2TB 7200 RPM Seagate Barracuda 
Optical DriveCoolingOSOS
ASUS 24x DVD/Burner Custom Loop Windows 10 Pro 64bit Debian Linux Distro 
MonitorMonitorKeyboardPower
Acer Predator XB270HU ACHIEVA Shimian QH2700 IPSMS Ducky Shine 2 (White LED/Brown Switches) EVGA 1300w G2 + Individually sleeved cables 
CaseMouseMouse PadAudio
Gun Metal NZXT Switch 810 EVGA Troq x10 Logitech G440 Onkyo TX-NR646 
Other
Bitfenix Recon Fan Controller 
  hide details  
Reply
post #2 of 4
You may find template classes helpful.. Are you sure you can't use the STL?
    
CPUMotherboardGraphicsGraphics
FX-8350 Asus Crosshair V MSI GTX460 Hawk 1gb MSI GTX460 Hawk 1gb 
RAMHard DriveHard DriveHard Drive
Kingston HyperX 8gb (2x4gb) Crucial M4 64GB Samsung F3 1TB Western Digital 320GB 
CoolingOSMonitorMonitor
Custom WC Windows 7 Ultimate X64 Dell E2311H Dell E2311H 
MonitorKeyboardPowerCase
LH 23EN43 Ducky Year of the Dragon 2012 SilverStone Strider 1000W-P Corsair 800D 
Audio
Asus Xonar Essence STX 
  hide details  
Reply
    
CPUMotherboardGraphicsGraphics
FX-8350 Asus Crosshair V MSI GTX460 Hawk 1gb MSI GTX460 Hawk 1gb 
RAMHard DriveHard DriveHard Drive
Kingston HyperX 8gb (2x4gb) Crucial M4 64GB Samsung F3 1TB Western Digital 320GB 
CoolingOSMonitorMonitor
Custom WC Windows 7 Ultimate X64 Dell E2311H Dell E2311H 
MonitorKeyboardPowerCase
LH 23EN43 Ducky Year of the Dragon 2012 SilverStone Strider 1000W-P Corsair 800D 
Audio
Asus Xonar Essence STX 
  hide details  
Reply
post #3 of 4
Thread Starter 
Quote:
Originally Posted by FiX View Post

You may find template classes helpful.. Are you sure you can't use the STL?

Yes we are supposed to be using the programs we worked with before.
Main Desktop PC
(23 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i7 5820k ASUS x99 Deluxe EVGA GTX 1080 FTW 4 x 4GB 2800 DDR4 Corsair Vengeance 
Hard DriveHard DriveHard DriveHard Drive
256GB Samsung 840 Pro 240GB OCZ ARC100 3TB 7200 RPM Seagate Barracuda 2TB 7200 RPM Seagate Barracuda 
Optical DriveCoolingOSOS
ASUS 24x DVD/Burner Custom Loop Windows 10 Pro 64bit Debian Linux Distro 
MonitorMonitorKeyboardPower
Acer Predator XB270HU ACHIEVA Shimian QH2700 IPSMS Ducky Shine 2 (White LED/Brown Switches) EVGA 1300w G2 + Individually sleeved cables 
CaseMouseMouse PadAudio
Gun Metal NZXT Switch 810 EVGA Troq x10 Logitech G440 Onkyo TX-NR646 
Other
Bitfenix Recon Fan Controller 
  hide details  
Reply
Main Desktop PC
(23 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i7 5820k ASUS x99 Deluxe EVGA GTX 1080 FTW 4 x 4GB 2800 DDR4 Corsair Vengeance 
Hard DriveHard DriveHard DriveHard Drive
256GB Samsung 840 Pro 240GB OCZ ARC100 3TB 7200 RPM Seagate Barracuda 2TB 7200 RPM Seagate Barracuda 
Optical DriveCoolingOSOS
ASUS 24x DVD/Burner Custom Loop Windows 10 Pro 64bit Debian Linux Distro 
MonitorMonitorKeyboardPower
Acer Predator XB270HU ACHIEVA Shimian QH2700 IPSMS Ducky Shine 2 (White LED/Brown Switches) EVGA 1300w G2 + Individually sleeved cables 
CaseMouseMouse PadAudio
Gun Metal NZXT Switch 810 EVGA Troq x10 Logitech G440 Onkyo TX-NR646 
Other
Bitfenix Recon Fan Controller 
  hide details  
Reply
post #4 of 4
To set it up like you had in the OP, have a class like so:
Code:
template <class T, class Y>
class queue
{
public:
    queue(T firstType, Y secondType);
    ~queue();
    ...
   T storedFirstType;
   Y storedSecondType;
};

And then your list class like so:
Code:
template <class T>
class list
{
public:
   list(T type);
   ~list();
   ...
   T storedType;
};
Not sure if this is helpful or not, but it should let you go:
Code:
queue<int, list<int>> myQueue;
Like you wanted
Edited by FiX - 4/2/12 at 1:29am
    
CPUMotherboardGraphicsGraphics
FX-8350 Asus Crosshair V MSI GTX460 Hawk 1gb MSI GTX460 Hawk 1gb 
RAMHard DriveHard DriveHard Drive
Kingston HyperX 8gb (2x4gb) Crucial M4 64GB Samsung F3 1TB Western Digital 320GB 
CoolingOSMonitorMonitor
Custom WC Windows 7 Ultimate X64 Dell E2311H Dell E2311H 
MonitorKeyboardPowerCase
LH 23EN43 Ducky Year of the Dragon 2012 SilverStone Strider 1000W-P Corsair 800D 
Audio
Asus Xonar Essence STX 
  hide details  
Reply
    
CPUMotherboardGraphicsGraphics
FX-8350 Asus Crosshair V MSI GTX460 Hawk 1gb MSI GTX460 Hawk 1gb 
RAMHard DriveHard DriveHard Drive
Kingston HyperX 8gb (2x4gb) Crucial M4 64GB Samsung F3 1TB Western Digital 320GB 
CoolingOSMonitorMonitor
Custom WC Windows 7 Ultimate X64 Dell E2311H Dell E2311H 
MonitorKeyboardPowerCase
LH 23EN43 Ducky Year of the Dragon 2012 SilverStone Strider 1000W-P Corsair 800D 
Audio
Asus Xonar Essence STX 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › C++ How to create a Queue that is implemented using a List?