链表 - JAVA - 使用链表实现堆栈

Question

我正在尝试实现堆栈，即使用我的链表DSAStack.java

，即DSALinkedList.java

我该怎么做？我想我应该push()执行一个insertFirst()，pop()做一个peekFirst()和removeFirst()来获得后进先出行为？那么isEmpty()呢和其他方法呢？

我

不确定，请帮帮我。用代码进行清晰的解释会非常明显。提前谢谢你！

这是DSAStack.java

public class DSAStack implements Iterable {
    public static int DEFAULT_CAPACITY = 100;
    private DSALinkedList list;
    private int           count;
    private Object[]      stack;
    public DSAStack() {
        count = 0;
        stack = new Object[DEFAULT_CAPACITY];
}
public DSAStack(int maxCapacity) {
    count = 0;
    stack = new Object[maxCapacity];
    }
    public int getCount() {
        return count;
    }
    public boolean isEmpty() {
        boolean empty = (count == 0);   
        return empty;   
    }
    public boolean isFull() {
        boolean full = (count == stack.length);
        return full;            
    }
    public void push(Object value) {
        if (isFull())
            throw new IllegalArgumentException("Stack is full");
        else
            stack[count] = value;
        count++;
    }
    public Object pop() {
        Object topVal = top();
        count--;
        return topVal;
    }
    public Object top() {
        Object topVal;
        if (isEmpty()) 
            throw new IllegalArgumentException("Stack is empty");
        else
            topVal = stack[count-1];
        return topVal; 
    }
    public Iterator iterator() {
        return list.iterator();
    }
}

这是DSALinkedList.java

import java.util.*;
public class DSALinkedList {
    public DSAListNode head;
    public DSAListNode tail;
    Object[] newValue;
    public DSALinkedList() {
        head = null;
        tail = null;
    }
    public void insertFirst(Object newValue){
        DSAListNode newNd;
        newNd = new DSAListNode(newValue);
        if (head == null) {
            head = newNd;
            tail = newNd;   
        } else {
            newNd.setNext(head);
            head = newNd;
        }
    }
    public void insertLast(Object newValue){
        DSAListNode newNd;
        newNd = new DSAListNode(newValue);
        if(head == null){
            head = newNd;
        } else {
            tail.next = newNd;
            tail      = newNd;  
        }
    }
    public boolean isEmpty() {
        return (head == null);
    }
    public Object peekFirst(){
        Object nodeValue;
        if (head == null)
            throw new IllegalArgumentException("head is empty");
        else 
            nodeValue = head.getValue();
        return nodeValue;
    }
    public Object peekLast(){
        Object nodeValue;
        if (head == null)
            throw new IllegalArgumentException("head is empty");
        else
            nodeValue = tail.getValue();
        return nodeValue;
    }
    public Object removeFirst(){
        Object nodeValue;
        if (head == null){
            throw new IllegalArgumentException("head is empty");
        } else {
            nodeValue = head.getValue();
            head      = head.getNext();
        }
        return nodeValue;
    }
}

Answer 1

DSAStack 类是用户和链接列表之间的接口。因此，该类提供了 LIFO 接口并将其强制给用户。从这里开始，它应该从linkedlist中隐藏实现，这样用户就不必担心插入最后或插入第一，他们只想插入。

所以回答你的问题。DSAStack 需要执行以下操作：

- size() -> returns int size
- push(Object e) -> returns bool (able to be inserted)
- pop() -> returns Object and removes it from linkedlist
- peek() -> returns Object
- isEmpty() -> returns bool if empty

您的DSAStack并不意味着保存任何数据。因此，您不需要计数或堆栈变量。相反，我们需要将它们存储在 DSALinkedList 类中。 因此，DSAStack 应实例化 DSALinkedList 对象，传递 maxCapacity，然后启动该对象。

当用户说他们想在DSAStack上使用pop（）时，该类需要告诉DSALinkedList，嘿！我想弹出你的一个对象！现在，DSALinkedList需要在此处实现详细信息。

重写代码将是这样的：

    public DSAStack(int maxCapacity) {
        list = new DSALinkedList[maxCapacity];
    }
    public int getCount() {
        return list.size();
    }
    public boolean isEmpty() {
        return list.isEmpty(); 
    }
    public boolean isFull() {
        return list.isFull();          
    }
    public void push(Object value) {
        list.insertLast(value);
    }
    public Object pop() {
        return list.removeLast();
    }
    public Object top() {
        return list.peekLast();
    }
    public Iterator iterator() {
        return list.iterator();
    }
}