在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;
}
}
假设您真的想从头开始而不是使用一个完美的现有堆栈实现，那么我建议:
- 创建一个"MyStack<类，它实现了你想要的任何接口(可能是List>
?) - 在MyStack中创建一个"私有静态final类Node<每个链表项的T>"内部类。每个节点包含一个对T类型对象的引用和一个对"下一个"节点的引用。
- 添加一个"topOfStack"节点引用到MyStack。
- 推送和弹出操作只需要在这个topOfStack节点上操作。如果它为空，则堆栈为空。我建议使用与标准Java堆栈相同的方法签名和语义，以避免以后的混淆.....
- 最后实现您需要的任何其他方法。为了加分，实现"Iterable<在创建迭代器时，它会记住堆栈的不可变状态，而不需要任何额外的存储分配(这>是可能的:-))
为什么不直接使用已经存在的Stack实现呢?
或者更好(因为它真的是一个链表，它的速度快，它的线程安全):LinkedBlockingDeque
如果您谈论的是单个链表(一个节点有对下一个对象的引用，但不是对前一个对象的引用)，那么类将看起来像这样:
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;
}
}
当然，您还需要编写其余方法的代码以使其正常有效地工作，但是您已经具备了基础。希望这对你有帮助!
使用LinkedList实现堆栈-这个StackLinkedList类内部维护LinkedList引用。
StackLinkedList的push方法内部调用了linkedList的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 (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
}
}
显示堆栈>从上到下:76 11 71 39
显示堆栈>从上到下:71 39
提供:http://www.javamadesoeasy.com/2015/02/implement-stack-using-linked-list.html
使用STL适配器std::stack。为什么?因为不需要编写的代码是完成任务的最快方式。stack经过了良好的测试，可能不需要您的任何关注。为什么不呢?因为你的代码需要一些特殊用途的需求，在这里没有记录。
默认情况下，stack使用deque双端队列，但它只要求底层容器支持"反向插入序列"，也称为.push_back。
typedef std::stack< myType, std::list<myType> > myStackOfTypes;
这是一个使用数组和链表栈实现的教程。
这要看情况而定。
数组:-你不能调整它的大小(固定大小)LinkedList:-它比基于数组的占用更多的内存，因为它想要在内存中保留下一个节点。
我看到了许多使用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());
}
}