Implementación de la pila usando listas vinculadas

Question

¿Cuál es la mejor manera de implementar una pila usando listas enlazadas en Java?

EDITAR: Definiría mejor como el más eficiente utilizando código limpio. Ya he utilizado una matriz para implementar una pila, pero no estoy familiarizado con listas de enlaces por lo que preguntaba si alguien me podría ayudar a implementar algo similar a continuación:

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

EDIT: Aquí está la aplicación lista enlazada si alguien está interesado ..

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

Suponiendo que realmente quiere hacer esto desde el principio en lugar de utilizar uno de los perfectly good existing stack implementations entonces recomendaría:

• Crear un "MyStack < T>" clase que implementa las interfaces que desea (tal vez Lista < T>?)
• Dentro MyStack crear un "nodo privada de clase static final < T>" clase interna para cada li ítem de la lista. Cada nodo contiene una referencia a un objeto de tipo T y una referencia a un "siguiente" nodo.
• Agregue una referencia de nodo "topOfStack" a MyStack.
• Las operaciones push y pop solo necesitan operar en este nodo TopOfStack. Si es nulo, la Pila está vacía. Sugiero usar el mismo método de firmas y semántica que la pila Java estándar, para evitar confusiones posteriores ...
• Finalmente, implemente cualquier otro método que necesite. Para los puntos de bonificación, implementar "Iterable < T>" de tal manera que recuerda el estado inmutable de la pila en el momento en que se creó el iterador sin ningún tipo de asignaciones adicionales de almacenamiento (esto es posible :-))

Answer 2

Utilice el adaptador STL std::stack. ¿Por qué? Debido a que el código que no debe escribir es la forma más rápida de completar su tarea. stack está bien probado y es probable que no necesite su atención. Por qué no? Debido a que hay algunos requisitos de propósito especial necesarios para su código, no documentados aquí.

Por defecto stack utiliza un deque cola de doble extremo, sino que se limita a exigir el contenedor subyacente para apoyar la "secuencia de inserción Volver", también conocido como .push_back.

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

Answer 3

¿Por qué no sólo tiene que utilizar la aplicación Stack ya ahí?

O mejor (porque realmente una lista enlazada, su rapidez y su seguro para hilos): LinkedBlockingDeque

Answer 4

Si estamos hablando de una sola lista enlazada (un nodo tiene una referencia al siguiente objeto, pero no la anterior), entonces la clase sería algo como esto:

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

} 

Por supuesto que sí necesita codificar el resto de los métodos para que funcione correctamente y de manera efectiva, pero tiene los conceptos básicos. Espero que esto ayude!

Answer 5

Aquí hay un tutorial que implements stack in Java using linked list. Implementa métodos push y pop junto con un iterador para iterar a través de elementos de la pila. Espero que ayude

Answer 6

Para implementar la pila utilizando LinkedList: esta clase StackLinkedList mantiene internamente la referencia LinkedList.

método push de StackLinkedList llama internamente el método de LinkedList insertFirst()

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

método de StackLinkedList llama internamente el método de LinkedList deleteFirst()

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

Programa Completo

/** 
*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 
    } 
} 

SALIDA

Viendo Pila> De arriba a abajo: 76 11 71 39

Viendo Pila> De arriba a abajo: 71 39

Cortesía: http://www.javamadesoeasy.com/2015/02/implement-stack-using-linked-list.html

Answer 7

Aquí es un tutorial implementar utilizando una matriz y una lista vinculada stack implementation.

Depende de la situación.

Matriz: - no se puede cambiar el tamaño (corregir el tamaño) LinkedList: - Se necesita más memoria que la basada en la matriz, ya que quiere mantener el siguiente nodo en la memoria.

Answer 8

Vi muchas implementaciones de pila usando LinkedList, al final entiendo qué pila es ... y la apilé por mí misma (para mí es limpia y eficiente). Espero que den la bienvenida a nuevas implementaciones. Aquí el código sigue.

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

Y aquí la clase principal para ello.

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()); 

    } 
}