Thread: Stack and Queue "quack" circular array

  1. #1
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221

    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

  2. #2
    Registered User
    Join Date
    Oct 2009
    Location
    While(1)
    Posts
    377
    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 >???

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> 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.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    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.
    Last edited by mrsirpoopsalot; 10-15-2009 at 08:57 AM.

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    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.
    Last edited by mrsirpoopsalot; 10-15-2009 at 05:32 PM.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    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;   
    	
    	
    }

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    (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.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    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! =(
    Last edited by mrsirpoopsalot; 10-15-2009 at 09:02 PM.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    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.

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by mrsirpoopsalot View Post
    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.

  13. #13
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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?

  14. #14
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    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.
    Last edited by mrsirpoopsalot; 10-19-2009 at 11:13 PM.

  15. #15
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. queue and stack implemented with linked list
    By popapez in forum C Programming
    Replies: 14
    Last Post: 09-22-2009, 10:56 PM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  3. Pushing a Queue onto a Stack?
    By MiroMage in forum C Programming
    Replies: 5
    Last Post: 10-14-2008, 09:23 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. queue / stack
    By smd in forum C++ Programming
    Replies: 2
    Last Post: 07-26-2002, 01:30 PM