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

Question

Каков наилучший способ реализации стека с использованием связанных списков в Java?

РЕДАКТИРОВАТЬ: я бы лучше определил как наиболее эффективный, используя чистый код.Я уже использовал массив для реализации стека, но не знаком со списками ссылок, поэтому мне было интересно, если кто-нибудь может помочь мне реализовать что-то похожее на приведенное ниже:

public class StackArray{

    private Object [] objArray;
    private int stackSize;

    public StackArray(){
        objArray = new Object[50];
        stackSize = 0;
    }

    public StackArray(int size){
        objArray = new Object[size];
        stackSize = 0;
    }

    //public interface methods - push, pop, top, empty & clear
    public void push(Object o)throws StackArrayException{
        if(stackSize < objArray.length){
            objArray[stackSize] = o;
            stackSize ++;
        }else{
            throw new StackArrayException("Stack Overflow");
        }
    }

    public Object pop()throws StackArrayException{
        if(stackSize != 0){
            stackSize--;
            return(objArray[stackSize]);
        }else{
            throw new StackArrayException("Stack Underflow");
        }
    }

    public void top() throws StackArrayException{
        if(stackSize != 0){
            return(objArray[stackSize-1]);
        }else{
            throw new StackArrayException("Stack Underflow");
        }
    }

    public boolean empty(){
        return (stackSize == 0):
    }

    public void clear(){
        stackSize = 0;
    }
}

РЕДАКТИРОВАТЬ: Вот реализация связанного списка, есливсем интересно ..

public class StackList{
    private Node listHead;

    protected class Node{
    protected Object datum;
    protected Node next;

    public Node(Object o, Node n){
        datum = o;
        next = n;
    }

    public StackList(){
        listHead = null;
    }

    //public interface methods - push pop top empty clear
    public void push(Object o){
        listHead = new Node(o, listHead);
    }

    public Object pop() throws StackListException{
        if(listHead!=null){
            Object top = listHead.datum;
            listHead = listHead.next;
            return top;
        }else{
            throw new StackListException("Stack Underflow");
        }
    }

    public Object top()throws StackListException{
        if(listHead != null){
            return(listHead.datum);
        }else{
            throw new StackListException("Stack Underflow");
        }
    }

    public boolean empty(){
        return (listHead == null);
    }

    public void clear(){
        listHead = null;
    }
}

Answer 1

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

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

Answer 2

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

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

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

Метод StackLinkedList внутренне вызывает метод 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's 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

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

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

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

Answer 3

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

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;
    }

}

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

Answer 4

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

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

Answer 5

Я видел много реализаций стека с использованием 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());

    }
}

Answer 6

Вот учебная реализация, использующая массив и связанный список Реализация стека .

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

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

Answer 7

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

Answer 8

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

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

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