FIFO List (Moving Elements) [C ++]

Question

Good evening people!

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

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

But I don’t understand anything.

This is what I wrote 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

I am not sure if I fully understood your question. But it looks like you really want to rotate the contents of the array.

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

• Flip the first elements of K.
• Flip the rest of the NK items.
• Flip the entire array.

Example:

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

• step 1: undo the first 3 elements: [3 2 1 4 5]
• Step 2: undo the remaining 2 items: [3 2 1 5 4]
• Step 3: discard the entire array: [4 5 1 2 3]

The C ++ function does 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]; } 

The best way to do this in a constant space is to make a U-turn 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); } 

Answer 2

Looks like you want to turn left? It does not have to be very difficult. Just remove the first elements of k , move the remaining elements of nk left (perhaps by placing them at the beginning of the temporary array), and then first add k at the end in order.

To change your code this way 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[ik]=a[i]; for (int x=0; x<=k-1; x++) t[i++-k]=a[x]; } 

And since it's still ugly, you can rewrite it to make the logic clearer, but I will leave it as an exercise.

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

Answer 3

Since you marked this as C ++, I will assume that you are using. In this case, you almost certainly use std::deque instead of an array to store data. In addition, there is usually a “front” and a “back” in the queue, so “left” does not really mean much.

Assuming (just for the sake of argument) that you want to take k elements from the back of the queue and bring them to the front, you can 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 turn in the other direction, this is largely due to replacing the roles in the front and back.

Answer 4

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

 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 5

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

It will display:

 3 4 1 2