FIFO list (moving elements) [C++]

Question

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 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.

Answer 1

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.

Answer 2

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.

Answer 3

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;
}

Answer 4

#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

Answer 5

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);
}