在数组C++中移位元素

Question

我已经为我的堆栈对象类开发了一个名为"rotate"的方法.我所做的是,如果堆栈包含元素:{0,2,3,4,5,6,7}我需要向前和向后旋转元素.

如果我需要向前旋转2个元素,那么我们将在数组中有{3,4,5,6,7,0,2}.如果我需要向后旋转,或者-3个元素,那么,查看原始数组,{5,6,7,0,2,3,4}

所以我开发的方法运行正常.它只是非常无效的IMO.我想知道我是否可以使用mod运算符包围数组？或者,如果它们是无用的代码,我还没有意识到,等等.

我想我的问题是,我该如何简化这种方法？例如使用较少的代码.:-)

void stack::rotate(int r)
{
    int i = 0;
    while ( r > 0 ) // rotate postively.
    {
        front.n = items[top+1].n;
        for ( int j = 0; j < bottom; j++ )
        {
            items[j] = items[j+1];                                  
        }
        items[count-1].n = front.n;
        r--;
    }

    while ( r < 0 )  // rotate negatively.
    {
        if ( i == top+1 )
        {
            front.n = items[top+1].n;  
            items[top+1].n = items[count-1].n; // switch last with first
        }

        back.n = items[++i].n; // second element is the new back
        items[i].n = front.n; 
        if ( i == bottom )
        {
            items[count-1].n = front.n; // last is first
            i = 0;  
            r++;   
            continue;
        }
        else
        {
            front.n = items[++i].n;
            items[i].n  = back.n;
            if ( i == bottom )
            {
                i = 0;
                r++; 
                continue;
            }
        }
    }
}

Answer 1

您可以更改"开始"的定义,而不是移动堆栈中的所有项目.有一个索引代表堆栈中的第一个项目,在开始时为0,您可以在需要旋转堆栈时添加和减去使用模运算.

请注意,如果你采用这种方法,你不应该让你的类的用户访问底层数组(不是你真的应该...).

Answer 2

好吧,因为这是一个数组的抽象,你可以将"零"索引存储为抽象的一个成员,并根据第一个元素的抽象概念索引到数组中.大致...

class WrappedArray
{
  int length;
  int first;
  T *array;

  T get(int index)
  {
    return array[(first + index) % length];
  }

  int rotateForwards()
  {
    first++;
    if (first == length)
      first = 0;
  }
}

Answer 3

你已经得到了几个合理的答案,但也许还有一个不会受到伤害.我的第一反应是让你的堆栈成为std :: deque的包装器,在这种情况下,将元素从一端移动到另一端是便宜的(O(1)).