数据结构：栈和队列的实现与应用

# 1. 引言

数据结构是计算机科学中非常重要的基础知识，它主要用来组织和存储数据，能够高效地进行增删改查等操作。栈和队列作为两种经典的数据结构，在实际开发中有着广泛的应用。

## 介绍数据结构的概念和重要性

数据结构是指数据元素之间的关系，以及对数据元素的操作方法的定义。它不仅是程序设计的基础，还能够直接影响到程序的效率和性能。了解和掌握各种数据结构，对提高程序的效率、减少资源的浪费以及更好地解决实际问题具有重要意义。

## 概述栈和队列的基本概念和特性

栈（Stack）和队列（Queue）是两种常见的抽象数据类型，它们在实际应用中有着不同的特点和作用。栈具有“先进后出”（FILO）的特性，而队列具有“先进先出”（FIFO）的特性。深入理解和掌握栈和队列对于实际问题的解决有着重要的意义。接下来我们将重点介绍栈和队列的定义、实现以及广泛应用。

# 2. 栈的实现与应用

栈是一种具有特殊性质的线性数据结构，它遵循后进先出（LIFO）的原则。栈主要有两个操作，即入栈（push）和出栈（pop）。入栈将元素压入栈顶，出栈则将栈顶元素弹出。

### 2.1 栈的定义和基本操作

栈可以通过数组或链表来实现。下面分别介绍两种常见的栈实现方式。

- **数组实现**

数组实现栈可以通过预留固定大小的数组，使用一个指针来表示栈顶的位置。当需要入栈时，将元素添加在栈顶并将指针向上移动，当需要出栈时，将栈顶元素弹出并将指针向下移动。

  class ArrayStack {
      private int maxSize;
      private int top;
      private int[] stack;
      public ArrayStack(int maxSize) {
          this.maxSize = maxSize;
          this.top = -1;
          this.stack = new int[maxSize];
      }
      public boolean isEmpty() {
          return top == -1;
      }
      public boolean isFull() {
          return top == maxSize - 1;
      }
      public void push(int value) {
          if (isFull()) {
              System.out.println("Stack is full");
              return;
          }
          stack[++top] = value;
      }
      public int pop() {
          if (isEmpty()) {
              throw new RuntimeException("Stack is empty");
          }
          return stack[top--];
      }
  }

在上述代码中，`maxSize`表示栈的最大容量，`top`表示栈顶的位置，`stack`是保存元素的数组。通过`isEmpty()`和`isFull()`方法判断栈是否为空或已满，`push()`方法将元素入栈，`pop()`方法将栈顶元素出栈。

- **链表实现**

链表实现栈可以使用带有头结点的单链表。每次入栈，则将新元素插入头结点后面，出栈则将头结点后面的元素删除。

  class Node {
      public int value;
      public Node next;
      public Node(int value) {
          this.value = value;
      }
  }
  class LinkedListStack {
      private Node head;
      public LinkedListStack() {
          this.head = new Node(-1);
      }
      public boolean isEmpty() {
          return head.next == null;
      }
      public void push(int value) {
          Node newNode = new Node(value);
          newNode.next = head.next;
          head.next = newNode;
      }
      public int pop() {
          if (isEmpty()) {
              throw new RuntimeException("Stack is empty");
          }
          Node topNode = head.next;
          head.next = topNode.next;
          return topNode.value;
      }
  }

在上述代码中，`head`是一个特殊的头结点，它的`next`指针指向栈顶的位置。通过`isEmpty()`方法判断栈是否为空，`push()`方法将元素入栈，`pop()`方法将栈顶元素出栈。

### 2.2 栈的应用案例

栈的一个常见应用是逆波兰表达式（后缀表达式）的计算。逆波兰表达式是一种不需要括号来表示操作符优先级的表达式，通过栈的特性可以方便地进行计算。

- **逆波兰表达式**

逆波兰表达式的操作符位于操作数的后面。例如，表达式`3 4 +`等价于中缀表达式`3 + 4`，结果为`7`。

  public int evalRPN(String[] tokens) {
      Stack<Integer> stack = new Stack<>();
      for (String token : tokens) {
          if (!"+-*/".contains(token)) {
              stack.push(Integer.parseInt(token));
          } else {