栈与队列：数据结构的基础应用

### 栈与队列：数据结构的基础应用 在数据结构的世界里，栈和队列是两种基础且重要的结构。它们在编程中有着广泛的应用，从简单的文本处理到复杂的算法实现，都离不开这两种结构的支持。下面将详细介绍栈和队列的相关知识，包括它们的操作、应用场景以及具体的代码实现。 #### 栈的基本操作与应用 栈是一种后进先出（LIFO）的数据结构，就像一叠盘子，最后放上去的盘子总是最先被拿走。栈的主要操作包括压入（push）和弹出（pop），此外还有一个重要的操作是窥视（peek）。 - **窥视操作（Peek）**：窥视操作允许我们查看栈顶元素的值，而不将其从栈中移除。通过多次按下窥视按钮，栈顶元素的值会被复制到数字文本字段中，但栈本身保持不变。需要注意的是，我们只能窥视栈顶元素，其他元素对栈的使用者是不可见的。 - **栈的大小**：栈通常是小型的临时数据结构，示例中展示的栈只有10个单元格。但在实际程序中，栈可能需要更多的空间。令人惊讶的是，即使是非常长的算术表达式，也可以用只有十几个单元格的栈来解析。 #### 栈的Java代码实现 以下是一个使用Java实现栈的示例代码： ```java // stack.java // demonstrates stacks // to run this program: C>java StackApp //////////////////////////////////////////////////////////////// class StackX { private int maxSize; // size of stack array private long[] stackArray; private int top; // top of stack //-------------------------------------------------------------- public StackX(int s) // constructor { maxSize = s; // set array size stackArray = new long[maxSize]; // create array top = -1; // no items yet } //-------------------------------------------------------------- public void push(long j) // put item on top of stack { stackArray[++top] = j; // increment top, insert item } //-------------------------------------------------------------- public long pop() // take item from top of stack { return stackArray[top--]; // access item, decrement top } //-------------------------------------------------------------- public long peek() // peek at top of stack { return stackArray[top]; } //-------------------------------------------------------------- public boolean isEmpty() // true if stack is empty { return (top == -1); } //-------------------------------------------------------------- public boolean isFull() // true if stack is full { return (top == maxSize-1); } //-------------------------------------------------------------- } // end class StackX //////////////////////////////////////////////////////////////// class StackApp { public static void main(String[] args) { StackX theStack = new StackX(10); // make new stack theStack.push(20); // push items onto stack theStack.push(40); theStack.push(60); theStack.push(80); while( !theStack.isEmpty() ) // until it’s empty, { // delete item from stack long value = theStack.pop(); System.out.print(value); // display it System.out.print(" "); } // end while System.out.println(""); } // end main() } // end class StackApp //////////////////////////////////////////////////////////////// ``` 上述代码中，`StackX`类实现了栈的基本操作，`StackApp`类的`main`方法创建了一个可以容纳10个元素的栈，将4个元素压入栈中，然后依次弹出并显示这些元素。输出结果为： ``` 80 60 40 20 ``` 可以看到，数据的顺序被反转了，这是因为栈的后进先出特性。 #### StackX类的方法分析 - **构造函数**：创建一个指定大小的新栈，栈的字段包括一个存储最大大小的变量、栈数组本身以及一个存储栈顶元素索引的变量`top`。 - **push方法**：将`top`指针加1，使其指向原栈顶元素上方的空间，然后将数据项存储在该位置。注意，`top`在插入元素之前先进行了递增。 - **pop方法**：返回栈顶元素的值，然后将`top`指针减1，从而有效地将元素从栈中移除。虽然该元素的值仍然存在于数组中，但由于`top`指针的移动，它变得不可访问。 - **peek方法**：简单地返回栈顶元素的值，不改变栈的状态。 - **isEmpty和isFull方法**：分别用于判断栈是否为空或已满。当`top`为 -1 时，栈为空；当`top`为`maxSize - 1`时，栈已满。 #### 错误处理 在处理栈错误时，有不同的哲学。如果尝试向已满的栈中压入元素或从空栈中弹出元素，会发生错误。在示例代码中，将处理这些错误的责任交给了类的使用者。使用者在插入元素之前应该始终检查栈是否已满： ```java if( !theStack.isFull() ) insert(item); else System.out.print("Can’t insert, stack is full"); ``` 在`main`方法中，为了简单起见，省略了这段代码，但在调用`pop`方法时会检查栈是否为空。许多栈类会在`push`和`pop`方法内部检查这些错误，这是更推荐的做法。在Java中，当栈类发现这些错误时，一个好的解决方案是抛出异常，然后由类的使用者捕获并处理。 #### 栈的应用示例 - **反转单词**：使用栈可以很方便地反转一个单词。程序会要求用户输入一个单词，按下回车键后，会显示该单词的反转形式。具体实现步骤如下： 1. 从输入字符串中逐个提取字符，并将其压入栈中。 2. 从栈中弹出字符并显示。由于栈的后进先出特性，字符的顺序被反转。 以下是实现该功能的Java代码： ```java // reverse.java // stack used to reverse a string // to run this program: C>java ReverseApp import java.io.*; // for I/O //////////////////////////////////////////////////////////////// class StackX { private int maxSize; private char[] stackArray; private int top; //-------------------------------------------------------------- public StackX(int max) // constructor { maxSize = max; stackArray = new char[maxSize]; top = -1; } //-------------------------------------------------------------- public void push(char j) // put item on top of stack { stackArray[++top] = j; } //-------------------------------------------------------------- public char pop() // take item from top of stack { return stackArray[top--]; } //-------------------------------------------------------------- public char peek() // peek at top of stack { return stackArray[top]; } //-------------------------------------------------------------- public boolean isEmpty() // true if stack is empty { return (top == -1); } //-------------------------------------------------------------- } // end class StackX //////////////////////////////////////////////////////////////// class Reverser { private String input; // input string private String output; // output string //-------------------------------------------------------------- public Reverser(String in) // constructor { inpu ```