10 Replies - 479 Views - Last Post: 04 October 2011 - 05:50 AM Rate Topic: -----

#1 skatingrocker17  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 117
  • Joined: 01-September 11

Question about popping and pushing

Posted 03 October 2011 - 08:53 AM

I've been assigned to write selected functions for some code that deals with a line at a sandwich shop. I'm only writing the push, pop and expand functions. The thing is we're not using vectors, that would be too easy. Instead, we're using a dynamic circular array. Anyway I was wondering if someone could look over my code, some of it seems right but I know for sure that the pop function is incorrect.
Here's the code, I won't include int main because that's only for testing.

#include <iostream>
#include <sstream>
using namespace std;
const int initialSize = 5;


struct Order {

	
	string sandwich;
	string customerName;
	int orderNbr;
	bool fries;
};


class SandwichQueue{

public:

	SandwichQueue();
	
	//Interface for queue
	Order pop();
	void push(const Order& sandwich);
	void expandQ();
	bool isEmpty();
	int size();	

private:

	//qSize is size of array, not amount stored in queue
	int qSize;
	Order* orderQ;
	int front;
	int back;
	
};

SandwichQueue::SandwichQueue()
{
	qSize = initialSize;
	orderQ = new Order[initialSize];
	back = qSize - 1;
	front = 0;
}

bool SandwichQueue::isEmpty()
{
	if (size() == 0)
		return true;
	else
		return false;
}


int SandwichQueue::size()
{

	return (back - front + 1 + qSize) % qSize;

}

//function to pop
Order SandwichQueue::pop()
{
	size();
	return Order(front);
}

//push an element, make sure it is not full, if it is call expand funciton
void SandwichQueue::push(const Order& sw)
{
	if (back == (qSize - 1))
		expandQ();
	 orderQ[++back] = sw;
	
}

//Double the queue size, copy the values, and reset back and front
void SandwichQueue::expandQ()
{
	qSize = initialSize * 2;
	orderQ = new Order[initialSize];
	back = qSize - 1;
	front = 0;


}




My functions are the last 3, pop, push and expandQ.
Thanks for any help.

Is This A Good Question/Topic? 0
  • +

Replies To: Question about popping and pushing

#2 WabiSabi  Icon User is offline

  • D.I.C Head

Reputation: 51
  • View blog
  • Posts: 202
  • Joined: 31-December 10

Re: Question about popping and pushing

Posted 03 October 2011 - 09:36 AM

What are you returning from size()? :blink: Seems to me like it would just be the index of the last element +1, wouldn't it?

And why do you call it without assigning its value to anything? What is the purpose of the call within pop?

As for your return value from pop, I'd just make it void... no return value. You want it to do something... remove an element from the array. Your push function doesn't return anything. Neither should your pop function.

I'm not sure a push function should increase the whole thing by 2... but idk, is that what the assignment calls for?
Was This Post Helpful? 1
  • +
  • -

#3 skatingrocker17  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 117
  • Joined: 01-September 11

Re: Question about popping and pushing

Posted 03 October 2011 - 11:03 AM

View PostWabiSabi, on 03 October 2011 - 09:36 AM, said:

What are you returning from size()? :blink: Seems to me like it would just be the index of the last element +1, wouldn't it? And why do you call it without assigning its value to anything? What is the purpose of the call within pop?


Since the pop function is supposed to remove the last element I thought I would decrement size. Yes, I know it's wrong. It was more of just a filler to remind myself to do it, if it even needs to be done.

View PostWabiSabi, on 03 October 2011 - 09:36 AM, said:

As for your return value from pop, I'd just make it void... no return value. You want it to do something... remove an element from the array. Your push function doesn't return anything. Neither should your pop function.


The function header was just written like that for me. I suppose it could just be void but I'd like to get it working first.

View PostWabiSabi, on 03 October 2011 - 09:36 AM, said:

I'm not sure a push function should increase the whole thing by 2... but idk, is that what the assignment calls for?


I should of added some comments to my code. The first thing push is doing is checking to see if the array is full, and if it is, the array size is then doubled.

If the array is not full, the new order is added to the back (or maybe it should be added to the front?).
Was This Post Helpful? 0
  • +
  • -

#4 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 656
  • View blog
  • Posts: 2,247
  • Joined: 31-December 10

Re: Question about popping and pushing

Posted 03 October 2011 - 11:35 AM

You should try to do it like the standard library does, and that is to return nothing from pop, just remove the last item in the queue. Then add a function back() that returns a reference to the last element. Functions should only do one thing, and they should do it well. That's why container classes have their pop functions return void. This way, if you need to access the last element before popping you just call back(), then pop() the element. You could also add an overloaded version of back() that returns a const reference.
Was This Post Helpful? 1
  • +
  • -

#5 skatingrocker17  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 117
  • Joined: 01-September 11

Re: Question about popping and pushing

Posted 03 October 2011 - 11:51 AM

View Postvividexstance, on 03 October 2011 - 11:35 AM, said:

You should try to do it like the standard library does, and that is to return nothing from pop, just remove the last item in the queue. Then add a function back() that returns a reference to the last element. Functions should only do one thing, and they should do it well. That's why container classes have their pop functions return void. This way, if you need to access the last element before popping you just call back(), then pop() the element. You could also add an overloaded version of back() that returns a const reference.


The way it's set up I don't need to add another function although I could. Do my push and expandQ functions work? I will probably make the pop function void though because I don't really know what it should be returning anyway.
Was This Post Helpful? 0
  • +
  • -

#6 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 656
  • View blog
  • Posts: 2,247
  • Joined: 31-December 10

Re: Question about popping and pushing

Posted 03 October 2011 - 12:08 PM

Not really, in your constructor and the expand function, you dynamically allocate memory, but you never deallocate that memory. You should add a destructor that deletes the storage. In the expand function, you only allow there to ever be 10 elements. You should double the size of the queue not just double the initialsize variable. When you allocate the memory, no where do you copy the old queue over to the new queue. And then you don't even deallocate the old storage. Lastly, you should think about making the expand function private, because only the member functions of the class should be able to call it, not the user.
Was This Post Helpful? 0
  • +
  • -

#7 WabiSabi  Icon User is offline

  • D.I.C Head

Reputation: 51
  • View blog
  • Posts: 202
  • Joined: 31-December 10

Re: Question about popping and pushing

Posted 03 October 2011 - 12:13 PM

View Postskatingrocker17, on 03 October 2011 - 12:03 PM, said:

Since the pop function is supposed to remove the last element I thought I would decrement size. Yes, I know it's wrong. It was more of just a filler to remind myself to do it, if it even needs to be done.



Ah... ok then. I think it definitely needs to be done.

I'd make a function to return the size (as it seems you have done) and a variable to hold the current size. And anytime you add or delete a value from your list, then increment or decrement size (size++ or size--)

something like this...
             int getSize() const{// return the size of the list (number of nodes in list)
                 return size;
             }  


But I guess a line is more like a queue, huh?

So, the new order, I would think, should go at the end. A line... first come, first served, right? New people/things end up at the back of the line.


             void queue(const elem_type& num){
                  myQueue.last();
                  myQueue.insertAfter(num);
             }
                 
             void dequeue(){
                  myQueue.first();
                  myQueue.remove();
             }
               

This post has been edited by WabiSabi: 03 October 2011 - 12:14 PM

Was This Post Helpful? 1
  • +
  • -

#8 skatingrocker17  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 117
  • Joined: 01-September 11

Re: Question about popping and pushing

Posted 03 October 2011 - 02:00 PM

View PostWabiSabi, on 03 October 2011 - 12:13 PM, said:

But I guess a line is more like a queue, huh?

So, the new order, I would think, should go at the end. A line... first come, first served, right? New people/things end up at the back of the line.


             void queue(const elem_type& num){
                  myQueue.last();
                  myQueue.insertAfter(num);
             }
                 
             void dequeue(){
                  myQueue.first();
                  myQueue.remove();
             }
               



Exactly. It is a queue. But I guess your queue and dequeue functions are my push and pop functions.
Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5801
  • View blog
  • Posts: 12,639
  • Joined: 16-October 07

Re: Question about popping and pushing

Posted 03 October 2011 - 04:55 PM

SandwichQueue::SandwichQueue() {
	qSize = initialSize; // ok
	orderQ = new Order[initialSize]; //ok
	front = 0; // sure
	back = qSize - 1; // questionable, it depends out how you're doing the rest
}

bool SandwichQueue::isEmpty() {
	/*
	this is just a pet peeve
	never return a bool if the test is a bool...
	if (size() == 0)
		return true;
	else
		return false;
	*/
	return size() == 0;
}


int SandwichQueue::size() {
	// I'm not sure of the logic of this
	// it hurts my head and depends quite a bit on the rest of it
	return (back - front + 1 + qSize) % qSize;
}

//function to pop
Order SandwichQueue::pop() {
	// right, this kind of does nothing,
	// why is it there?
	// size(); 
	// big problem time
	// don't you think you should change front?
	return Order(front);
	// you also don't check we're empty
	// maybe that's what you meant by some call to size()
	// as pointed out, you don't seem to have a plan
	// if the queue is empty
}

void SandwichQueue::push(const Order& sw) {
	// if this is a circular queue
	// then checking back is meaningless
	// perhaps you meant to check size?
	if (back == (qSize - 1))
		expandQ();
	// this makes sense
	// unless back == (qSize - 1) and you have room starting at 0
	// this is circular, yes?
	orderQ[++back] = sw;
	
}


void SandwichQueue::expandQ() {
	// big problems here
	// you just droped all your data, and made a nice memory leak
	qSize = initialSize * 2;
	orderQ = new Order[initialSize];
	back = qSize - 1;
	front = 0;
}




Honestly, front and size would probably be easier. Then you could do that modulus trick for the end?

Expand should be non destructive. It is your chance to restart at the front again, though.
Was This Post Helpful? 1
  • +
  • -

#10 skatingrocker17  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 117
  • Joined: 01-September 11

Re: Question about popping and pushing

Posted 03 October 2011 - 05:41 PM

View Postbaavgai, on 03 October 2011 - 04:55 PM, said:

Honestly, front and size would probably be easier. Then you could do that modulus trick for the end?

Expand should be non destructive. It is your chance to restart at the front again, though.


Thanks baavgai, do you think something like this would work better? I just realized that front is actually the end of the array, which makes sense because if you're at the front of the line obviously you're going to be the first to exit the queue.

My pop function still needs some work.
//function to pop
Order SandwichQueue::pop()
{
	if (isEmpty())
		return;
	return Order(front);
}

//push an element, make sure it is not full, if it is call expand funciton
void SandwichQueue::push(const Order& sw)
{
	if (size == (qSize - 1))
		expandQ();
	 orderQ[++front] = sw;
	
}

//Double the queue size, copy the values, and reset back and front
void SandwichQueue::expandQ()
{
	qSize = initialSize * 2;
	back = qSize - 1;
	front = 0;
}

Was This Post Helpful? 0
  • +
  • -

#11 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5801
  • View blog
  • Posts: 12,639
  • Joined: 16-October 07

Re: Question about popping and pushing

Posted 04 October 2011 - 05:50 AM

Your expand doesn't get any more memory...

I'm just going look at one, maybe that will give idea:
Order SandwichQueue::pop() {
	if (isEmpty()) { 
		// we need to return something
		// you told me we'd return something
		// return;
		// at the very least, return default
		return Order();
		// understand now why
		// bool SandwichQueue::pop(Order &item)
		// might be preferable?
	}
	// so many problems here
	// return Order(front);
	// you want to 
	// 1. get the current item from your list
	Order item = orderQ[front];
	// 2. move your position in that list forward
	front++;
	// 3. check to see if that puts you at the end of the list
	// if so, move back to the begining
	if (found==qSize) { front=0; }
	// 4. return the popped value
	return item;
}



Now, if it were me, I'd be using size. E.g.
bool SandwichQueue::isEmpty() const { return size==0; }

bool SandwichQueue::pop(Order &item) {
	if (!isEmpty()) { 
		item = orderQ[front++];
		size--;
		if (front==qSize) { front=0; }
		return true;
	}
	return false;
}


Was This Post Helpful? 1
  • +
  • -

Page 1 of 1