Rotating or shifting a circular que

This is a discussion on Rotating or shifting a circular que within the C++ Programming forums, part of the General Programming Boards category; I had a previous thread about pushing data in a circular queue. I didnt see a need to keep that ...

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

    Rotating or shifting a circular que

    I had a previous thread about pushing data in a circular queue.
    I didnt see a need to keep that thread going.

    After all the items are pushed into the circular queue
    i need to rotate them forward and reverse.
    Problem is i cant use a temporary array to do it.
    I need to do it inside the circular que.
    could i use a bitwise to do it?

    This is some of my code.

    Code:
    nt 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;
    	pop(q, true);
    	cout << q;
    	pop(q, true);
    	cout << q;
    	push(q, false, 7);
    	cout << q;
    	push(q, false, 8);
    	cout << q;
    	cout << ">>> rotate(2)\n";
    	q.rotate(2);
    	cout << q;
    	cout << ">>> rotate(-3)\n";
    	q.rotate(-3);
    	cout << q;
    	cout << ">>> reverse\n";
    	q.reverse();

    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
    Code:
    bool quack::pushFront(const int n)
    {
    
    
    	if ( count == maxsize )
    	{   
    
    		return false;
    	}
    	front = (front - 1 ) % maxsize;
    	items[front].n = n;
    	count++;
    
    	return true;    
    
    
    }
    
    
    bool quack::pushBack(const int n)
    {
    
    
    	back = (back = front + count ) % maxsize;
    	items[back].n = n;
    	count++;
    	return true;   
    
    
    
    }
    
    bool quack::popFront(int& n)
    {
    
    	front = (front + 1 ) % maxsize;
    	--count;
    
    
    	return true;
    }
    
    
    bool quack::popBack(int& n)
    {
    
    	back = (back -1) % maxsize;
    	--count;
    
    	return true;
    
    
    
    }
    And i need to rotate them by the number being passed in.
    Code:
    void quack::rotate(int r)
    {
    
    
    
    
    }
    
    void quack::reverse(void)
    {
    }
    Right now the circular array looks like:
    3,2,1,0,7,8 before the rotate.
    Rotate(2)

    1,0,7,8,3,2

    Any hints on how to accomplish this?
    Last edited by mrsirpoopsalot; 10-21-2009 at 09:07 PM.

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,325
    Are you allowed to make your storage array one size bigger than the max size of the circular array?

  3. #3
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    Im not sure what you mean by storage array?

    I am suppose to Implement quack::rotate and quack::reverse to rotate or reverse the items in place in the array pointed to by the items data member (that is, without using a temporary array). The only array variable you can use is the items data member itself. In other words, you are not allowed to use a temporary array for this version.
    Last edited by mrsirpoopsalot; 10-21-2009 at 10:48 PM.

  4. #4
    Registered User
    Join Date
    Oct 2009
    Location
    While(1)
    Posts
    377
    Code:
    #include <stdio.h>
    
    
    
    void rotate_left(int* queue, const int count) {
    	const int first_element = *(queue + 0);
    	for (int index = 0; index < count; ++index) {
    		*(queue + index) = *(queue + index + 1);
    	}
    	*(queue + count - 1) = first_element;
    }
    
    void rotate_right(int* queue, const int count) {
    	const int last_element = *(queue + count - 1);
    	for (int index = count - 1; index >= 0; --index) {
    		*(queue + index) = *(queue + index - 1);
    	}
    	*(queue + 0) = last_element;
    }
    
    void reverse(int* queue, const int count) {
    	int end_index  = 0;
    	for (int start_index  = 0, end_index = count - 1; 
    		 start_index < count / 2; ++start_index, --end_index) {
    		const int temp         = *(queue + start_index);
    		*(queue + start_index) = *(queue + end_index);
    		*(queue + end_index)   = temp;
    	}
    };
    
    void display(int* queue, const int count) {
    	for (int index = 0; index < count; ++index)
    		printf("%d  ", *(queue + index));
    	printf("\n"); 
    }
    
    int main() {
    	int queue[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    	display(queue, 10);
    	rotate_left(queue, 10);
    	display(queue, 10);
    	rotate_right(queue, 10);
    	display(queue, 10);
    	reverse(queue, 10);
    	display(queue, 10);
    	return 0;
    }

    May be this code can help you dude

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,325
    Actually, rotate is really easy because your front (and back) indexes don't have to be at the start of your items array. They can be anywhere, and they determine the order. If you move them, you can move the starting point of the circular array.

    Implementing reverse might be a little harder, but I'd try to get rotate first.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Circular Positioning in C# form application?
    By arcaine01 in forum C# Programming
    Replies: 4
    Last Post: 05-08-2008, 02:31 PM
  2. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  3. Circular include issue
    By einarp in forum C++ Programming
    Replies: 10
    Last Post: 07-10-2006, 08:43 PM
  4. circular shift
    By n00bcodezor in forum C Programming
    Replies: 2
    Last Post: 11-20-2001, 02:51 AM
  5. Circular Logic
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 10-15-2001, 08:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21