Блог

Я написал следующий код стека:

 #include <iostream>
using namespace std;

template <typename T>
class Stack 
{
    T *sptr;
    int cap;
    int top;
    
public:
    Stack ()
    {
        sptr = nullptr;
        top = -1;
        cap = 0;
    }
    
    void push (const Tamp; obj)
    {
        if (top == -1)
        {
            sptr = new T[1];
            cap = 1;
            sptr[  top] = obj;
        }
        else if (cap == (top   1))
        {
            cap *= 2;
            T *temp = new T[cap];
            for (int i = 0; i <= top; i  )
                temp[i] = sptr[i];
            temp[  top] = obj;
            delete [] sptr;
            sptr = temp;
            temp = nullptr;
        }
        else
        {
            sptr[  top] = obj;
        }
    }
    
    inline bool empty () const
    {
        return (top == -1);
    }
    
    inline int size () const
    {
        return (top   1);
    }
    
    const Tamp; peek () 
    {
        return sptr[top];
    }
    
    void pop ()
    {
        if (top >= 0)
        {
            if (top == 0)
            {
                top = -1;
                cap = 0;
                delete [] sptr;
            }
            else if (top >= (cap/2 -1))
            {
                top--;
            }
            else
            {
                cap /= 2;
                T *temp = new T [cap];
                for (int i = 0; i < top; i  )
                {
                    temp[i] = sptr[i];
                }
                delete [] sptr;
                sptr = temp;
                temp = nullptr;
                top--;
            }
        }
    }
    
    /*void flip() // flip method
    {
        
    }*/
};
  

Теперь я хочу реализовать метод flip, который логически инвертирует стек таким образом, что самый старый элемент становится самым новым элементом, поэтому следующий pop удалит элемент, который был в нижней части стека до того, как он был перевернут. И я должен иметь возможность снова и снова переворачивать в O (1).

Невозможно перевернуть реальный стек в O (1).

Лучшее, что вы можете сделать, это O (n) . Чтобы увидеть это, вам нужно только заметить, что для получения нижнего элемента стека вам нужно вставить его n раз.

Тем не менее, вы можете сделать это в O (n):

Что вы можете сделать, чтобы создать еще один стек, вытащить содержимое, нажав на другой. Когда оригинал пуст, отбросьте его и верните новый стек.

ОБНОВЛЕНИЕ: однако ваша реализация поддерживается массивом, который строго более мощный, чем стек.

Вы можете изменить его, сохранив флаг направления, и когда запрашивается revese для переключения головы в хвост, изменения флага, а также направления обхода. Также будет некоторая дополнительная бухгалтерия для управления памятью, поскольку вам, возможно, придется расширять как high, так и low.

Я предлагаю создать чертеж структуры данных, чтобы вы могли отслеживать, что происходит со смещениями.

Для аналогичной, но фиксированной структуры размера вы можете взглянуть на это: https://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-Circular-Buffer-with-a-Twist

Что вам нужно, так это Deque, который позволяет добавлять и удалять элементы с обоих концов:

https://en.wikipedia.org/wiki/Double-ended_queue

Чтобы использовать его как обратимый стек, вы просто сохраняете логическую переменную, чтобы определить, с каким концом будут работать операции стека.