Можете ли вы перевернуть стек со временем выполнения O (1)? - PullRequest
Новая
       16

Можете ли вы перевернуть стек со временем выполнения O (1)?

3 голосов
/ 24 марта 2020

Я строю программу, которая использует двусвязный список для построения стека. Мне необходимо перевернуть стек или изменить его порядок со временем выполнения O (1). Например:

1 -> 2 -> 3 -> 4

становится

4 -> 3 -> 2 -> 1

Самый быстрый способ, которым я могу думать, использует O (N) как время выполнения. Необходимость использования времени выполнения O (1) не означает, что все циклы исключены, поскольку все они неизбежно будут зависеть от количества узлов в стеке.

Кто-нибудь может порекомендовать разумный способ * 1012? * об этой проблеме?

Ответы [ 3 ]

5 голосов
/ 24 марта 2020

Просто сохраните флаг направления, глобальный для списка, и переверните его, чтобы изменить направление списка. Определите ваш узел списка следующим образом: 

struct node {
    struct node *link[2];
    bool *dir;
};

Указатель dir каждого узла должен указывать на один объект bool, общий для всего списка (например, в отдельной выделенной памяти). Тогда везде, где вы обычно обращаетесь к p->next или p->prev, вместо этого обращайтесь к p->link[*p->dir] или p->link[!*p->dir] соответственно. Теперь вы можете перевернуть смысл prev и next для всего списка, просто инвертировав флаг направления: *p->dir = !*p->dir;.

Обратите внимание, что хранение указателя в каждом узле обходится дорого, и вы можете избежать этого просто сохраняя флаг отдельно «вне диапазона», но это ограничивает доступ к списку (по крайней мере, со знанием текущего направления) только там, где у вас есть эта информация вне диапазона; тогда вы не можете сделать это, начиная только с члена списка.

1 голос
/ 24 марта 2020

Определение новой структуры, указывающей на хвост связанного списка, с помощью prev & next указателей, которые переключаются (меняются местами), могут помочь. Таким образом, фактически вы даже не меняете и не перемещаете какое-либо значение данных, а просто смотрите на поток данных с другим набором очков.

edit: И да, как заметил @Marceeaax, вы должны были отслеживание указателей head & tail. 

typedef struct OriginalStruct {
    SomeType value;
    ...
    OriginalStruct *prev;
    OriginalStruct *next;
} OriginalStruct;

typedef struct ReversedStruct {
    SomeType value;
    // all same but the last two switched / swapped
    ReversedStruct *next;
    ReversedStruct *prev;
} ReversedStruct;

...
int main() {
    OriginalStruct *orgnHead = NULL;
    OriginalStruct *orgnTail = NULL;
    OriginalStruct *orgnList = createList(&orgnHead, &orgnTail);

    ...
    ReversedStruct *rvsdList = orgnTail;

    ...
    return 0;
}
0 голосов
/ 24 марта 2020

Если вы используете указатели головы и хвоста, этого должно быть достаточно, если поменять местами эти указатели. Это будет сделано в O (1).

...