R语言 ClickHouse 图像处理 ASP.NET webserver perl kubernetes plot uicollectionview jqgrid vue标签 css最后一个子元素 js空格符 ceb转换成pdf在线转换 docker查看所有容器 java 大文件上传 python线程 python教程 python下载安装教程 python开发环境 python函数参数 java程序实例 java中的接口 java的运行环境 java安装步骤 java绝对值 python教程视频 黑客攻防实战入门 内存修改器 梦幻西游手游助手 主板芯片组天梯图 华为交换机学习指南 编程之家 fastcgi 手机刷机助手 idea下载 人脸识别代码 Ivideo 答题器下载 一创智富通
当前位置: 首页 > 学习教程  > 编程语言

数据结构_栈

2020/9/19 13:32:17 文章标签:

栈(Stack)
特点:栈的最大特点就是后进先出(LIFO)。对于栈中的数据来说,所有操作都是在栈的顶部完成的,只可以查看栈顶部的元素,只能够向栈的顶部压⼊数据,也只能从栈的顶部弹出数据。

实现:利用一个单链表来实现栈的数据结构。而且,因为我们都只针对栈顶元素进行操作,所以借用单链表的头就能让所有栈的操作在 O(1) 的时间内完成。

class Node{
	int data;
	Node next;
	
	public Node(int data) {
		this.data = data;
	}
}
 
/**
 * 使用链表来实现栈
 * @author User
 *
 */
public class MyStack {
	Node top;
	
	/**
	 * 压栈
	 * @param data
	 */
	public void push(int data) {
		// 先把传入的数字构造成一个节点,因为是链表嘛!
		Node node = new Node(data);
		if(top == null) {
			top = node;
		}else {
			// 直接将新节点作为栈顶元素
			node.next = top;
			top = node;
		}
	}
	
	
	/**
	 * 出栈
	 * @return
	 */
	public int pop() {
		if(isEmpty()) {
			throw new RuntimeException("栈是空的!");
		}
		int data = top.data;
		top = top.next;
		return data;
	}
	
	
	/**
	 * 返回栈顶元素
	 * @return
	 */
	public int peek() {
		if(isEmpty()) {
			throw new RuntimeException("栈是空的!");
		}
		return top.data;
	}
	
	
	/**
	 * 栈中元素总数
	 * @return
	 */
	public int length() {
		if(top == null) {
			return 0;
		}
		Node temp = top;
		// 计数器
		int count = 0;
		while(temp != null) {
			temp = temp.next;
			count++;
		}
		
		return count;
	}
	
	
	/**
	 * 判空
	 * @return
	 */
	public boolean isEmpty() {
		return top == null;
	}
}
 
 

应用场景:在解决某个问题的时候,只要求关心最近一次的操作,并且在操作完成了之后,需要向前查找到更前一次的操作。

如果打算用一个数组外加一个指针来实现相似的效果,那么,一旦数组的长度发生了改变,哪怕只是在最后添加一个新的元素,时间复杂度都不再是 O(1),而且,空间复杂度也得不到优化。

注意:栈是许多 LeetCode 中等难度偏上的题目里面经常需要用到的数据结构,掌握好它是十分必要的。

例题分析一
LeetCode 第 20 题:https://leetcode-cn.com/problems/valid-parentheses/

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

class Solution {
    public boolean isValid(String s) {
        if(s == null || s.length() == 0){
            return true;
        }
        if(s.length() == 1){
            return false;
        }
        Stack<Character> stack = new Stack<Character>();
        char[] chas = s.toCharArray();
        for(char c : chas){
            if(c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }
            else if(c == ')'){
                if(stack.isEmpty() || stack.peek() != '('){
                    return false;
                }
                else{
                    stack.pop();
                }
            }
            else if(c == ']'){
                if(stack.isEmpty() || stack.peek() != '['){
                    return false;
                }
                else{
                    stack.pop();
                }
            }
            else{
                if(stack.isEmpty() || stack.peek() != '{'){
                    return false;
                }
                else{
                    stack.pop();
                }
            }
        }
        return stack.isEmpty();
    }
}

例题分析二:

LeetCode 第 739 题:根据每日气温列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

提示:气温列表 temperatures 长度的范围是 [1, 30000]。 

示例:给定一个数组 T 代表了未来几天里每天的温度值,要求返回一个新的数组 D,D 中的每个元素表示需要经过多少天才能等来温度的升高。

给定 T:[23, 25, 21, 19, 22, 26, 23]

返回 D:  [  1,   4,   2,   1,   1,   0,   0]

解题思路

第一个温度值是 23 摄氏度,它要经过 1 天才能等到温度的升高,也就是在第二天的时候,温度升高到 24 摄氏度,所以对应的结果是 1。接下来,从 25 度到下一次温度的升高需要等待 4 天的时间,那时温度会变为 26 度。

思路 :可以运用一个堆栈 stack 来快速地知道需要经过多少天就能等到温度升高。从头到尾扫描一遍给定的数组 T,如果当天的温度比堆栈 stack 顶端所记录的那天温度还要高,那么就能得到结果。

对于[23, 24, 25, 21, 19, 22, 26, 23]

对第一个温度 23 度,堆栈为空,把它的下标压入堆栈;

下一个温度 24 度,高于 23 度高,因此 23 度温度升高只需 1 天时间,把 23 度下标从堆栈里弹出,把 24 度下标压入;

同样,从 24 度只需要 1 天时间升高到 25 度;

21 度低于 25 度,直接把 21 度下标压入堆栈;

19 度低于 21 度,压入堆栈;

22 度高于 19 度,从 19 度升温只需 1 天,从 21 度升温需要 2 天;

由于堆栈里保存的是下标,能很快计算天数;

22 度低于 25 度,意味着尚未找到 25 度之后的升温,直接把 22 度下标压入堆栈顶端;

后面的温度与此同理。

该方法只需要对数组进行一次遍历,每个元素最多被压入和弹出堆栈一次,算法复杂度是 O(n)。

class Solution {
    public int[] dailyTemperatures(int[] T) {
        if(T == null){
            return null;
        }
        int[] res = new int[T.length];
        Stack<Integer> stack = new Stack<>();
        for(int i =0; i < T.length; i++){
            while(!stack.isEmpty() && T[i] > T[stack.peek()]){
                int index = stack.peek();
                stack.pop();
                res[index] = i - index;
            }
            stack.push(i);
        }
        return res;
    }
}

LeetCode224: 基本计算器

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -,非负整数和空格  。

示例 1:

输入: "1 + 1"
输出: 2
示例 2:

输入: " 2-1 + 2 "
输出: 3
示例 3:

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

思路:
先反转字符串
从后往前遍历:
如果为' ':continue
如果为数字:
    更新操作数的值,num = Math.pow(10, n) * (c - '0') + num;
    n ++;
     continue;
否则:
    如果操作数num不为0:入栈,重置指数值和操作数值为0
    如果为')':直接入栈
    如果为'(': 
        从栈中计算表达式的值
            
 


本文链接: http://www.dtmao.cc/news_show_200007.shtml

附件下载

上一篇:鼠标样式cursor

下一篇:类初始化和加载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?