使用链接列表实现堆栈

在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中，为每个链接列表项创建“私有静态最终类Node ”内部类。 每个节点包含对类型为T的对象的引用和对“下一个”节点的引用。
• 添加一个“topOfStack”节点引用到MyStack。
• 推送和弹出操作只需要在这个topOfStack节点上运行。 如果为null，则堆栈为空。 我建议使用与标准Java堆栈相同的方法签名和语义，以避免以后的混淆…..
• 最后实现您需要的任何其他方法。 对于奖励积分，实施“Iterable ”，以便在创建迭代器时记住堆栈的不可变状态，而无需任何额外的存储分配（这是可能的:-)）

Answer 2

你为什么不在那里使用Stack实现呢？

或者更好（因为它确实是一个链表，它的速度很快，而且它的线程安全）： LinkedBlockingDeque

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

使用LinkedList实现堆栈 – 此StackLinkedList类在内部维护LinkedList引用。

StackLinkedList的push方法在内部调用了insertFirst()的insertFirst()方法

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

StackLinkedList的方法在内部调用linkedList的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 (ie 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 5

使用STL适配器std::stack 。 为什么？ 因为您不必编写的代码是完成任务的最快方法。 stack经过充分测试，可能不需要您的任何关注。 为什么不？ 因为您的代码需要一些特殊用途的要求，所以这里没有记录。

默认情况下， stack使用deque双端队列，但它只需要底层容器支持“Back Insertion Sequence”，也称为.push_back 。

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

Answer 6

这是一个使用链表在Java中实现堆栈的教程。 它实现了push和pop方法以及迭代器来迭代堆栈项。 希望它会有所帮助。

Answer 7

这是一个使用数组和链表列表实现的教程实现 。

这取决于实际情况。

数组： – 你不能调整它的大小（修复大小）LinkedList： – 它需要比基于数组的内存更多的内存，因为它想要将下一个节点保留在内存中。

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