Как работает стек в связанной структуре?

Question

Я понимаю большую часть следующего кода, но мне просто неясно, как работает метод pop. Я не понимаю, почему, когда вызывается top.getNext (), он возвращает предыдущий узел. То же самое с методом push. Почему вызывается temp.setNext (top), а затем top назначается temp?

public class Stack {

private Node top;

public Stack()
{
    top = null;
}

public void push(int v)
{
    Node temp = new Node();
    temp.setValue(v);
    temp.setNext(top);
    top = temp;
}

public int peek()
{
    return top.getValue();
}

public int pop()
{
    int temp = top.getValue();
    top = top.getNext();
    return temp;
}

public boolean isEmpty()
{
    return(top == null);
}

public void makeEmpty()
{
    top = null;
}

}

public class Node {

private int value;
private Node next;

public void setValue(int v)
{
    value = v;
}

public int getValue()
{
    return value;
}

public void setNext(Node n)
{
    next = n;
}

public Node getNext()
{
    return next;
}

}

Набор следующего кода - это то, что действительно смущает меня.

Answer 1

Скажем, вы хотите поместить значения 1,2,3,4 в стек:

push (1): Stack = {1} | Верх 1

push (2): Stack = {2 => 1} | Верх 2

push (3): Stack = {3 => 2 => 1} | Верх 3

push (4): Stack = {4 => 3 => 2 => 1} | Верх 4

Чтобы получить его поведение при добавлении узла, вы должны создать новый узел, в этом случае temp со значением, добавленным к добавляемому значению. Теперь, так как этот узел будет новой вершиной, узел, на который он указывает, должен быть текущей вершиной стека. Следовательно, setNext (top); . Теперь, чтобы сделать новый узел вершиной стека, вы должны установить его соответствующим образом через top = temp; .

Теперь, если мы вытолкнем значение из стека выше:

pop (): возвращаемое значение = 4 | Стек = {3 => 2 => 1} | Верх 3

Чтобы получить это поведение, мы получаем значение текущей вершины стека, поэтому int temp = top.getValue (); . Теперь мы не хотим, чтобы этот узел больше был вершиной, мы хотим, чтобы новая вершина была узлом, на который указывает текущая вершина, поэтому top = top.getNext (); . Осталось только вернуть значение, которое мы сохранили в temp, и мы правильно вытолкнули стек.

Answer 2

Чтобы ответить на ваши вопросы, давайте рассмотрим, как концептуально работает стек. Позвольте мне привести пример.

Допустим, вы моете посуду. В этом примере мы можем мыть только 1 блюдо за раз. Когда вы чистите блюдо в первый раз, вы кладете его на стол. Следующее блюдо, которое вы чистите, идет поверх этого. Каждый раз, когда вы чистите блюдо, вы кладете это вершина существующей стопки посуды. Последнее блюдо, которое вы убрали, всегда находится на вершине стека, а последовательно старые блюда - все дальше и дальше. Нижнее блюдо - то, которое было убрано сначала.

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

Давайте рассмотрим другой пример. Скажем, мы помещаем птицу, рыбу, собаку и кошку в стопку в таком порядке. Это будет выглядеть так

Stack after bird, fish, dog pushed
----------------------------------
top:    dog
        fish
bottom: bird

Stack after cat pushed
----------------------
top:    cat
        dog
        fish
bottom: bird        

Stack after a pop operation
---------------------------
top:    dog
        fish
bottom: bird

Когда мы выталкиваем кошку из верха стека, собака становится новой вершиной. Мы знаем это, потому что мы можем видеть весь стек. Однако код не может видеть весь стек. Так что код делает что-то умное.

Когда новое животное помещается в стек, старая вершина сохраняется вместе с тем животным, которое было только что добавлено. Другими словами, кошка помнит, что собака раньше была верхом. Зачем? Так что, если мы поп-кошка, вершина вернется к тому, что было раньше.

Это то, что возвращает top.getNext () - старая вершина после всплывающего окна, которой назначена вершина. То, что раньше было вершиной, стало текущей вершиной. Теперь мы знаем, что собака является вершиной стека.

Что это помнит, чтобы top.getNext () вернул старую вершину? Это достигается с помощью temp.setNext (вверху), который происходит при выполнении push. Когда добавляется cat, перед обновлением top, чтобы он стал cat, старый топ сохраняется с помощью cat.

Answer 3

Структура данных стека работает как LIFO (последний пришел первым вышел).

С учетом этого приведенный выше код структурирован таким образом, что каждый добавленный узел будет указывать узел на вершину стека. И top будет назначен для ссылки на этот недавно добавленный узел. Это обеспечивается методом setNext (). С той же логикой, когда узел выталкивается; следующий узел, добавленный перед ним, будет новым верхним узлом.

Например, предположим, что стек пуст. Когда будет добавлен первый узел, top будет ссылаться на этот узел. Когда второй узел добавлен, он должен быть новым верхом в соответствии с LIFO. Поэтому, когда он будет добавлен в стек, его следующий узел будет указывать на текущий верхний узел, первый. После этого вершина будет ссылаться на этот новый узел. Здесь установка следующего узла для ранее добавленного узла помогает нам найти новый верхний узел, если мы вытолкнем этот недавно добавленный узел.