轻松掌握栈的基本操作

• • • 1、栈的基本概念
    • 2、栈的实现
    • 3、栈常见的算法题目

1、栈的基本概念

如何理解栈

对于栈，首先列举一个生活案例，家里的厨房通常都放有很多盘子。每次洗好的盘子总是堆叠在一起，如图所示，ABC三个盘子：

我们在洗碗的时候，先洗好的放在下面，后洗好的放在上面

反过来每次使用盘子的时候，总是先拿上面的盘子，后拿下面的盘子

如果用专业术语表示，则为：后进先出、先进后出，这就是栈的特性

2、栈的实现

栈的使用场景非常广泛，所以在编程各类语言中都有栈的实现，例如在 Java 中，栈的数据结构类是：Stack

从栈的特性我们知道，它的本质是用于存储一批相同类型的数据，因此它的底层实现无非两种选择：数组和链表

兜兜转转，终究还是来到了我们擅长的领域（狗头）
链表的文章可以参考【Java】轻松掌握链表操作

核心方法

首先我们需要理解栈中的三个核心方法：push、pop、peek

push：往栈顶添加元素

pop：从栈顶移除元素

peek：获取栈顶元素，并不做任何添加删除操作

栈的所有操作都是基于栈顶进行的，这是它的特色。接下来，我们用Java数组实现一个栈

栈的初始化

首先考虑栈的初始化，为了先简单实现栈的功能，在此处只考虑存储字符串，并且不考虑栈的扩容问题

public class OrangeStack {
    String[] data;
    int size;
    
    // 初始化栈，默认大小为 20
    public OrangeStack () {
        this.initData(20);
    }
    
    // 初始化栈，并传入栈空间大小
    public OrangeStack (int size) {
        this.initData(size);
    }
    
    // 初始化数组
    private void initData(int size) {
        this.size = size;
        this.data = new String[this.size];
    }
}

代码中，支持创建一个默认空间为20的栈，也支持自定义空间的栈

栈的push方法

接下来实现 push 方法，在实现之前，需要先添加一个top变量记录栈顶在数组中的位置

当栈为空的时候，top 为 -1 
当只有 1 个元素时，top 为 0 
当有 10 个元素时，top 为 9 

push 的核心逻辑有 3 点：

1. 优先判断是否数组越界
2. 更改变量 top 的值
3. 往数组中添加一个元素

了解 push 方法后，pop、peek自然也变得游刃有余了，在这两个操作时，需要考虑栈为空的情况，若为空，返回 null 即可

用数组实现上面三个方法，代码如下：

public class OrangeStack {

  	String[] data;
  	int size;

  	// 栈顶位置
  	int top = -1;

  	// 初始化栈，默认大小为20
  	public OrangeStack() {
    	this.initData(20);
  	}

  	// 初始化栈，并传入栈空间大小
  	public OrangeStack(int size) {
    	this.initData(size);
  	}

  	// 初始化数组
  	private void initData(int size) {
    	this.size = size;
    	this.data = new String[this.size];
  	}

  	// 添加元素
  	public boolean push(String value) {
    	// 数组越界了
    	if (this.top >= this.size - 1) {
      		return false;
    	}

    	// top 栈顶 +1
    	this.top++;
    	// 设置栈顶元素
    	this.data[this.top] = value;
    	return true;
  	}

  	// 弹出栈顶元素
  	public String pop() {
    	if (this.top == -1) {
      		return null;
    	}
    	String item = this.data[this.top];
    	this.top--;
    	return item;
  	}

  	// 获取栈顶元素
  	public String peek() {
    	if (this.top == -1) {
    	  	return null;
    	}
    	return this.data[this.top];
  	}

  	public static void main(String[] args) {
    	OrangeStack stack = new OrangeStack();
    	System.out.println(stack.peek());
    	System.out.println(stack.pop());
    	stack.push("hello");
    	System.out.println(stack.peek());
    	stack.push("you");
    	System.out.println(stack.pop());
    	System.out.println(stack.peek());
  	}
}

若用链表实现，实现过程与数组实现的差异如下：

1. 链表不需要声明长度空间，链表本身具备无限扩容的能力
2. 链表应选用链表头作为栈顶元素的选择。因为链表头操作的时间复杂度为 O(1)，链表尾操作的时间复杂度为 O(N)，所以将链表头作为栈顶是最佳选择

代码如下：

public class OrangeStack {

  	Node header;

  	public OrangeStack() {
  	}

  	// 添加元素
  	public boolean push(String value) {
    	if (this.header == null) {
      		// 当前为空的时候，添加header
      		this.header = new Node(value);
    	} else {
      		// 当前不为空的时候，构建一个新的头部节点
      		this.header = new Node(value, this.header);
    	}
    	return true;
  	}

  	// 弹出栈顶元素
  	public String pop() {
    	if (this.header == null) {
      		return null;
    	}
    	// 删除链表头部节点
    	Node node = this.header;
    	this.header = node.getNext();
    	node.setNext(null);
    	return node.getContent();
  	}

  	// 获取栈顶元素
  	public String peek() {
    	if(this.header == null){
      		return null;
    	}
    	return this.header.getContent();
  	}

  	public static void main(String[] args) {
    	OrangeStack stack = new OrangeStack();
    	System.out.println(stack.peek());
    	System.out.println(stack.pop());
    	stack.push("hello");
    	System.out.println(stack.peek());
    	stack.push("you");
    	System.out.println(stack.pop());
    	System.out.println(stack.peek());
  	}
}

3、栈常见的算法题目

接下来我们看一道栈的常见的算法题目：括号匹配

在运行 Java 代码的时候，运行工具会先帮我们进行语法校验，在语法校验中很重要的一步是 —— 判断括号是否匹配

什么意思？

简单来说，有左括号就应该有右括号，有开即有合

核心思路：

当遇到左括号 (、{、[，则压入栈中，当遇到右括号 )、}、]，将此右括号和栈顶括号进行匹配。如果配套，则将栈顶元素弹出，否则括号不匹配

什么叫作配套？

()、{}、[] 属于配套的括号，其他组合就属于不配套

我们来看两个例子

第一个例子

查看字符串 ()({()}) 括号匹配情况，示意图如下：

具体步骤如下：

1. 扫描到`(`，左括号压入栈中
2. 扫描到`)`，右括号与栈顶`(`匹配，执行`pop`操作
3. 扫描到`(`，左括号压入栈中
4. 扫描到`{`，左括号压入栈中
5. 扫描到`(`，左括号压入栈中
6. 扫描到`)`，右括号与栈顶`(`匹配，执行`pop`操作
7. 扫描到`}`，右括号与栈顶`{`匹配，执行`pop`操作
8. 扫描到`)`，右括号与栈顶`(`匹配，执行`pop`操作

接下来验证一下 {((})) 这种错误的匹配案例

第二个例子

查看字符串 {((})) 括号匹配情况，示意图如下：

1. 扫描到`{`，左括号压入栈中
2. 扫描到`(`，左括号压入栈中
3. 扫描到`(`，左括号压入栈中
4. 扫描到`}`，右括号与栈顶`(`匹配，匹配失败，停止操作

注意上面的术语

压入栈中：指的是 Stack 中的 push 操作

弹出：指的是 Stack 中的 pop 操作

获取栈顶元素：指的是 Stack 中的 peek 操作

代码实现：

public class Demo {

    // 判断代码括号是否匹配
    public static boolean match(String code) {
        OrangeStack<Character> stack = new OrangeStack<>();
        for (int i = 0; i < code.length(); i++) {
            char c = code.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
                continue;
            }

            if (c == ')') {
                if (stack.peek() == '(') {
                    stack.pop();
                    continue;
                }
                return false;
            }

            if (c == '}') {
                if (stack.peek() == '{') {
                    stack.pop();
                    continue;
                }
                return false;
            }

            if (c == ']') {
                if (stack.peek() == '[') {
                    stack.pop();
                    continue;
                }
                return false;
            }
        }
        return stack.peek() == null;
    }

    public static void main(String[] args) {
        boolean result = match("()({()})");
        System.out.println("()({()}): " + result);

        result = match("{((}))");
        System.out.println("{((})): " + result);
    }
}