getting the length of a simple queue

Question

I am taking a C++ data structures class and the problem I am working on is to write a client function that gets the length of the queue without changing the queue using the function prototype:

int GetLength(QueType queue);

In my mind this is very simple because when you pass the queue object to a function it is working with a copy so if I iterate and dequeue until it's empty I know how many items are in the queue.

The QueType is a simple queue type provided by the text, ItemType is defined as

typedef char ItemType;

My simple driver code is below:

#include "QueType.h" using namespace std; int GetLength(QueType queue); int main() { ItemType item; //typedef char //initialize and fill the queue QueType que(5); que.Enqueue('A'); que.Enqueue('B'); que.Enqueue('C'); que.Enqueue('D'); que.Enqueue('E'); cout << "The length of the queue is " << GetLength(que) << endl; while (!que.IsEmpty()) { que.Dequeue(item); cout << "Dequeue item of queue: " << item << endl; } system("PAUSE"); return EXIT_SUCCESS; } int GetLength(QueType queue) { int cnt = 0; ItemType item; while (!queue.IsEmpty()) { queue.Dequeue(item); cout << "Dequeue item of local copy of queue: " << item << endl; cnt++; } return cnt; }

My expected output would be:

Dequeue item of local copy of queue: A Dequeue item of local copy of queue: B Dequeue item of local copy of queue: C Dequeue item of local copy of queue: D Dequeue item of local copy of queue: E The length of the queue is 5 Dequeue item of queue: A Dequeue item of queue: B Dequeue item of queue: C Dequeue item of queue: D Dequeue item of queue: E Press any key to continue . . .

But I am getting this:

Dequeue item of local copy of queue: A Dequeue item of local copy of queue: B Dequeue item of local copy of queue: C Dequeue item of local copy of queue: D Dequeue item of local copy of queue: E The length of the queue is 5 Dequeue item of queue: p Dequeue item of queue: ↨ Dequeue item of queue: 7 Dequeue item of queue: Dequeue item of queue: ─ Press any key to continue . . .

QueType.h: class FullQueue {};

class EmptyQueue {}; typedef char ItemType; class QueType { public: QueType(); QueType(int max); ~QueType(); void MakeEmpty(); bool IsEmpty() const; bool IsFull() const; void Enqueue(ItemType newItem); void Dequeue(ItemType& item); private: int front; int rear; ItemType* items; int maxQue; };

QueType.cpp:

#include "QueType.h" QueType::QueType(int max) { maxQue = max + 1; front = maxQue - 1; rear = maxQue - 1; items = new ItemType[maxQue]; } QueType::QueType() // Default class constructor { maxQue = 501; front = maxQue - 1; rear = maxQue - 1; items = new ItemType[maxQue]; } QueType::~QueType() // Class destructor { delete [] items; } void QueType::MakeEmpty() { front = maxQue - 1; rear = maxQue - 1; } bool QueType::IsEmpty() const { return (rear == front); } bool QueType::IsFull() const { return ((rear + 1) % maxQue == front); } void QueType::Enqueue(ItemType newItem) { if (IsFull()) throw FullQueue(); else { rear = (rear +1) % maxQue; items[rear] = newItem; } } void QueType::Dequeue(ItemType& item) { if (IsEmpty()) throw EmptyQueue(); else { front = (front + 1) % maxQue; item = items[front]; } }

The code gets the length but clearly the queue has been modified. If the object was passed by reference the queue would be empty but it's not, it just has garbage in each queue position. There is some concept that I am not understanding. Any help would be greatly appreciated!

You need to see what the copy constructor does. It may be just a shallow copy. — Raymond Chen
– Raymond Chen, Commented Jan 1, 2014 at 20:51
As Raymond implied, show the implementation of QueType to get a definitive answer. — Oswald
– Oswald, Commented Jan 1, 2014 at 21:09
ok, so I understand that the base class needs a copy constructor if it has a destructor. I removed the destructor and now it works. I'm not familiar with copy constructors, could you tell me the correct code for the copy constructor to make this work? — user3151905
– user3151905, Commented Jan 1, 2014 at 22:46
Well, isEmpty is defined as: return rear == tail;. If there's only 1 element in the queue, the rear == tail, but the queue is not empty? — Marckvdv
– Marckvdv, Commented Jan 2, 2014 at 18:52

Mark Setchell · Accepted Answer · 2014-01-01 21:13:09Z

1

How about overriding the Enqueue and Dequeue functions to increment and decrement a counter... then you'd know how many items were in the queue.

answered Jan 1, 2014 at 21:13

Mark Setchell

210k32 gold badges309 silver badges503 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Thomas Matthews Over a year ago

Try this: items_in_queue = ((rear + maxQueue) - front) % maxQueue;

Thomas Matthews · Accepted Answer · 2014-01-01 21:46:24Z

A better approach is to implement a length or size function in the QueType class that returns the number of items in the queue.

Otherwise, you'll need to give the queue iterator support or a foreach function. This are passive visiting functions. Your GetLength function removes items from the queue which may not be a good thing. In other words, to get the number of items in the queue, you need to remove the items in the queue.

I agree that this is a better approach but since this is a school assignment I can't change the base class, I have to implement a client side function and the only thing I could think to do with the base member functions is to remove the items and count. I just can't figure out why the queue ends up with garbage in it.

Ali Essam · Accepted Answer · 2014-01-01 23:07:21Z

Since you can't change the base class, and from other answers and comments it seems you can't actually have deep copy without implementing your own copy constructor, the only workaround i can think of now for your client function is that you make another temporary queue, and when you dequeue an item from the original queue, enqueue it in the tmp one, and after you finish move them back again to the original queue.

Some pseudo code:

while(!Q.empty()) tmp.enqueue(Q.dequeue()) counter++ while(!tmp.empty()) Q.enqueue(tmp.dequeue())

This solution would cost θ(2n*copy_cost), any solution implemented without using interior counter would cost O(n), and since you don't have any options to iterate on your queue without removing elements of your queue, the only option is to enqueue your elements and make changes to the original queue.

TWA · Accepted Answer · 2015-05-07 00:31:19Z

The problem here is that the QueType class destructor is being called when the queue argument goes out of scope in your GetLength() client function.

QueType::~QueType() // Class destructor { delete [] items; }

This is freeing the dynamically allocated array (items) containing the queue's internal data.

You are correct in that since the GetLength() function's queue argument is passed by value you don't need to copy the queue values since the internal state will not be modified in the original variable.

You will find that if you comment out the delete[] in the destructor your GetLength() function will work as expected.

Collectives™ on Stack Overflow

getting the length of a simple queue

4 Answers 4

1 Comment

1 Comment

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

1 Comment

Comments

Comments

Related