当前位置:   article > 正文

【Java】轻松掌握栈的基本操作_java 栈

java 栈

1、栈的基本概念

如何理解栈

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

图片选自优课达官网

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

图片选自优课达官网

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

图片选自优课达官网

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


2、栈的实现

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

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

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

核心方法

首先我们需要理解栈中的三个核心方法:pushpoppeek

图片选自优课达官网

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];
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

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

栈的push方法

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

当栈为空的时候,top 为 -1 
当只有 1 个元素时,top 为 0 
当有 10 个元素时,top 为 9 
  • 1
  • 2
  • 3

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
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67

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

  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());
  	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

3、栈常见的算法题目

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

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

什么意思?

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

核心思路:

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

什么叫作配套?

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

我们来看两个例子

第一个例子

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

图片选自优课达官网

具体步骤如下:

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

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

第二个例子

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

图片选自优课达官网

1. 扫描到`{`,左括号压入栈中
2. 扫描到`(`,左括号压入栈中
3. 扫描到`(`,左括号压入栈中
4. 扫描到`}`,右括号与栈顶`(`匹配,匹配失败,停止操作
  • 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);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/611797
推荐阅读
相关标签
  

闽ICP备14008679号