Circular linked queue

[zeid]

Hi all, I need to do a program to do something like the CPU scheduling using Round Robin technique .. The whole idea is in my mind but the problem with me that I'm having a problem in implementing the queue functions such as "Append" and "serve" As a circular linked queue.

These are my 2 classes:

class process
{
public:
	char name;
	int burst_time;
	process *next;
	process() {next = NULL;}
	process(char name1, int burst_time1, process *next1 = NULL)
	{
		name = name1;
		burst_time = burst_time1;
		next = next1;
	}
};

class queue
{
public:
	queue() {front= NULL; rear = NULL;}
	void append(char name, int burst_time);
	void serve();
	bool isEmpty() {return rear == front;}
private:
	process front;
	process rear;
};

Can someone please just show me how to do these two functions: "Append" and "Serve" one to add to list and the other to delete.

I tried alot but the whole circular linked queue idea is complicated in my mind.

Thanks very much, I really appreciate it if some one just implement these two functions for me using the features in my two classes.

zeid

[crei]

From what I can see I don't think that you need a queue class because the STL already contains collections which are prefect for RR Scheduling. If on the other hand you do need a class for queue, you can just inherit the core behavior of the collection. Here is an example:

#include <queue>
class ProcessQueue : public std::queue<process>
{
  /* functions */
};

Here is a way to implement the circular behavior using a list. Note that doing this is kind of hacky.

#include <list>
#include <string>
#include <iostream>

class process
{
public:
  process(const std::string& name, int burst_time)
    : mName (name),
      mBurstTime (burst_time),
      mIsBlocked (false) {}
  const std::string& getName() const
  { return mName; }
  int getQuantum() const
  { return mBurstTime; }
  bool isBlocked() const
  { return mIsBlocked; }
  void setIsBlocked(bool blocked = false)
  { mIsBlocked = blocked; }
private:
  std::string mName;
  int mBurstTime;
  bool mIsBlocked;
};

int main() {
  std::list<process> processList;

  processList.push_back (process ("text_editor", 100));
  processList.push_back (process ("shell", 100));
  processList.push_back (process ("player", 100));

  std::list<process>::const_iterator iter;
  for (iter = processList.begin(); /*Loop Forever*/;) {
    if (!iter->isBlocked()) {
      std::cout << "Running " << iter->getName() << std::endl;
    }
    //To make list circular
    if (++iter == processList.end()){
      iter = processList.begin();
    }
  }
  return 0;
}

[wildfrog]

Here is a way to implement the circular behavior using a list. Note that doing this is kind of hacky.

Another, maybe less 'hacky' approach is to use a circular iterator that works with any STL container. That way the 'curcular' effect is build into the iterator itself, and the iterator automatically loop back to the beginning of the container when you reach the end.

You can search the web for implementations of circular iterators.

- petter

[zeid]

Thank you .. BUT this is an assigment so I should use my dr's ways and techniques .. anyway I've done some code but I don't know why there is a lot of errors in it.

#include <iostream>
using namespace std;

int time_quantum;

class process
{
public:
	char name;
	int burst_time;
	process *next;
	process() {next = NULL;}
	process(char name1, int burst_time1, process *next1 = NULL)
	{
		name = name1;
		burst_time = burst_time1;
		next = next1;
	}
};

class queue
{
public:
	queue() {front = NULL; rear = NULL;}
	void append(const char name, int burst_time);
	void serve();
	bool isEmpty() {return rear == front;}
private:
	process front;
	process rear;
};

void queue::append(const char name, int burst_time)
{
	process *temp;
	temp = new process(name, burst_time);

	if (!isEmpty())
	{
		rear->next = temp;
		rear = rear->next;
	}
	else
	{
		front = temp;
		rear = temp;
	}
}

void queue::serve()
{
	process *temp = front;
	front = front->next;
	delete temp;
	rear->next = front;
}

int main()
{
	queue myqueue;
	int number;
	char name;
	int burst_time;
	int quantum_time;

	cout << "Enter number of processes: " << endl;
	cin >> number;

	for (int i = 0; i <= number; i++)
	{
		cout << "Enter Process " << i << " Info (name, burst time):" << endl;
		cin >> name >> burst_time;
		myqueue.append(name, burst_time);
	}

	cout << "Enter Quantum time:" << endl;
	cin >> quantum_time;
	
	process *temp = front;

	while (!myqueue.isEmpty())
	{
		if (time_quantum - temp->burst_time > 0)
		{
			myqueue.append(name, burst_time);
			myqueue.serve();
		}
		else
		{
			cout << "Process " << temp->name << " with Quantum " << temp->burst_time << " was finished" << endl;
			myqueue.serve();
		}
	}
	
	return 0;
}

Errors are:

--------------------Configuration: ROUND ROBIN - Win32 Debug--------------------
Compiling...
Round_Robin.cpp
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(28) : error C2679: binary '=' : no operator defined which takes a right-hand operand of type 'const int' (or there is no acceptable conve
rsion)
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(28) : error C2679: binary '=' : no operator defined which takes a right-hand operand of type 'const int' (or there is no acceptable conve
rsion)
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(31) : error C2784: 'bool __cdecl std:perator ==(const class std::allocator<_Ty> &,const class std::allocator<_U> &)' : could not deduce
template argument for 'const class std::allocator<_Ty> &' from 'class process'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(31) : error C2784: 'bool __cdecl std:perator ==(const class std::istreambuf_iterator<_E,_Tr> &,const class std::istreambuf_iterator<_E,
_Tr> &)' : could not deduce template argument for 'const class std::istreambuf_iterator<_E,_Tr> &' from 'class process'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(31) : error C2784: 'bool __cdecl std:perator ==(const class std::reverse_iterator<_RI,_Ty,_Rt,_Pt,_D> &,const class std::reverse_iterat
or<_RI,_Ty,_Rt,_Pt,_D> &)' : could not deduce template argument for 'const class std::reverse_iterator<_RI,_Ty,_Rt,_Pt,_D> &' from 'class process'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(31) : error C2784: 'bool __cdecl std:perator ==(const struct std:air<_T1,_T2> &,const struct std:air<_T1,_T2> &)' : could not deduc
e template argument for 'const struct std:air<_T1,_T2> &' from 'class process'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(31) : error C2676: binary '==' : 'class process' does not define this operator or a conversion to a type acceptable to the predefined ope
rator
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(44) : error C2819: type 'process' does not have an overloaded member 'operator ->'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(11) : see declaration of 'process'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(44) : error C2227: left of '->next' must point to class/struct/union
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(45) : error C2819: type 'process' does not have an overloaded member 'operator ->'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(11) : see declaration of 'process'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(45) : error C2227: left of '->next' must point to class/struct/union
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(49) : error C2679: binary '=' : no operator defined which takes a right-hand operand of type 'class process *' (or there is no acceptable
conversion)
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(50) : error C2679: binary '=' : no operator defined which takes a right-hand operand of type 'class process *' (or there is no acceptable
conversion)
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(56) : error C2440: 'initializing' : cannot convert from 'class process' to 'class process *'
No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(57) : error C2819: type 'process' does not have an overloaded member 'operator ->'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(11) : see declaration of 'process'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(57) : error C2227: left of '->next' must point to class/struct/union
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(59) : error C2819: type 'process' does not have an overloaded member 'operator ->'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(11) : see declaration of 'process'
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(59) : error C2227: left of '->next' must point to class/struct/union
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(83) : error C2065: 'front' : undeclared identifier
C:\Documents and Settings\Computer\My Documents\My Homeworks\DATA STRUCTURES\QUEUES\ROUND ROBIN\Round_Robin.cpp(83) : error C2440: 'initializing' : cannot convert from 'int' to 'class process *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
Error executing cl.exe.

Round_Robin.obj - 20 error(s), 0 warning(s)

[zeid]

opps i forgot to add * after process

[MikeAThon]

If you are looking for further guidance, Boost has an almost-approved circular ring buffer at http://boost.cvs.sourceforge.net/*ch...ar_buffer.html , as described in this thread: http://www.codeguru.com/forum/showthread.php?p=1542018

Mike