C ++ - Stack Pop () функция с односвязным списком

Question

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

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

Я просто не понимаю, как добраться до предшественника моего узла theBack.Спасибо!

Answer 1

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

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

top -> null

с этим кодом:

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

Pushingэлемент фактически вставляет его в начало списка.Таким образом, когда вы нажимаете 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.

И тогда popping просто удаляет этот первый узел.

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

Каждый узел в односвязном списке ссылается на предыдущий узел.Самый первый элемент, помещенный в стек, имеет значение 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 3

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

Answer 4

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