Deque push_front()和push_back()，不包括<deque>

Question

我需要自己创建一个deque来理解它是如何与实践一起工作的，而且我不需要使用这个库，我想编写我自己的函数

我创建了一个类Deque，它有方法push_back()、push_front()、pop_back()、pop_front()；

首先，我为push_front()编写了这样的代码：

void Deque :: push_front( int data, int number ) {

 deque[head - 1] = data;
 head++;
}

下面是构造函数：

  Deque :: Deque( int number ) : head (1), tail (1), 
                                 go_straight (0), go_back (1), 
                                 deque (new int [number]) {
                                    for( int i = 0; i < number; ++i) {
                                       deque[i] = 0;
                                    }
                                 };

但是这个push_front的工作方式是这样的:如果我输入4(元素数)，然后输入40(值)

   40 0 0 0

如果我输入50(值)，它将变成：

  40 50 0 0

但我需要这样做

  50 40 0 0

换句话说，我需要在+1上移动元素，我如何做到这一点？

提前谢谢！

Answer 1

假设您的序列存储在某个数组ar[N]中，以及一些ar[len]中，其中len < N是队列的当前“回退”，那么只需“移动”元素：

#include <iostream>

template<typename T, size_t N>
bool push_front(const T& val, T(&ar)[N], size_t& len)
{
    if (len >= N)
        return false;

    size_t i = len;
    while (i--)
        ar[i+1] = ar[i];
    ar[0] = val;
    ++len;
    return true;
}

template<typename T, size_t N>
void print_array(const T(&ar)[N])
{
    for (auto& x : ar)
        std::cout << x << ' ';
    std::cout << '\n';
}

int main()
{
    int ar[10] = {0};
    size_t len = 0;
    print_array(ar);

    for (int i=10; push_front(i, ar, len); i+=10);
    print_array(ar);

    return 0;
}

输出

0 0 0 0 0 0 0 0 0 0 
100 90 80 70 60 50 40 30 20 10 

注意:对于每次插入(这意味着插入N项的O(N^2) )，这具有O(N)复杂性。使用循环缓冲区和非常小心的模块化算法，您可以将其变为O(1)，但这并不简单，因此我提前警告您。

关于如何在您的代码中工作，包括充实一个副本/交换成语，以符合三条规则。这两项推动措施已经实施。我将这两个pops、top()和back()实现留给您。

#include <algorithm>

class Deque
{

private:
    unsigned int size;
    unsigned int length;
    int *elems;

    void swap(Deque& other)
    {
        std::swap(size, other.size);
        std::swap(length, other.length);
        std::swap(elems, other.elems);
    }

public:
    Deque(unsigned int size)
        : size(size)
        , length(0)
        , elems(new int[size]())
    {
    }

    Deque(const Deque& arg)
        : size(arg.size)
        , length(arg.length)
        , elems(new int[arg.size])
    {
        std::copy(arg.elems, arg.elems + arg.length, elems);
    }

    ~Deque()
    {
        delete [] elems;
    }

    Deque& operator =(Deque obj)
    {
        swap(obj);
        return *this;
    }

    // push to the front of the deque
    bool push_front(int value)
    {
        if (length == size)
            return false;

        unsigned int i=length;
        while (i--)
            elems[i+1] = elems[i];
        elems[0] = value;
        ++length;
        return true;
    }

    // push to the back of the deque
    bool push_back(int value)
    {
        if (length == size)
            return false;

        elems[length++] = value;
        return true;
    }
};