Реализация стека с использованием связанных списков

Ответ 1

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

• Создайте класс "MyStack <T> ", который реализует любые необходимые вам интерфейсы (возможно, List <T> ?)
• Внутри MyStack создайте внутренний класс private private final Node <T> для каждого элемента связанного списка. Каждый node содержит ссылку на объект типа T и ссылку на "следующий" Node.
• Добавьте ссылку "topOfStack" node на MyStack.
• Операции push и pop просто должны работать на этом topOfStack Node. Если он равен нулю, стек будет пустым. Я бы предложил использовать те же подписи и семантику методов, что и стандартный стек Java, чтобы избежать более поздней путаницы.....
• Наконец, выполните любые другие методы, которые вам нужны. Для бонусных очков реализуйте "Iterable <T> " таким образом, чтобы он запоминал неизменяемое состояние стека в момент создания итератора без каких-либо дополнительных распределений памяти (это возможно:-))

Ответ 2

Почему бы вам не использовать Stack уже там?

Или лучше (потому что это действительно связанный список, его быстрый и безопасный поток): LinkedBlockingDeque

Ответ 3

Если вы говорите об одном связанном списке (node имеет ссылку на следующий объект, но не на предыдущий), тогда класс будет выглядеть примерно так:

public class LinkedListStack {

    private LinkedListNode first = null;
    private LinkedListNode last = null;
    private int length = 0;

    public LinkedListStack() {}

    public LinkedListStack(LinkedListNode firstAndOnlyNode) {
        this.first = firstAndOnlyNode;
        this.last = firstAndOnlyNode;
        this.length++;
    }

    public int getLength() {
        return this.length;
    }

    public void addFirst(LinkedListNode aNode) {
        aNode.setNext(this.first);
        this.first = aNode;
    }

}

public class LinkedListNode {

    private Object content = null;
    private LinkedListNote next = null;

    public LinkedListNode(Object content) {
        this.content = content;
    }

    public void setNext(LinkedListNode next) {
        this.next = next;
    }

    public LinkedListNode getNext() {
        return this.next;
    }

    public void setContent(Object content) {
        this.content = content;
    }

    public Object getContent() {
        return this.content;
    }

}

Конечно, вам нужно будет закодировать остальные методы, чтобы он работал правильно и эффективно, но у вас есть основы. Надеюсь, это поможет!

Ответ 4

Для реализации стека с использованием LinkedList. Этот класс StackLinkedList внутренне поддерживает ссылку LinkedList.

Метод push StackLinkedList внутренне вызывает метод linkedLists insertFirst()

public void push(int value){
    linkedList.insertFirst(value);
}

Метод StackLinkedLists внутренне вызывает метод linkedLists deleteFirst()

public void pop() throws StackEmptyException {
    try{
        linkedList.deleteFirst();
    }catch(LinkedListEmptyException llee){
        throw new StackEmptyException();
    }
}

Полная программа

/**
 *Exception to indicate that LinkedList is empty.
 */

class LinkedListEmptyException extends RuntimeException{
    public LinkedListEmptyException(){
        super();
    }

    public LinkedListEmptyException(String message){
        super(message);
    }  
}

/**
 *Exception to indicate that Stack is empty.
 */

class StackEmptyException extends RuntimeException {

    public StackEmptyException(){
        super();
    }

    public StackEmptyException(String message){
        super(message);
    }
}

/**
 *Node class, which holds data and contains next which points to next Node.
 */
class Node {
    public int data; // data in Node.
    public Node next; // points to next Node in list.

    /**
     * Constructor
     */
    public Node(int data){
        this.data = data;
    }

    /**
     * Display Node data
     */
    public void displayNode() {
        System.out.print( data + " ");
    }
}


/**
 * LinkedList class
 */
class LinkedList {
    private Node first; // ref to first link on list

    /**
     * LinkedList constructor
     */
    public LinkedList(){
        first = null;
    }

    /**
     * Insert New Node at first position
     */
    public void insertFirst(int data) {
        Node newNode = new Node(data);  //Creation of New Node.
        newNode.next = first;   //newLink ---> old first
        first = newNode;    //first ---> newNode
    }

    /**
     * Deletes first Node
     */
    public Node deleteFirst()
    {
        if(first==null){    //means LinkedList in empty, throw exception.               
            throw new LinkedListEmptyException("LinkedList doesn't contain any Nodes.");
        }
        Node tempNode = first; // save reference to first Node in tempNode- so that we could return saved reference.
        first = first.next; // delete first Node (make first point to second node)
        return tempNode; // return tempNode (i.e. deleted Node)
    }


    /**
     * Display LinkedList
     */
    public void displayLinkedList() {
        Node tempDisplay = first; // start at the beginning of linkedList
        while (tempDisplay != null){ // Executes until we don't find end of list.
            tempDisplay.displayNode();
            tempDisplay = tempDisplay.next; // move to next Node
        }
        System.out.println();   
    }
}


/**
 * For implementing stack using using LinkedList- This StackLinkedList class internally maintains LinkedList reference.
 */

class StackLinkedList{

    LinkedList linkedList = new LinkedList(); // creation of Linked List

    /**
     * Push items in stack, it will put items on top of Stack.
     */
    public void push(int value){
        linkedList.insertFirst(value);
    }

    /**
     * Pop items in stack, it will remove items from top of Stack.
     */
    public void pop() throws StackEmptyException {
        try{
            linkedList.deleteFirst();
        }catch(LinkedListEmptyException llee){
            throw new StackEmptyException();
        }
    }

    /**
     * Display stack.
     */
    public void displayStack() {
        System.out.print("Displaying Stack >  Top to Bottom : ");
        linkedList.displayLinkedList();
    }
}


/**
 * Main class - To test LinkedList.
 */
public class StackLinkedListApp {
    public static void main(String[] args) {

        StackLinkedList stackLinkedList=new StackLinkedList();
        stackLinkedList.push(39);  //push node.
        stackLinkedList.push(71);  //push node.
        stackLinkedList.push(11);  //push node.
        stackLinkedList.push(76);  //push node.

        stackLinkedList.displayStack(); // display LinkedList

        stackLinkedList.pop();  //pop Node
        stackLinkedList.pop();  //pop Node

        stackLinkedList.displayStack(); //Again display LinkedList
    }
}

OUTPUT

Отображение стекa > Вверху донизу: 76 11 71 39

Отображение стекa > Вверху донизу: 71 39

Предоставлено: http://www.javamadesoeasy.com/2015/02/implement-stack-using-linked-list.html

Ответ 5

Используйте адаптер STL std::stack. Зачем? Потому что код, который вам не нужно писать, - это самый быстрый способ выполнить вашу задачу. stack хорошо протестирован и, вероятно, вам не понадобится никакого внимания. Почему нет? Поскольку для вашего кода требуются некоторые специальные требования, недокументированные здесь.

По умолчанию stack использует очередность с двумя концами deque, но для этого требуется, чтобы базовый контейнер поддерживал "Обратную последовательность вставки", также известную как .push_back.

typedef std::stack< myType, std::list<myType> > myStackOfTypes;

Ответ 6

Вот учебник, в котором реализует стек в Java, используя связанный список. Он реализует push и pop методы вместе с итератором для итерации по элементам стека. Надеюсь, это поможет.

Ответ 7

Ниже приведен пример использования учебника с использованием массива и связанного списка реализация стека.

Это зависит от ситуации.

Массив: - вы не можете изменить его размер (размер исправления) LinkedList: это занимает больше памяти, чем массив, потому что он хочет сохранить следующий node в памяти.

Ответ 8

Я видел много реализации стека с помощью LinkedList, В конце я понимаю, какой стек... и реализовал стек сам (для меня он чистый и эффективный). Надеюсь, вы приветствуете новые реализации. Здесь следует код.

class Node
{
    int     data;
    Node    top;

    public Node()
    {

    }

    private Node(int data, Node top)
    {
        this.data = data;
        this.top = top;
    }

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

    public boolean push(int data)
    {
        top = new Node(data, top);
        return true;
    }

    public int pop()
    {
        if (top == null)
        {
            System.out.print("Stack underflow<-->");
            return -1;
        }
        int e = top.data;
        top = top.top;
        return e;
    }
}

И вот главный класс для него.

public class StackLinkedList
{
    public static void main(String[] args)
    {
        Node stack = new Node();
        System.out.println(stack.isEmpty());
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
        System.out.println(stack.pop());

    }
}