FIFO list (moving elements) [C++]

Good evening, people!

I'm trying to solve a rather simple problem, but.. well, it seems that I can't. :)

The idea is that I have a FIFO list (FIFO queue) with n elements and it's given a value, k (k < n). My little program has to move the elements to the left with k elements. (e.g. for n=4, k=3, a[]=(1, 2, 3, 4), the result is 4 1 2 3).

But well, I get nowhere near that.

This is what I've written so far:

#include <iostream>
using开发者_如何学JAVA namespace std;

void move (int a[100], unsigned n, unsigned k) {
        int t[100];
        unsigned i;
        for (i=0; i<=n-1; i++) t[i]=a[i];
        for (i=0; i<=k-1; i++) a[i]=a[i+k-1];
        for (i=k; i<=n-1; i++) a[i]=t[i+1];
}

int main () {
        int a[100];
        unsigned k, n, i;
        cout<<"n; k= "; cin>>n>>k;
        for (i=0; i<=n-1; i++) cin>>a[i];
        move (a, n, k);
        for (i=0; i<=n-1; i++) cout<<a[i]<<" ";
}

Any help would be greatly appreciated. Thank you in advance.

I'm not sure if I've understood your question completely. But looks like you effectively want to rotate the contents of the array.

To rotate the array contents to the left k times. You can do the following:

• Reverse the first K elements.
• Reverse the remaining N-K elements.
• Reverse the entire array.

Example:

N = 5, K = 3, and array = [1 2 3 4 5]

• step 1: reverse the first 3 elements: [3 2 1 4 5]
• step 2: reverse the remaining 2 elements: [3 2 1 5 4]
• step 3: reverse the entire array: [4 5 1 2 3]

C++ function to do the same:

void move (int a[100], int n, int k) {
        int t[100];
        int i,j;
        for (i=k-1,j=0; i>=0; i--,j++) t[j]=a[i];
        for (i=n-1; i>=k; i--,j++) t[j]=a[i];
        for (i=n-1,j=0; i>=0; i--,j++) a[j]=t[i];
}

A better way to do it in constant space is to do the reversal in-place:

void arr_rev(int a[100], int start, int end) {
        int temp;

        for(;start<end;start++,end--) {
                temp = a[start];
                a[start] = a[end];
                a[end] = temp;
        }
}

void move2 (int a[100], int n, int k) {
        arr_rev(a,0,k-1);
        arr_rev(a,k,n-1);
        arr_rev(a,0,n-1);
}

Since you've tagged this as C++, I'll assume that's what you're using. In that case, you should almost certainly be using an std::deque instead of an array for storing the data. In addition, a queue normally has a "front" and a "back", so "left" doesn't really mean much.

Assuming (just for the sake of argument) that what you want is to take k elements from the back of the queue and move them to the front, you could do something like:

typedef std::deque<your_type> data;

void push_to_front(data &d, int k) { 
    if (k > d.size())
        return;
    for (int i=0; i<k; i++) {
        data::value_type v = d.pop_back();
        d.erase(d.back());
        d.push_front(v);
    }
}      

If you want to rotate in the other direction, it's pretty much a matter of swapping the roles of the front and back.

It looks like you want a left-rotate? That shouldn't be very difficult. Just dequeue the first k elements, shift the remaining n-k elements to the left (possibly by putting them at the beginning of a temporary array), and then add in the first k at the end in order.

To modify your code in this manner might look like this:

void move (int a[100], unsigned n, unsigned k) {
        int t[100];
        unsigned i;
        for (i=k; i<=n-1; i++) t[i-k]=a[i];
        for (int x=0; x<=k-1; x++) t[i++-k]=a[x];
}

And since this is still ugly, you might rewrite it to make the logic more clear, but I will leave that as an exercise.

This also assumes you are not allowed to use STL data structures; if that is not the case, see Jerry Coffin's answer.

If you mean "move the kth element to the front of the queue", then this is one way to do it:

void move( int *a, unsigned n, unsigned k )
{ 
    int t; // To store the temporary for the k'th element 

    t = a[ k ];

    // Shift all the elements to the right by one.
    for( unsigned i = k; i > 0; --i )
        a[ i ] = a[ i - 1 ];

    // Put the k'th element at the left of the queue.
    a[ 0 ] = t;
}

#include <iostream>
#include <list>
template <typename T>
void Rotate(std::list<T>& list, int k){
    for(int i=0; i<k; ++i){
        T tmp(list.back());
        list.pop_back();
        list.push_front(tmp);
    }
}
int main(){
    std::list<int> ints;
    ints.push_back(1); ints.push_back(2);
    ints.push_back(3); ints.push_back(4);
    Rotate(ints,2);
    for(std::list<int>::const_iterator i = ints.begin(); i!=ints.end(); ++i)
        std::cout << *i << std::endl;
    return 0;
}

Will output:

3
4
1
2

The question is old, but nowadays it seems that the easiest solution is to rely on std::rotate. The complexity is linear but depends on the distance between first and last. So if you need to rotate 1 element complexity is O(1), for 3 it is O(3).