『数据结构与算法』栈

主页地址：/gozhuyinglong.github.io
源码分享：github.com/gozhuyinglong/blog-demos

栈又叫堆栈，是一种运算受限制的线性表，限定只能在一端进行插入和删除操作，该端称为栈顶（Top），相对的另一端叫栈底（Bottom）。

根据栈的定义可知，最先进入栈的元素在栈底，最后进入栈的元素在栈顶。而删除元素刚好相反，即删除顺序从栈顶到栈底

对栈的操作只有两种：

• 入栈（push）：又叫进栈或压栈，即向栈插入一条新的元素，该元素为新的栈顶元素。
• 出栈（pop）：又叫退栈，即从栈顶删除（取出）最后入栈的元素，而其相邻元素成为新的栈顶元素。

栈是一个先进后出（FILO - First In Last Out）的有序列表。在上图中描述了栈的模型，我们对栈的操作只有push和pop，栈顶元素是该栈唯一可见的元素。

由于栈是一个表，因此任何实现表的方法都能实现栈。显然我们之前用到的《 [数组]》和《 [链表]》都可以实现栈。下面代码是使用数组实现的一个栈。

size表示栈内元素的大小，栈顶元素为 elementData[size - 1]，栈底元素为 elementData[0]。入栈时执行 size++，出站时执行 size–

public class StackDemo {

    public static void main(String[] args) {

 System.out.println("-------------------入站");
 Stack stack = new Stack<>(10);
 stack.push("a");
 stack.push("b");
 stack.push("c");
 stack.push("d");
 stack.push("e");
 stack.print();

 System.out.println("元素大小: " + stack.size());
 System.out.println("栈容量: " + stack.capacity());

 System.out.println("-------------------出站");
 System.out.println("出站元素: " + stack.pop());
 System.out.println("出站元素: " + stack.pop());
 stack.print();
 System.out.println("元素大小: " + stack.size());
 System.out.println("栈容量: " + stack.capacity());
    }

    private static class Stack {
 private int size; // 元素大小
 private final int capacity; // 栈的容量
 transient Object[] elementData; // 元素数据

 public Stack(int capacity) {
     if (capacity <= 0) {
  throw new IllegalArgumentException("Illegal Capacity: " + capacity);
     } else {
  this.capacity = capacity;
  elementData = new Object[capacity];
     }
 }

 
 public int size() {
     return size;
 }

 
 public int capacity() {
     return capacity;
 }

 
 public boolean push(E e) {
     if (size >= capacity) {
  return false;
     }
     elementData[size++] = e;
     return true;
 }

 
 public E pop() {
     if (size <= 0) {
  return null;
     }
     return (E) elementData[--size];
 }

 
 public void print() {
     System.out.print("站内元素: ");
     for (int i = 0; i < size; i++) {
  System.out.printf("%st", elementData[i]);
     }
     System.out.println();
 }
    }
}

-------------------入站
站内元素: a	b	c	d	e	
元素大小: 5
栈容量: 10
-------------------出站
出站元素: e
出站元素: d
站内元素: a	b	c	
元素大小: 3
栈容量: 10

public class StackDemoBalancedChar {

    public static void main(String[] args) {

 BalancedChar balancedChar = new BalancedChar();
 String str = "[()][{}][][((()))]";
 boolean ok = balancedChar.isOk(str);
 System.out.printf("字符串：%st----> %s", str, ok);
    }

    private static class BalancedChar {
 private final char[] openArray = {'(', '[', '{'};  // 左括号
 private final char[] closeArray = {')', ']', '}'}; // 右括号

 
 public boolean isOk(String str) {
     // 使用 Java 自带的 Stack 类
     Stack stack = new Stack<>();

     boolean ok = true; // 判断字符串是否正确

     for (char c : str.toCharArray()) {

  // 若不是平衡符则忽略
  if (!isBalancedChar(c)) {
      continue;
  }

  // 如果是左括号，则入栈
  if (isOpen(c)) {
      stack.push(c);
      continue;
  }

  // 如果是右括号，而栈为空则报错
  if (stack.empty()) {
      ok = false;
      break;
  }
  // 如果是右括号，从栈中取出一个元素，并与当前元素判断是否是一对，若不是一对则报错
  Character open = stack.pop();
  if (!isTwain(open, c)) {
      ok = false;
  }
     }

     return ok && stack.empty();
 }

 
 public boolean isOpen(char c) {
     return inArray(openArray, c);
 }

 
 public boolean isClose(char c) {
     return inArray(closeArray, c);
 }

 
 public boolean isBalancedChar(char c) {
     return isOpen(c) || isClose(c);
 }

 
 public boolean inArray(char[] charArray, char c) {
     for (char c1 : charArray) {
  if (c1 == c) {
      return true;
  }
     }
     return false;
 }

 
 public boolean isTwain(char open, char close) {
     switch (open) {
  case '(':
      if (close == ')') {
   return true;
      }
  case '[':
      if (close == ']') {
   return true;
      }
  case '{':
      if (close == '}') {
   return true;
      }
  default:
      return false;
     }
 }

    }
}

字符串：[()][{}][][((()))]	----> true