卡片游戏

tips：这个题还要参考，同学要加油啦~~

要求

1. 创建队列类，使用数组描述的循环队列
2. 实现卡片游戏

描述

假设桌上有一叠扑克牌，依次编号为1-n（从上至下）。当至少还有两张的时候，可以进行操作：把第一张牌扔掉，然后把新的第一张（原先扔掉的牌下方的那张牌,即第二张牌）放到整叠牌的最后。输入n，输出最后剩下的牌。

格式

输入

一个整数n，代表一开始卡片的总数。

输出

最后一张卡片的值。

样例

输入

100

输出

72

限制

1s, 64MB for each test case.

#include <iostream>

#include <algorithm>
using namespace std;

template<class T>
void changeLength1D(T *&a, int oldLength, int newLength) {
    T *temp = new T[newLength]; //新数组
    int number = min(oldLength, newLength); //需要复制的元素个数
    copy(a, a + number, temp);
    delete[] a; //释放老数组的内存空间
    a = temp;
}

template<class T>
class arrayQueue {
public:
    arrayQueue(int initialCapacity = 10);

    ~ arrayQueue() { delete[] queue; }

    bool empty() const { return queueFront == queueBack; }

    int size() const {
        return (arrayLength + queueBack
                - queueFront) % arrayLength;
    }
    /* LYZ */
    T &front() const; //返回队首元素
    T &back() const; // 返回队尾元素
    void pop(); //删除队首元素
    void push(const T &theElement); //元素插入到队尾
private:
    int queueFront; //与第一个元素在反时针方向上相差一个位置
    int queueBack; // 指向最后一个元素
    int arrayLength; // 队列数组容量
    T *queue; // 元素数组
};

template<class T>

arrayQueue<T>::arrayQueue(int initialCapacity) { // 构造函数
    arrayLength = initialCapacity;
    queue = new T[arrayLength];
    queueFront = 0,queueBack = 0;
}

template<class T>
T &arrayQueue<T>::front() const {//返回队首元素

    return queue[(queueFront + 1) % arrayLength];
}

template<class T>
T &arrayQueue<T>::back() const {// 返回队尾元素
    return queue[queueBack];
}

template<class T>
void arrayQueue<T>::pop() {// 删除队首元素
    queueFront = (queueFront + 1) % arrayLength;
    queue[queueFront].~T();
}

template<class T>
void arrayQueue<T>::push(const T &theElement) {// 把元素theElement添加到队列的尾部
//如果队列空间满，则加倍数组长度
    if ((queueBack + 1) % arrayLength == queueFront) {

        changeLength1D(queue, arrayLength, 2 * arrayLength);
        arrayLength *= 2;
    }
    queueBack = (queueBack + 1) % arrayLength;
    queue[queueBack] = theElement;
}


int main() {
   arrayQueue<int> Queue;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        Queue.push(i);
    }
    while(Queue.size()>=2){
        Queue.pop();
        int flag=Queue.front();
        Queue.push(flag);
        Queue.pop();
    }
    int res=Queue.back();
    cout<<res<<endl;


    return 0;
}