Двойные указатели в реализации стека связанного списка

Question

Недавно я читал книгу, и это объяснение для реализации стека в Связанном списке. Далее следует объяснение:

typedef struct Element { 
    struct Element *next; 
    void *data; 
} Element; 

Соответствующие прототипы нажимной и поп следуют:

void push(Element *stack, void *data); 
void *pop(Element *stack); 

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

void push(Element **stack, void *data); 
void *pop(Element **stack); 

Однако, что интересно, это то, что есть необходимость ставить двойные указатели на стек? Я понимаю понятие двойных указателей, но, однако, когда новый узел создается с использованием Element *node1 = (Element *) malloc (sizeof(Element));, у нас уже есть указатель на узел. Почему бы просто не отправить этот указатель сам, а не использовать двойной указатель?

Answer 1

Поскольку у вас нет автономного объекта Stack, каждый раз, когда вы меняете верхний узел в стеке, первичная ссылка на этот стек должна изменяться для всего, что с ним связано. Вот почему нужен двойной указатель, потому что старая вершина стека уже недействительна.

Если вы создали объект стека верхнего уровня, который имеет указатель на элемент и, возможно, некоторые другие данные, такие как число элементов, то вы сможете отправить это, чтобы нажать/поп как один указатель, потому что object/struct останется прежним, только данные внутри него будут меняться.

// pseudocode 
struct Stack { 
    Element * top = NULL; 
    int size = 0; 
} 

struct Element { 
    Element * next; 
    void * data; 
} 

function push(Stack * stack, void * data) { 
    Element * element = new Element(data); 
    element->next = stack->top; 
    stack->top = element; 
    size++; 
} 

// pop left as an exercise to the reader.. :) 

int main(void*) { 
    Stack * stack = new Stack; 
    push(stack, "foo"); <== no need for double pointer 
    pop(stack); 
    printf("%d\n", stack->size); 
} 

Answer 2

Это немного сбивает с толку из-за общей путаницы понятий pointers и passing by reference.

Давайте рассмотрим оригинальную функцию push. Параметр stack представляет собой указатель на начало стека. Этот указатель предоставляется вызывающим абонентом. Если нужно изменить начало стека, функция push не сможет это сделать, потому что было передано значением, т. Е. Внутри тела функции это копия оригинала. То же самое касается pop.

Это проще всего понять на примере. Предположим, что начало стека находится по адресу 0x1234. Когда push вызывается, значение 0x1234 передается ему вызывающим абонентом. push может делать все, что захочет, с этим значением, но не изменяет данные исходного указателя, и изменения не будут отражаться в контексте вызывающего абонента.

Почему бы не написать node1 указатель, который вы создали внутри? push: Element *node1 = (Element *) malloc (sizeof(Element));?Это именно то, что вы должны сделать, но вам все еще нужно двойной указатель:

void push(Element **stack, void *data) 
{ 
    Element *node1 = (Element *) malloc (sizeof(Element)); 
    node1->data = data; 
    node1->next = *stack; 
    *stack = node1; 
} 

Если вы пытаетесь достичь этой цели без двойного указателя, вызывающий абонент не будет видеть изменения и останется со старым указателем стека:

void push(Element *stack, void *data) 
{ 
    Element *node1 = (Element *) malloc (sizeof(Element)); 
    node1->data = data; 
    node1->next = stack; 
    stack = node1;   //The data structure was updated but caller won't see it! 
}