栈的Java实现和栈的应用举例(Java栈实现及其应用实例解析)

原创

ithorizon 7个月前 (10-20) 阅读数 14 #后端开发

栈的Java实现和栈的应用举例

一、栈的Java实现

栈（Stack）是一种后进先出（Last In First Out，LIFO）的数据结构。在栈中，只能在栈顶进行插入和删除操作。下面将介绍怎样使用Java实现一个简洁的栈。

1. 栈的接口定义

首先，我们定义一个栈的接口，包括基本操作：push（入栈）、pop（出栈）、peek（查看栈顶元素）和isEmpty（判断栈是否为空）。


public interface Stack<E> {
    void push(E element);
    E pop();
    E peek();
    boolean isEmpty();
}

2. 栈的实现

接下来，我们使用数组来实现栈。这里需要注意的是，数组的长度是固定的，故而在插入元素时需要判断栈是否已满。


public class ArrayStack<E> implements Stack<E> {
    private E[] elements;
    private int size;
    public ArrayStack(int capacity) {
        elements = (E[]) new Object[capacity];
        size = 0;
    }
    @Override
    public void push(E element) {
        if (size == elements.length) {
            throw new IllegalStateException("Stack is full");
        }
        elements[size++] = element;
    }
    @Override
    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return elements[--size];
    }
    @Override
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return elements[size - 1];
    }
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}

二、栈的应用举例

栈在编程中有着广泛的应用。下面将通过几个实例来展示栈在实际问题中的使用。

1. 浏览器历史记录

在浏览器中，我们经常性使用前进和后退按钮来浏览历史记录。实际上，浏览器可以使用两个栈来实现这个功能：一个栈用于保存后退的历史记录，另一个栈用于保存前进的历史记录。


public class BrowserHistory {
    private Stack<String> backStack;
    private Stack<String> forwardStack;
    public BrowserHistory() {
        backStack = new ArrayStack<>(100);
        forwardStack = new ArrayStack<>(100);
    }
    public void visit(String url) {
        backStack.push(url);
        forwardStack.clear();
    }
    public void back() {
        if (backStack.isEmpty()) {
            return;
        }
        forwardStack.push(backStack.pop());
    }
    public void forward() {
        if (forwardStack.isEmpty()) {
            return;
        }
        backStack.push(forwardStack.pop());
    }
}

2. 括号匹配

在编程中，我们经常性需要检查括号是否成对出现。使用栈可以很方便地解决这个问题。


public class BracketMatcher {
    public static boolean isBalanced(String expression) {
        Stack<Character> stack = new ArrayStack<>(expression.length());
        for (char ch : expression.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((ch == ')' && top != '(') ||
                    (ch == ']' && top != '[') ||
                    (ch == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

3. 逆序输出

使用栈可以实现字符串的逆序输出。我们只需要将字符串的每个字符依次入栈，然后依次出栈，即可得到逆序的字符串。


public class ReverseString {
    public static String reverse(String str) {
        Stack<Character> stack = new ArrayStack<>(str.length());
        for (char ch : str.toCharArray()) {
            stack.push(ch);
        }
        StringBuilder reversed = new StringBuilder();
        while (!stack.isEmpty()) {
            reversed.append(stack.pop());
        }
        return reversed.toString();
    }
}