数据结构学习—— 栈(stack)
- 什么是栈
- 无处不在的栈——栈的应用
- 使用数组实现ArrayStack及时间复杂度分析
- Leetcode20题:有效的括号
什么是栈(stack)
栈(stack)是一种运算受限的线性数据结构,运算受限指的是栈这种数据结构仅允许在一端添加元素,删除元素,这一端被称作栈顶,相对应的另一端则称为栈底。如图所示:
当前栈,如果想要添加元素“D”只能从栈顶部添加,从栈中取出元素则还是从栈顶开始取元素,所以栈是一种后进先出的数据结构即:LIFO(Last In First Out)。
无处不在的栈——栈的应用
一:Undo(撤销操作)
当我们在文档编辑器中输入文字,当发现输入错误时,想要撤销到前一步,这个操作就是Undo。撤销的原理实际上就是栈这种数据结构来设计实现的。例如:李雷在某个文档编辑器上输入文字“我爱韩梅梅”,结果,由于李雷满脑子想的都是韩梅梅的音容笑貌,不小心将内容输入成了“我爱含梅梅”。李雷想将内容恢复到“我爱” 这一步,所以他按了三次“Ctrl+z”,然后又依次将“韩”,“梅”,“梅”三个字输入了进去。
Undo(撤销)看似很高级的操作,背后的原理就是栈。
二:C语言printf()函数
来看一个C语言的问题:
#include<stdio.h>
int main(void){
int i=1;
printf("%d%d%d",i,i++,i++);
return 0;
}
复制代码
这个程序的运行结果是什么?如果只是知道i++与++i的区别是不足以解决这道问题的。先公布答案,这个程序的运行结果为:321,这与printf的底层原理有关,因为printf的底层实现就是栈。还是拿李雷韩梅梅来举例说明。
printf("我爱韩梅梅");
复制代码
printf函数首先会将字符串内容从右至左 push到栈中。
然后,再将栈里面的元素依次pop出来,这样我们就能看到"我爱韩梅梅"这个字符串被打印出来了。这道题也是一样,首先将最右边的%d即“i++” push到栈中,i==1,1入栈后,执行++操作,i的值变成了2。按照上述思路依次将所有元素推入栈中,栈的情况为:
将所有的元素出栈,出栈的顺序就是我们看到的打印结果即:321。
三:程序调用系统栈
有如下程序:
A();
function A(){
1 ...
2 B();
3 ...
4 end
}
function B(){
1 ...
2 C();
3 ...
4 end
}
function C(){
1 ...
2 ...
3 ...
4 end
}
复制代码
程序从A方法开始调用,执行到 A方法的第二行,计算机发现需要执行B方法,这时就会将执行到哪一步这样一个信息压入到系统栈中。例如,定义A2为A方法的第二行,计算机此时将A2压入系统栈,表明执行到了A方法的第二行。
计算机在系统栈压入这样一个信息后,开始执行B方法,执行到B方法的第二行,发现需要执行C方法,于是计算机将B2压入系统栈中。
计算机开始执行C方法,C方法中没有调用其他的函数,执行结束后,计算机发现系统栈中有残留的任务,于是pop stack 发现需要回去执行完B方法,且执行到了B方法的第二行。B方法执行完毕后,计算机又去看了看系统栈,发现仍有残留的任务需要执行,于是乎又 pop stack 发现原来A方法还没有执行完毕,且执行到了第二行,所以计算机又将A方法执行完毕。这时系统栈为空,计算机终于松了一口气,知道所有的任务已经执行完毕了~
使用数组实现ArrayStack及时间复杂度分析
本文中ArrayStack的底层实现数组为动态数组:动态数组,DobbyKim's Blog。
public interface Stack<E> {
void push(E e);
E pop();
E peek();
int getSize();
boolean isEmpty();
}
public class ArrayStack<E> implements Stack<E>{
Array<E> array;
public ArrayStack(int capacity){
array = new Array<>(capacity);
}
public ArrayStack(){
array = new Array<>();
}
public void push(E e){...}
public E pop(){...}
public int getSize(){...}
public int getCapacity(){...}
public boolean isEmpty(){...}
public E peek(){...}
public String toString(){...}
}
复制代码
点击查看源码
ArrayStack的方法push 与 pop 的均摊时间复杂度为O(1),因为这里面涉及到底层实现Array为动态数组,resize()扩容操作为一个O(n)的算法。getSize()方法,peek()方法,isEmpty()方法的时间复杂度均为O(1)。
Leetcode20题:有效的括号
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
- 示例 1:
输入: "()"
输出: true
复制代码
- 示例 2:
输入: "()[]{}"
输出: true
复制代码
- 示例 3:
输入: "(]"
输出: false
复制代码
- 示例 4:
输入: "([)]"
输出: false
复制代码
- 示例 5:
输入: "{[]}"
输出: true
复制代码
问题解决思路:栈。只要是左侧的括号为'(','[','{'就push到栈中,遇到与之匹配的右侧括号则pop,最后栈如果为空则说明匹配成功。Java代码如下:
import java.util.Stack
class Solution {
public boolean isValid(String s) {
Stack<Character>stack = new Stack<>();
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{'){
stack.push(s.charAt(i));
}else{
if(stack.isEmpty())
return false;
char c = stack.pop;
if(s.charAt(i)==')' && c!='(')
return false;
if(s.charAt(i)==']' && c!='[')
return false;
if(s.charAt(i)=='}' && c!='{')
return false;
}
}
return stack.isEmpty();
}
}
复制代码