《恋上数据结构第1季》动态数组实现栈

简介: 《恋上数据结构第1季》动态数组实现栈

我的《恋上数据结构》源码(第1季 + 第2季):https://github.com/szluyu99/Data_Structure_Note

栈是一种特殊的线性表,只能在一端进行操作
在这里插入图片描述

  • 往栈中添加元素的操作,一般叫做 push入栈

在这里插入图片描述

  • 从栈中移除元素的操作,一般叫做 pop出栈

(只能移除栈顶元素,也叫做:弹出栈顶元素)
在这里插入图片描述

  • 后进先出的原则,Last In First Out,LIFO

注意:这里说的 “栈” 与内存中的 “栈空间” 是两个不同的概念;

栈的应用 – 浏览器的前进和后退

在这里插入图片描述
类似的应用场景:软件的撤销(Undo)、恢复(Redo)功能

栈的接口设计

int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void push(E element); // 入栈
E pop(); // 出栈
E top(); // 获取栈顶元素
void clear(); // 清空

栈的内部实现是否可以直接利用以前学过的数据结构?

  • 动态数组链表

动态数组实现栈

动态数组的知识:《恋上数据结构第1季》动态扩容数组原理及实现(Java、C++)

利用前面写的动态数组实现栈,极其简单;

package com.mj;

import com.mj.list.ArrayList;
import com.mj.list.List;

public class Stack <E> {

    private List<E> list = new ArrayList<>();
    
    public void clear(){
        list.clear();
    }
    
    public boolean isEmpty(){
        return list.isEmpty();
    }
    
    public void push(E element){
        list.add(element);
    }
    
    public E pop(){
        return list.remove(list.size() - 1); 
    }
    
    public E top(){
        return list.get(list.size() - 1);
    }
    
}

练习题

逆波兰表达式求值

150_逆波兰表达式求值:https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

在这里插入图片描述

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String string : tokens) {
            switch (string) {
            case "+":
                stack.push(stack.pop() + stack.pop());
                break;
            case "-":
                stack.push(-stack.pop() + stack.pop());
                break;
            case "*":
                stack.push(stack.pop() * stack.pop());
                break;
            case "/":
                Integer right = stack.pop();
                stack.push(stack.pop() / right);
                break;
            default:
                stack.push(Integer.parseInt(string));
                break;
            }
        }
        return stack.pop();
    }
}

有效的括号

在这里插入图片描述
解法1:

public boolean isValid(String s) {
    while(s.contains("{}") || s.contains("[]") || s.contains("()")){
        s.replace("{}", "");
        s.replace("[]", "");
        s.replace("()", "");
    }
    return s.isEmpty();
}

解法2:

public boolean isValid2(String s){
    Stack<Character> stack = new Stack<>();
    int len = s.length();
    for(int i = 0; i < len; i++){
        char c = s.charAt(i);
        if(c == '(' || c == '[' || c == '{'){ // 左括号
            stack.push(s.charAt(i)); // 左字符入栈
        }else{ // 右括号
            if(stack.isEmpty()) return false; // 没有左括号, 却匹配到了右括号,false
            
            char left = stack.pop();
            if(left == '(' && c != ')') return false; // 左右括号不匹配
            if(left == '[' && c != ']') return false; // 左右括号不匹配
            if(left == '{' && c != '}') return false; // 左右括号不匹配
        }
    } // 扫描完毕
    return stack.isEmpty();
}

解法3:

static HashMap<Character, Character> map = new HashMap<>();
static {
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');
}
public boolean isValid(String s){
    Stack<Character> stack = new Stack<>();
    int len = s.length();
    for(int i = 0; i < len; i++){
        char c = s.charAt(i); 
        if(map.containsKey(c)){ // 左括号,哈希表中有该键则入栈
            stack.push(c);
        }else{ // 右括号
            if(stack.isEmpty()) return false;
            char left = stack.pop();
            if(c != map.get(left)) return false;
        }
    }
    return stack.isEmpty();
}
相关文章
|
2天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
77 64
|
11天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
|
2天前
|
Go
数据结构之 - 深入了解栈数据结构
数据结构之 - 深入了解栈数据结构
12 5
|
11天前
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
|
11天前
|
前端开发
07_用队列实现栈
07_用队列实现栈
|
11天前
06_用栈来求解汉诺塔问题
06_用栈来求解汉诺塔问题
|
11天前
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
|
11天前
03_如何仅用递归函数和栈操作逆序一个栈
03_如何仅用递归函数和栈操作逆序一个栈
|
11天前
|
测试技术
02_由两个栈组成的队列
02_由两个栈组成的队列
|
15天前
|
存储