Stack and Queue "quack" circular array

I am trying to push items into a circular array by push front and then pushback.

it pushes 1 -4 in front then suppose to push 0 in back then push 9 in front.
What i get is 0 in front. The book i have only shows how to push in back.
Any help is very appreciative since i have worked on this for hours.
Sorry about the format of my code. I didnt notice it was really bad until i hit preview and im too lazy to start this post over.

Code:

const static int QUACK_SIZE = 7;

static void push(quack& q, bool front, int n)
{
	bool	ok;

	if (front)
		ok = q.pushFront(n);
	else
		ok = q.pushBack(n);
	cout << ">>> push" << (front ? "Front " : "Back ") << n << (ok ? " succeeded\n" : " failed\n");
}

static void pop(quack& q, bool front)
{
	bool	ok;
	int		n;

	if (front)
		ok = q.popFront(n);
	else
		ok = q.popBack(n);
	cout << ">>> pop" << (front ? "Front " : "Back ");
	if (ok)
		cout << "succeeded: " << n << endl;
	else
		cout << "failed\n";
}

int main (void)
{
	quack	q(QUACK_SIZE);

#ifdef _WIN32
	// request memory leak report in Output Window after main returns
	_CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF );
#endif

	
	cout << q;
	push(q, true, 1);
	push(q, true, 2);
	push(q, true, 3);
	push(q, true, 4);
	push(q, false, 0);
	push(q, true, 9);
	cout << q;
	cout << "--- # of items: " << q.itemCount() << endl << endl;

Code:

#pragma once

#include <ostream>

using namespace std;

class quack
{
public:
	quack(int capacity);
	~quack(void);
	bool pushFront(const int n);	// push an item onto the front
	bool pushBack(const int n);		// push an item onto the back
	bool popFront(int& n);			// pop an item off the front
	bool popBack(int& n);			// pop an item off the back
	void rotate(int r);				// "rotate" the stored items (see note below)
	void reverse(void);				// reverse the order of the stored items
	int	itemCount(void);			// return the current number of stored items

private:
	struct item						// definition of each item stored by the quack
	{
		int		n;
		int     top;
		int     count;
		int     maxsize;
		int     front;
		int     back;
		
	};
	item		*items;				// pointer to storage for the circular array

public:
	friend ostream& operator<<(ostream& out, quack& q);
	friend ostream& operator<<(ostream& out, quack::item& i);
};

Code:

quack::quack(int capacity)
{

	items = new item[capacity];
	items->n = 0;
	items->top = 0;
	items->count = 0;
	items->maxsize = capacity;
	
    items->back = capacity;
    items->front = capacity -1;
	

}

Code:

bool quack::pushFront(const int n)
{

if ( items->count == items->maxsize )
    {   
      
        return false;
    }
    
    items->front = (items->front - 1) % items->maxsize;
    items[items->front].n = n;
    items->count++;
    
        return true;    
   

}

bool quack::pushBack(const int n)
{


    items->back = (items->back + 1) % items->maxsize;
   items[items->back].n = n;
    items->count++;
    
        return true;    


//items[items->count].n = n;
  //items->count++;


	
}

my output:

Code:

quack: empty
>>> pushFront 1 succeeded
>>> pushFront 2 succeeded
>>> pushFront 3 succeeded
>>> pushFront 4 succeeded
>>> pushBack 0 succeeded
>>> pushFront 9 succeeded

quack: 0, 9, 4, 3, 2, 1

--- # of items: 6

>>> popFront failed

quack: 0, 9, 4, 3, 2, 1

Dude where is the defination of

Code:

ok = q.popFront(n);
ok = q.popBack(n);

how will we know that what is written inside those functions >???

>> how will we know that what is written inside those functions >???
You don't really need the definitions of the pop functions to see the problem.

Just go through the code one line at a time and watch what the values are for items->back and items->front.

I'll start you off:

When you first create the quack q, you specify a capacity of 7. In the constructor, items->back is set to 7 and items->front is set to 6.

Next you push the value 1. Inside the pushFront function you call:

Code:

items->front = (items->front - 1) % items->maxsize;

That changes items->front from 6 to = (6-1)%7 which of course is 5. So iterms->front is 5 and that is the position you add the value 1 to. Your array looks like this:

Code:

 ___ ___ ___ ___ ___ ___ ___
| . | . | . | . | . | 1 | . |
  0   1   2   3   4   5   6

Now you continue this process and try to figure out where the rest of the values go and why it doesn't do what you expected.

I guess i dont understand how the circular array work. Where ever i put my numbers at in the array they stay there? For some reason im thinking since the array wraps around the numbers shift in the array..
capacity =7

So, if front =0; back =6 ...and i want to pushfront items do i have start at zero?
same for back. i have to start at 6?

because i am pushing 1234 in that order in front

but the order i want is 943210

so, basically when i first push that 1, i want it to be in the right spot that i want?
if so then im actually in the back!

I cant find any good tutorials on this subject.

Your understanding was fine with the original code, but if you follow through with where the code puts the items, what does the final array look like? What value is items->front?

I think your issue is more of an off-by-one issue. That's why I think you can fix it by following the code through each operation. You can probably skip the pushing of 3 and 4 if you want. The problem appears to be that your idea of what is the "front" and what is the "back" is just off by a little.

What happens if you do pushFront(1), pushFront(2), pushFront(3), pushBack(4), pushBack(5), pushFront(6)? I'd expect you might get 561234.

So, basically i want to push 1 in 4th slot?
Grrr, none of this is making sense to me..
No matter what i try it comes out wrong..


To push in the back i set front to zero and back to size - 1
so, do i do the reverse for front?
The circular array goes in a clockward direction.

Im confused because if my order is
12345 and im pushing in the front does front have to be zero?
becuase 0 =1 , 1 =2, 2=3 however, i want the reverse order.

the order it pushes is 1,2,3,4,0,9
my output needs to be 9,4,3,2,1,0

ok, i stepped through the code..


I can get it to put them in the right order starting with 1234

Code:

|__| |__| |_4_| |_3_| |_2_| |_1_|
 0    1      2     3     4     5

However, to get it to 6th slot to put my zero in
i have to do this below. Which is fine it puts in the 6th slot after 1

Code:

bool quack::pushBack(const int n)
{

   items->front = (items->front + items->count) % items->maxsize;
   items[items->front].n = n;
    items->count++;
    
        return true;

However,
When it calls pushfront to push the last item 9

front is now pointing to 5
thats where my 1 is stored.

how can i get it back to its original position before i pushed the zero in back?
or is this way totally off base?

Code:

bool quack::pushFront(const int n)
{

if ( items->count == items->maxsize )
    {   
      
        return false;
    }
    
    items->front = (items->front - 1) % items->maxsize;
    items[items->front].n = n;
    items->count++;
    
        return true;    
   }
   
   
bool quack::pushBack(const int n)
{

   items->front = (items->front + items->count) % items->maxsize;
   items[items->front].n = n;
    items->count++;
    
        return true;   
	
	
}

(Note: I didn't see that last post before I wrote this one, so this applies to the post before your last one.)

It doesn't matter where you start front or back. It's a circular array. Just pick an index and start there.

Your push functions change the index and then assign the value. I think that's your problem.

For example. To start, you set back to 7 and front to 6. Then, the first value you put in the front gets put in 5 (because you decrement front before using it). The first item you add to the back gets put into 0 because you increment back before using it. Do you see why that's a problem in the beginning? The first item pushed in the front and the first item pushed in the back should be side by side in the circular array.

A simple solution might be to take the code you had above, and then change your starting values in the constructor. Make it so back is 6 and front is 7. Then your first item pushed to the front will be placed in 6 and the first item pushed on the back will be placed in 7 and they will be side-by-side.

I hope that makes sense. It might be a simple change to make the whole thing work.

Daved, thanks for all your help..

Ok, since i have the capacity of the array is 7..
However, we are only pushing on 6 items. I cannot change the capacity
since down the road it will contain all the items.

I think when its all filled with my items. index 0 is empty
only 1- 6 array indexes are occupied..

I walked through the code, and every item is going into its place that i want. However, the output is wrong..

This is what i have.

Code:

quack::quack(int capacity)
{

	items = new item[capacity];
	items->n = 0;
	items->top = -1;
	items->count = 0;
	items->maxsize = capacity;
	
	 items->back = capacity;           // 7 
             items->front = capacity-1;      // 6

Code:

bool quack::pushFront(const int n)
{



if ( items->count == items->maxsize )
    {   
      
        return false;
    }
    
    items->front = (items->front - 1) % items->maxsize;
    items[items->front].n = n;
    items->count++;
    
        return true;    
           
   }
   
   
bool quack::pushBack(const int n)
{
   items->back = (items->back - 1) % items->maxsize;  // items->back points to 6
   items[items->back].n = n;
    items->count++;
    
        return true;   

	
}

Code:

CS260 - Lab2 - Your Name

quack: empty
>>> pushFront 1 succeeded
>>> pushFront 2 succeeded
>>> pushFront 3 succeeded
>>> pushFront 4 succeeded
>>> pushBack 0 succeeded
>>> pushFront 9 succeeded

quack: 0, 9, 4, 3, 2, 1

--- # of items: 6

>>> popFront failed

quack: 0, 9, 4, 3, 2, 1

i am pushing 0 in array index6. I dont see why its sitting infront! =(

Array indexes have exactly zero to do with being in front or in back, since it's a circle. Where your front pointer is pointing, that's your front. Look at your array indexing again. There are two choices: one, you store the array index that was just recently written to, which means you modify before you write and you leave it alone before you pop; two, you store the next index to go, which means you leave it alone before you write and modify before you pop. If you modify before you write and modify before you pop, then That's Just Wrong.

Tabstop, not sure if im doing what you say. I looked and front points to 1
and back points to 6
So, i am not sure what going on.

Originally Posted by mrsirpoopsalot

Tabstop, not sure if im doing what you say. I looked and front points to 1
and back points to 6
So, i am not sure what going on.

That seems completely reasonable, since that's where the front and back of the line are. (That is to say, the front is at element 1, which is the 9, which was most recently added to the front of the line; the back is at element 6 (apparently unused), which is "behind" the 0.) So as long as your popFront function doesn't touch that index before trying to get the front element, then you're fine.

Code:

	 items->back = capacity;           // 7 
             items->front = capacity-1;      // 6

My suggestion was to make it so back started at 6 and front started at 7. Did you try that simple change?

I was told that in order to implement a circular array, you need either pointers or indexes into that array, and those need to be data members of quack, not of item.
I am not sure how to do use pointers, since the circular array is ints.

Code:

#include <ostream>

using namespace std;

class quack
{
public:
	quack(int capacity);
	~quack(void);
	bool pushFront(const int n);	// push an item onto the front
	bool pushBack(const int n);		// push an item onto the back
	bool popFront(int& n);			// pop an item off the front
	bool popBack(int& n);			// pop an item off the back
	void rotate(int r);				
	void reverse(void);				// reverse the order of the stored items
	int	itemCount(void);			// return the current number of stored items

private:
	
	
	struct item						// definition of each item stored by the quack
	{
		int		n;
                        int    front;
                        int    back;
	
		
	};
	item		*items;	          // pointer to storage for the circular array

I was told i shouldnt use any more data members in the struct other than n
Isnt putting the data members in the private section acceptable?

Code:

bool quack::pushBack(const int n)
{
   items->back = (items->back - 1) % items->maxsize;
   items[items->back].n = n;
    items->count++;

Isnt this acceptable? I am getting the required output.

Code:

class quack
{
public:
	quack(int capacity);
	~quack(void);
	bool pushFront(const int n);	// push an item onto the front
	bool pushBack(const int n);		// push an item onto the back
	bool popFront(int& n);			// pop an item off the front
	bool popBack(int& n);			// pop an item off the back
	void rotate(int r);				// "rotate" the stored items (see note below)
	void reverse(void);				// reverse the order of the stored items
	int	itemCount(void);			// return the current number of stored items

private:
	
	 int front;
	 int back;
	 int maxsize;
	 int count;
	 
	struct item						// definition of each item stored by the quack
	{
		int		n;
	
		
	};
	item		*items;	// pointer to storage for the circular array
	

public:
	friend ostream& operator<<(ostream& out, quack& q);
	friend ostream& operator<<(ostream& out, quack::item& i);
};

Any help is much appreciated since i have lost a week on this project.

Yup, looks fine to me (that last piece of code). It is definitely more correct to have all those values outside of the item struct and as private members of quack, although that wasn't what was causing your earlier problem.

The push_back function you posted looks like it still uses the old way (with back, count and maxsize all as part of an item instead of members of quack. Do you have updated code for the constructor and push functions with those members moved?