Java?栈与队列实战真题训练

栈与队列是数据结构中最常用的两种数据结构，其中栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。它们在计算机科学和软件工程领域中得到了广泛的应用，比如逆波兰表达式、迷宫求解、操作系统进程调度等。

本文将介绍栈与队列的实战题目，并提供相关解答思路和代码实现。这些题目所涉及的知识点包括了栈和队列的基本操作、栈的应用、队列的应用等。

栈的基本操作

1.实现一个栈的基本操作（包括压栈、弹栈、判断栈是否为空、获取栈顶元素等）。

解答思路：

可以用数组或链表来实现栈的基本操作。对于数组实现，需要定义一个数组和一个指针，指针指向最后一个入栈的元素。对于链表实现，需要定义一个链表结构，其中每个节点保存一个元素和一个指向下一个节点的指针。

以下是使用数组实现的代码：

class ArrayStack {
    private int[] arr;
    private int top = -1;

    public ArrayStack(int size) {
        arr = new int[size];
    }

    public void push(int data) {
        if (top == arr.length - 1) {
            throw new RuntimeException("Stack is full.");
        }
        arr[++top] = data;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty.");
        }
        return arr[top--];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty.");
        }
        return arr[top];
    }
}

以下是使用链表实现的代码：

class Node {
    int data;
    Node next;
    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
}

class LinkedStack {
    private Node top = null;

    public void push(int data) {
        top = new Node(data, top);
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty.");
        }
        int data = top.data;
        top = top.next;
        return data;
    }

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

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty.");
        }
        return top.data;
    }
}

2.实现一个计算器，可以进行四则运算，包括加减乘除。

解答思路：

可以使用栈来实现一个简单的计算器，具体步骤如下：

（1）定义两个栈：一个保存操作数，一个保存运算符。

（2）读入字符串表达式，从左到右扫描每个字符。

（3）如果当前字符是操作数，则直接入操作数栈。

（4）如果当前字符是左括号，则直接入运算符栈。

（5）如果当前字符是右括号，则弹出运算符栈顶元素和操作数栈顶的两个元素进行运算，并将结果入操作数栈，直到遇到左括号。

（6）如果当前字符是运算符，比较其与运算符栈栈顶元素的优先级。如果当前运算符优先级较低，则弹出运算符栈顶元素和操作数栈顶的两个元素进行运算，并将结果入操作数栈，重复此操作直到当前运算符优先级较高或运算符栈为空，最后将当前运算符入运算符栈。

（7）最后，当表达式扫描完之后，如果运算符栈不为空，按照上述方式依次弹出运算符栈顶元素和操作数栈顶的两个元素进行运算。

以下是代码实现：

class Calculator {
    private LinkedStack numberStack = new LinkedStack();
    private LinkedStack operatorStack = new LinkedStack();

    private int priority(char operator) {
        if (operator == '*' || operator == '/') {
            return 2;
        } else if (operator == '+' || operator == '-') {
            return 1;
        } else {
            throw new RuntimeException("Invalid operator: " + operator);
        }
    }

    private void performOperation() {
        char operator = (char) operatorStack.pop();
        int operand2 = numberStack.pop();
        int operand1 = numberStack.pop();
        int result;
        switch (operator) {
            case '+':
                result = operand1 + operand2;
                break;
            case '-':
                result = operand1 - operand2;
                break;
            case '*':
                result = operand1 * operand2;
                break;
            case '/':
                result = operand1 / operand2;
                break;
            default:
                throw new RuntimeException("Invalid operator: " + operator);
        }
        numberStack.push(result);
    }

    public int calculate(String expression) {
        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            if (ch == ' ') {
                continue;
            } else if (ch == '(') {
                operatorStack.push(ch);
            } else if (ch == ')') {
                while ((char) operatorStack.peek() != '(') {
                    performOperation();
                }
                operatorStack.pop(); // pop '('
            } else if (ch >= '0' && ch <= '9') {
                int number = 0;
                while (i < expression.length() && expression.charAt(i) >= '0' && expression.charAt(i) <= '9') {
                    number = number * 10 + (expression.charAt(i) - '0');
                    i++;
                }
                i--;
                numberStack.push(number);
            } else {
                while (!operatorStack.isEmpty() && priority(ch) <= priority((char) operatorStack.peek())) {
                    performOperation();
                }
                operatorStack.push(ch);
            }
        }
        while (!operatorStack.isEmpty()) {
            performOperation();
        }
        return numberStack.pop();
    }
}

队列的基本操作

3.实现一个队列的基本操作（包括入队、出队、获取队列头元素、判断队列是否为空等）。

解答思路：

可以使用数组或链表来实现队列的基本操作。对于数组实现，需要定义一个数组和两个指针，一个指针指向队列头，一个指针指向队列尾。对于链表实现，需要定义一个链表结构，其中每个节点保存一个元素和一个指向下一个节点的指针，同时需要维护两个指针，一个指向队列头，一个指向队列尾。

以下是使用数组实现的代码：

class ArrayQueue {
    private int[] arr;
    private int front = 0;
    private int rear = -1;

    public ArrayQueue(int size) {
        arr = new int[size];
    }

    public void enqueue(int data) {
        if (rear == arr.length - 1) {
            throw new RuntimeException("Queue is full.");
        }
        arr[++rear] = data;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty.");
        }
        return arr[front++];
    }

    public boolean isEmpty() {
        return front > rear;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty.");
        }
        return arr[front];
    }
}

以下是使用链表实现的代码：

`java

class LinkedQueue {

class Node {

int data;

Node next;

public Node(int data, Node next) {

this.data = data;

this.next = next;

}

}

private Node front = null;

private Node rear = null;

public void enqueue(int data) {

if (rear == null) {

front = rear = new Node(data, null);

} else {

rear.next = new Node(data, null);

rear = rear.next;

}

}

public int dequeue() {

if (isEmpty()) {

throw new RuntimeException("Queue is empty.");

}

int data =