C++ - Stack Pop() Функция с единственно Связанный список

Question

Для начала это не относится к моему текущему заданию домашней работы для моего класса Data Structures. Я не прошу ответа, я прошу о помощи.

У меня есть класс стека, который реализует связный список вместо массива. В настоящее время я пытаюсь написать свою функцию pop(). У меня есть узел для моей части пакета.

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

Любая помощь с этим была бы замечательной! Благодаря!

Answer 1

Стек фактически достаточно прост для реализации как отдельный список из-за его ограниченных операций push и pop. На самом деле это намного проще, если вы вставляете толкаемые элементы в головку . Поскольку это домашнее задание, я предоставил псевдокод.

Чтобы инициализировать стек, это просто создание:

top -> null 

с этим кодом:

def init (stk): 
    stk->top = null     # just initialise to empty. 

Раздвигая элемент фактически вставив его в начала списка. Таким образом, когда вы нажимаете 3, 4 и 5, вы получите:

 +---+ 
top -> | 3 | -> null 
     +---+ 
     +---+ +---+ 
top -> | 4 | -> | 3 | -> null 
     +---+ +---+ 
     +---+ +---+ +---+ 
top -> | 5 | -> | 4 | -> | 3 | -> null 
     +---+ +---+ +---+ 

со следующим кодом:

def push (stk, val): 
    item = new node      # Create the node. 
    item->value = val     # Insert value. 
    item->next = stk->top    # Point it at current top. 
    stk->top = item      # Change top pointer to point to it. 

И поппинг затем просто удаление, что первый узел.

def pop (stk): 
    if stk->top == null:    # Catch stack empty error. 
     abort with "stack empty" 
    first = stk->top     # Save it for freeing. 
    val = first->value     # Get the value from the top. 
    stk->top = first->next    # Set top to the top's next. 
    free first       # Release the memory. 
    return val       # Return the value. 

Answer 2

если вы реализуете стек, то вы хотите, чтобы вытолкнуть верхний узел в любом случае, так что вы должны установить theTop быть следующий узел в линии (который должен быть указателем на theTop узла)

Answer 3

Каждого узел в односвязном списке ссылается на предыдущий узел. У самого первого элемента, помещенного в стек, есть NULL, все остальные указывают на элемент «ниже» (предшественник) в стеке.

Итак, прежде чем уничтожить верхний узел, вы захватите обратную ссылку и сохраните ее как новую вершину. Что-то вроде этого псевдокода, который предполагает, что стек Int значений:

pop() 
    ALink *poppedLink = myTop; 
    myTop = poppedLink.nextNode; // point to next node 

    int returnValue = poppedLink.value; // save the value 
    delete poppedLink; // destroy the instance 

    return returnValue; 

Если на «предшественник», вы имеете в виду: «То, что было до этого совал»: что это давно уже нет, не так ли?

Answer 4

Что значит «предшественник» сверху? Верхний узел является главой вашего списка, у него нет предшественников.