java链栈基本操作

链栈是一种使用链表实现的栈。它的基本操作包括初始化链栈、判断链栈是否为空、获取链栈的长度、获取链栈的栈顶元素、向链栈中压入元素、从链栈中弹出元素以及显示链栈的内容。

链栈的基本操作可按照以下步骤实现：

1. 链栈的初始化：创建一个头结点，并将头结点的指针指向null，表示链栈为空。

2. 判断链栈是否为空：通过判断链栈的头结点是否为空来判断链栈是否为空。如果头结点为空，说明链栈中没有元素，返回true；否则，返回false。

3. 获取链栈的长度：从链栈的头结点开始，遍历整个链栈，每遍历一个结点，计数器加1，直到遍历到链栈的末尾。最后返回计数器的值即为链栈的长度。

4. 获取链栈的栈顶元素：直接返回链栈的头结点的数据项。

5. 向链栈中压入元素：创建一个新的结点，将新结点的数据项设置为要压入的元素，然后将新结点的指针指向链栈的头结点，最后将链栈的头结点指向新结点。

6. 从链栈中弹出元素：首先判断链栈是否为空，如果为空，则无法弹出元素；否则，将链栈的头结点指向下一个结点，然后返回弹出的元素。

7. 显示链栈的内容：从链栈的头结点开始，遍历整个链栈，并依次打印每个结点的数据项。

相关问题

1． 根据JAVA所学内容，完成顺序栈类的定义，并实现其基本操作。 2． 根据JAVA所学内容，完成链栈类的定义，并实现其基本操作。 3． 使用栈完成程序解决后缀表达式求值问题，编写该程序，并编写程序对其进行测试， 即：输入后缀表达式，调用该程序计算结果，并输出该结果。

1. **顺序栈（ArrayStack）的定义及基本操作**:
- 首先，在Java中，我们可以使用`java.util.Stack`类作为基础，但它是一个线程安全的，如果你想要自定义无界栈，可以创建一个基于数组的简单版本：

public class ArrayStack {
    private int[] data;
    private int top;

    // 构造函数
    public ArrayStack(int capacity) {
        this.data = new int[capacity];
        this.top = -1;
    }

    // 入栈操作
    public void push(int item) {
        if (isFull()) {
            throw new StackOverflowError("Stack is full");
        }
        data[++top] = item;
    }

    // 出栈操作
    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException("Stack is empty");
        }
        return data[top--];
    }

    // 查看栈顶元素
    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException("Stack is empty");
        }
        return data[top];
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 判断栈是否已满
    public boolean isFull() {
        return top == data.length - 1;
    }
}

2. **链栈（LinkedStack）的定义及基本操作**:
- 这里我们可以使用链表实现，例如`LinkedList`，作为栈的基础：

import java.util.LinkedList;

public class LinkedStack<T> {
    private LinkedList<T> list;

    // 构造函数
    public LinkedStack() {
        this.list = new LinkedList<>();
    }

    // 入栈操作
    public void push(T item) {
        list.addFirst(item);
    }

    // 出栈操作
    public T pop() {
        if (list.isEmpty()) {
            throw new EmptyStackException();
        }
        return list.removeFirst();
    }

    // 查看栈顶元素
    public T peek() {
        if (list.isEmpty()) {
            throw new EmptyStackException();
        }
        return list.getFirst();
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }
}

3. **后缀表达式求值程序**:
- 为了处理后缀表达式（逆波兰表示法），我们需要遍历字符串，将数字入栈，遇到运算符则从栈顶弹出两个数并执行相应的运算，将结果压回栈。这里假设有一个`evaluate`方法用于计算：

public class PostfixEvaluator {
    public static int evaluate(String postfixExpr) {
        ArrayStack<Integer> stack = new ArrayStack<>();
        for (char c : postfixExpr.toCharArray()) {
            if (Character.isDigit(c)) {
                stack.push(Character.getNumericValue(c));
            } else {
                int right = stack.pop();
                int left = stack.pop();
                switch (c) {
                    case '+': stack.push(left + right); break;
                    case '-': stack.push(left - right); break;
                    case '*': stack.push(left * right); break;
                    case '/': stack.push(left / right); break;
                    default: throw new IllegalArgumentException("Invalid operator: " + c);
                }
            }
        }
        return stack.pop();
    }
}

// 测试示例
String expr = "2 3 + 4 *";
System.out.println(PostfixEvaluator.evaluate(expr)); // 输出: 20

编写程序实现链栈的建立、入栈、出栈、输出的基本操作

链栈是一种基于链表的数据结构，其基本操作通常包括以下几个步骤：

1. **建立链栈** (创建栈)：
首先，你需要定义一个节点类，包含数据域和指向下一个节点的引用（通常是`next`）。然后，你可以定义一个链栈类，初始化时保持一个头节点为空（`top = null`）。

class Node {
    int data;
    Node next;
}

class Stack {
    private Node top;
}

2. **入栈 (Push)**：
当需要将元素添加到栈顶时，创建一个新的节点，存储数据，并设置新节点的`next`指向当前的栈顶。然后更新栈顶指针。

void push(int value) {
    Node newNode = new Node();
    newNode.data = value;
    newNode.next = top;
    top = newNode;
}

3. **出栈 (Pop)**：
如果栈非空，移除并返回栈顶元素，同时将栈顶指针指向下一个节点。如果栈空，则抛出异常。

int pop() {
    if (top == null) {
        throw new EmptyStackException();
    }
    int value = top.data;
    top = top.next;
    return value;
}

4. **查看栈顶元素 (Peek 或者 Top)**：
只能查看栈顶元素，但不删除它。同样，如果栈空则抛出异常。

int peek() {
    if (top == null) {
        throw new EmptyStackException();
    }
    return top.data;
}

5. **判断栈是否为空 (IsEmpty)**：
检查栈顶是否为`null`即可。

boolean isEmpty() {
    return top == null;
}