王道考研数据结构--5.顺序栈

**顺序栈**

顺序栈是一种线性表的抽象数据类型，它遵循先进先出（LIFO）的原则。也就是说，最后添加的元素将首先被移除。

###5.1 顺序栈的定义和基本操作**定义**

顺序栈是由一组元素组成的线性表，每个元素都有一个索引值（即其在栈中的位置），栈顶元素的索引值最大。栈底元素的索引值最小。

**基本操作**

1. **push(x)**：将元素x压入栈顶。
2. **pop()**：从栈顶弹出一个元素，返回该元素的值。如果栈为空，则抛出异常。
3. **peek()**：返回栈顶元素的值，但不移除该元素。若栈为空，则抛出异常。

###5.2 顺序栈的实现####5.2.1 使用数组实现顺序栈

javapublic class ArrayStack {
 private int[] elements;
 private int top;

 public ArrayStack(int capacity) {
 this.elements = new int[capacity];
 this.top = -1;
 }

 public void push(int x) {
 if (top == elements.length -1) {
 // 栈满了，需要扩容 int[] newElements = new int[elements.length *2];
 System.arraycopy(elements,0, newElements,0, elements.length);
 elements = newElements;
 }
 top++;
 elements[top] = x;
 }

 public int pop() {
 if (top == -1) {
 // 栈空了，抛出异常 throw new RuntimeException("Stack is empty");
 }
 int x = elements[top];
 elements[top--] =0; // 将栈顶元素置为0，以便GC回收 return x;
 }

 public int peek() {
 if (top == -1) {
 // 栈空了，抛出异常 throw new RuntimeException("Stack is empty");
 }
 return elements[top];
 }
}

javapublic class Node {
 int data;
 Node next;

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

public class LinkedListStack {
 private Node top;

 public void push(int x) {
 Node node = new Node(x);
 if (top == null) {
 top = node;
 } else {
 node.next = top;
 top = node;
 }
 }

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

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

javapublic class BracketMatcher {
 public boolean match(String s) {
 ArrayStack stack = new ArrayStack(s.length());
 for (int i =0; i < s.length(); i++) {
 char c = s.charAt(i);
 if (c == '(' || c == '[' || c == '{') {
 stack.push(c);
 } else if (c == ')' || c == ']' || c == '}') {
 if (stack.isEmpty()) {
 return false;
 }
 char top = stack.pop();
 if ((c == ')' && top != '(') ||
 (c == ']' && top != '[') ||
 (c == '}' && top != '{')) {
 return false;
 }
 }
 }
 return stack.isEmpty();
 }
}

javapublic class Calculator {
 public int evaluate(String s) {
 ArrayStack stack = new ArrayStack(s.length());
 for (int i =0; i < s.length(); i++) {
 char c = s.charAt(i);
 if (c == ' ') {
 continue;
 } else if (c >= '0' && c <= '9') {
 int num = c - '0';
 while (i +1 < s.length() && s.charAt(i +1) >= '0' && s.charAt(i +1) <= '9') {
 i++;
 num = num *10 + (s.charAt(i) - '0');
 }
 stack.push(num);
 } else if (c == '+' || c == '-' || c == '*' || c == '/') {
 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 '/':
 if (right ==0) {
 throw new RuntimeException("Division by zero");
 }
 stack.push(left / right);
 break;
 }
 } else {
 throw new RuntimeException("Invalid character");
 }
 }
 return stack.pop();
 }
}