深入理解栈(Stack)
目录
1. 栈(Stack)之概念
首先明确:
栈是一种特殊的线性表,它特殊在只能在一端进行插入删除操作,并且最重要的是先进后出
(1)栈顶:进行数据插入和删除操作的一端
(2)栈顶:栈顶的另一端
(3)入栈:栈的插入操作,也叫做压栈/进栈,入数据在栈顶
(4)出站:栈的删除操作,出数据也在栈顶
下面理解一下,先进后出,看图解
分析一下,
1. 栈是先进后出的,那么入栈和出栈的时间复杂度是多少
因为入栈和出栈的数据都是在栈顶进行操作的 ,所以
入栈时间复杂度O(1) 出栈时间复杂度O(1)
2. 前面说的顺序存储的方式,那么栈的链式存储是什么样的
假设栈是以单向链表存储,那么插入数据有头插和尾插
(1)入栈是尾插法,那么时间复杂度就是O(N)
出栈,删除尾结点也是O(N)
(2)入栈是头插法,那么时间复杂度是O(1)从头结点插入不需要遍历链表
出栈,删除头结点就是O(1)
所以当栈的存储方式是链式时,并且是单链表,那么对比下来,
入栈就选头插法,出栈就删除头结点
3. 如果是以双向链表来看做栈,那么从哪里入哪里出
(1)从头入栈,从头出栈
(2)从尾入栈,从尾出栈
两种时间复杂度都是O(1)因为双向链表有头结点和尾结点,两边入栈出栈都一样
2. 栈(Stack)之模拟实现
栈继承了Vector,Vector和ArrayList类似,都是动态的顺序表,不过Vector的线程是安全的
先写一个栈
public int[] elem;
public int usedSize;
public static final int DEFAULT_CAPATI = 10;
public MyStack() {
elem = new int[DEFAULT_CAPATI];
}
1.入栈push()
入栈前先要判断栈是否满的isFull()
public boolean isFull() {
if (usedSize == elem.length) {
return true;
}
return false;
}
public void push(int val) {
//判断栈满
if (isFull()) {
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize] = val;
usedSize++;
}
2.删除栈顶元素pop()
删除栈顶元素前,先判断栈空isEmpty()
public boolean isEmpty() {
return usedSize == 0;
}
如果栈是空的,还要写一个异常EmptyStackException
public class EmptyStackException extends RuntimeException{
public EmptyStackException() {
}
public EmptyStackException(String msg) {
super(msg);
}
}
public int pop() {
if (isEmpty()) {
throw new EmptyStackException("栈是空的");
}
int oldVal = elem[usedSize-1];
usedSize--;
return oldVal;
}
3.获取栈顶元素,不删除peek()
public int peek() {
if (isEmpty()) {
throw new EmptyStackException("栈是空的");
}
return elem[usedSize-1];
}
4.获取中有效元素个数getUsedSize()
public int getUsedSize() {
return usedSize;
}
3. 栈(Stack)之使用
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(7);
System.out.println(stack.size());
System.out.println(stack.peek());
stack.pop();
System.out.println(stack.pop());
}
4.栈(Stack)之使用场景
4.1 改变元素的序列
(1)先看牛客上的一道题
分析一下 ,答案选C
(2) 若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()
A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1
分析一下,答案选C
2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈,则元素出栈的顺序是()。A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA
4.2 将递归转化为循环
写一个逆序打印链表
(1)递归
public class Demo01 {
static class Node{
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
public Node head;
public void printList(Node head) {
if (head == null) {
return;
}
if (head.next == null) {
System.out.print(head.val + " ");
return;
}
printList(head.next);
System.out.print(head.val + " ");
}
}
(2)非递归实现
既然栈是先进后出的,那么可以将数字依次放进去,然后再pop取出栈顶元素,打印出来,这不就实现了逆序打印
public void printList2(Node head) {
Stack<Node> stack = new Stack<>();
Node cur = head;
//将元素全部依次放入栈中
while(cur != null) {
stack.push(cur);
cur = cur.next;
}
//给栈pop取出栈顶元素然后拿出val打印
while(!stack.empty()) {
Node top = stack.pop();
System.out.println(top.val + " ");
}
}
4.3 括号匹配
题目要求
分析一下
上代码
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length(); i++ ) {
char ch = s.charAt(i);
if(ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
}else {
//此时ch 是右括号
//说明走到右边括号了
if(stack.empty()) {
//遇到有括号了,但是栈空了,说明1.右括号多
return false;
}
char top = stack.peek();
if(ch == ')' && top == '(' || ch == ']' && top == '[' || ch == '}' && top == '{') {
//说明当前字符是匹配的
stack.pop();
}else {
//2.左右括号不匹配
return false;
}
}
}
if(stack.empty()) {
return true;
}else {
//3.说明是左括号多
return false;
}
}
}
4.4 逆波兰表达式求值
链接 150. 逆波兰表达式求值 - 力扣(LeetCode)
在说这道题前先明白 逆波兰表达式又叫做后缀表达式
(1)后缀表达式又可以通过中缀表达式来转化出来(考研-选择题)
所以中缀变后缀三步走
(1)按规则加括号 (2)将运算符放括号外面 (3)去掉所有括号
(2)后缀表达式计算结果(代码题)
后缀计算4步走
(1)将数字按顺序依次放入栈中
(2)遇到运算符后,拿出栈顶两个元素
(3)按这样的规则计算( 次栈顶元素 运算符 栈顶元素 )
(4)将计算的结果,继续放入栈中,继续执行前面操作
好了,下面看一下这道题
根据前面的后缀计算4步走验证一下这个例子
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String x : tokens) {
if(!isOperation(x)) {
//不是加减乘除
//字符转成整数.放进栈中
stack.push(Integer.parseInt(x));
}else {
int num2 = stack.pop();
int num1 = stack.pop();
switch(x) {
case "+": stack.push(num1 + num2);
break;
case "-": stack.push(num1 - num2);
break;
case "*": stack.push(num1 * num2);
break;
case "/": stack.push(num1 / num2);
break;
}
}
}
return stack.pop();
}
private boolean isOperation(String opera) {
if(opera.equals("+") || opera.equals("-") || opera.equals("*") || opera.equals("/")) {
return true;
}
return false;
}
}
4.5 出栈入栈次序匹配
链接 栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
题目要求:
分析一下
上代码
import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0;
for(int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while(j <popA.length && !stack.empty() && stack.peek().equals(popA[j])) {
stack.pop();
j++;
}
}
return stack.empty();
}
}
相关文章
- 深入理解jquery新的绑定事件机制on方法的使用
- 深入理解并行编程-分割和同步设计(二)
- 深入理解JNI(《深入理解android》(author : 邓凡平)读书札记)
- 《深入理解Android2》读书笔记(四)
- 深入理解web
- 深入详解windows安全认证机制ntlm&Kerberos
- 深入理解C# 静态类与非静态类、静态成员的区别
- 深入理解Java反射+动态代理
- 转:深入理解Java G1垃圾收集器
- SAP UI5 应用开发教程之九十三 - 基于 JSONModel 数据模型的列表控件显示数据的深入讨论试读版
- 深入掌握 SAP Fiori Elements 工作原理的前提条件:理解 Smart Field
- DBMS/Database:数据库管理的简介、安装(注意事项等)、学习路线(基于SQLSever深入理解SQL命令语句综合篇《初级→中级→高级》/几十项代码案例集合)之详细攻略
- 深入理解java虚拟机读书笔记(三)
- 【精华文章】深入理解 Java 内存模型
- mysql的事务是什么 mybatis框架中的事务配置 mybatis中的自动提交事务和手动提交事务 深入理解mybatis事务源码 通过对象的地址来理解mysbaits中的会话 对象的首地址
- 深入理解JVM一性能监控工具
- 深入理解JVM一垃圾回收器
- vue中axios的深入使用
- 深入理解Java:注解(Annotation)自定义注解入门
- 分布式事务开山之作——《深入理解分布式事务:原理与实战》草图曝光!!
- 深入理解cookie与session
- PostgreSQL的学习心得和知识总结(九十六)|深入理解PostgreSQL数据库开源MPP扩展Citus 分片表隐藏及显示 的实现原理
- 深入剖析Android音频之AudioPolicyService
- [深入理解SSD 为SSD编程] SSD的架构和基准
- ADO.NET入门教程(八) 深入理解DataAdapter(上)
- 深入理解C#中的IDisposable接口
- 二十三、CANdelaStudio深入-SnapshotData编辑
- 深入理解css3中的flex-grow、flex-shrink、flex-basis