- 一、理解栈
- 1. 栈的定义
- 2. 什么是 Java 虚拟机栈
- 3. 什么是栈帧
- 二、测试 Java 实现栈及其方法
- 测试一
- 测试二
- 三、通过顺序表实现自己的栈
- 创建一个类 Stack 表示栈中的情况
- 创建一个类 Test 用来测试对栈的操作
- 测试一
- 测试二
- 用什么结构实现栈最优?
- 四、通过OJ题深入理解栈
- 题目一 出栈的输出序列判断
- 题目二 栈的压入、弹出序列
- 题目三 中缀表达式 与 后缀表达式
- 题目四 有效的括号
- 题目五 最小栈
栈是限定仅在表尾进行插入和删除操作的线性表。
栈中的数据的特点:先进后出,后进先出。
在下图我们可以看到,我们只能对栈顶进行插入和操作,通俗的说,栈只能实现尾插尾删。
Java 虚拟机栈是 JVM 中的一块内存,该内存一般用来存放,局部变量等等…
3. 什么是栈帧调用函数的时候,我们会为这个函数开辟一块内存,叫做栈帧,而开辟内存的场所就在 Java 虚拟机栈 之中。
二、测试 Java 实现栈及其方法 测试一程序清单1:
//测试 push、pop、peek、isEmpty 方法
public class Test1 {
public static void main(String[] args) {
Stack stack = new Stack<>();
stack.push(1);
stack.push(3);
stack.push(5);
stack.push(7);
stack.push(9);
System.out.println(stack);
System.out.println(stack.pop()); //弹出栈顶的元素,并删除此元素
System.out.println(stack);
System.out.println(stack.peek()); //查看栈顶的元素,不删除此元素
System.out.println(stack.peek());
System.out.println(stack);
System.out.println(stack.isEmpty());
}
}
输出结果:
程序清单2:
//测试 search 方法
public class Test2 {
public static void main(String[] args) {
Stack stack = new Stack<>();
stack.push(1);
stack.push(3);
stack.push(9);
stack.push(7);
stack.push(9);
System.out.println(stack.search(9));
System.out.println(stack.search(3));
System.out.println(stack.search(2));
//search() 方法从栈顶开始找元素,
//如果找到栈顶第一个元素就返回1,找到第二个元素就返回2...
//找不到就返回-1
}
}
输出结果:
程序清单3:
import java.util.Arrays;
public class Stack{
public int[] elem;
public int usedSize;
public Stack() {
elem = new int[10];
}
//入栈
public void push(int data){
if(isFull() == true){
expansion();
}
elem[usedSize] = data;
usedSize++;
}
//判断栈是否已满
public boolean isFull(){
if(usedSize == elem.length){
return true;
}else {
return false;
}
}
//扩容
public void expansion(){
elem = Arrays.copyOf(elem,elem.length*2);
}
//移除栈顶的一个元素
public int pop(){
if(isEmpty() == true){
throw new RuntimeException("栈为空!");
}
int ret = elem[usedSize-1];
elem[usedSize-1] = 0;
usedSize--;
return ret;
}
//访问栈顶的一个元素
public int peek(){
if(isEmpty() == true){
throw new RuntimeException("栈为空!");
}
return elem[usedSize-1];
}
//判断栈是否为空
public boolean isEmpty(){
if(usedSize == 0){
return true;
}else {
return false;
}
}
//寻找栈中的某个元素
public int search(int findData){
int size = usedSize;
for (int i = usedSize - 1; i >= 0 ; i--) {
if(elem[i] == findData){
return size - i ;
}
}
return -1;
}
//打印栈中的所有元素
public void print(){
for (int i = 0; i < usedSize; i++) {
System.out.print(elem[i] + " ");
}
System.out.println();
}
}
创建一个类 Test 用来测试对栈的操作
测试一
程序清单4:
public class Test4 {
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(1);
stack.push(3);
stack.push(5);
stack.push(7);
stack.push(9);
stack.print();
System.out.println(stack.pop());
stack.print();
System.out.println(stack.peek());
System.out.println(stack.peek());
stack.print();
System.out.println(stack.isEmpty());
}
}
输出结果:
程序清单5:
public class Test5 {
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(1);
stack.push(3);
stack.push(9);
stack.push(7);
stack.push(9);
System.out.println(stack.search(9));
System.out.println(stack.search(3));
System.out.println(stack.search(2));
}
}
输出结果:
刚刚我们自己通过顺序表实现了栈的结构,那么,我们可以使用单链表实现栈的结构吗?
答:可以。但是,有区别。
通过顺序表(数组实现栈时),入栈和出栈的复杂度都为 O(1),因为我们只要考虑尾插、尾删即可,很方便就能对栈顶的元素进行直接操作。
但是,通过单链表实现栈时,当我们头插头删的时候,入栈和出栈的复杂度都为 O(1),而我们进行尾插尾删的时候,我们都要进行遍历链表,找到链表的最后一个节点,此时入栈和出栈的复杂度都为 O(n) 。
而我们通过双向链表实现栈时,不论是头插头删、尾插尾删,入栈和出栈的复杂度都为 O(1),因为双向链表某个节点总有前驱节点的地址。
- 一个栈的入栈顺序是 a b c d e,则栈不可能的输出序列是:( C )
A. e d c b a
B. d e c b a
C. d c e a b
D. a b c d e
一个数据可以入栈,也同时可以出栈,先入栈的数据可以事先出来,事先入栈的元素也可以最后出来。并且遵循先进后出原则。
题目二 栈的压入、弹出序列牛客网链接
程序清单6:
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack stack = new Stack<>();
int j = 0;
for(int i=0; i
stack.push( pushA[i] );
while( j
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}
思路:
① 理解 pushA 数组是压栈数组,popA 数组是出栈数组。
② 通过 for 循环遍历 pushA 数组,不断地往 stack 栈中放入数据,数据通过数组下标 i 记录。
③ 与此同时,通过 while 循环判断栈最顶部的数据是否与 popA 数组的 j 下相等,若相等,则执行出栈操作。
④ 返回的时候,若栈为空,那么就符合出栈的逻辑,反之,不符合数据结构的逻辑。
下图为两种情况,只要考虑到这两种情况,那么就能将此题做出来了。
这里,我们需要注意一下程序清单1中,while 循环的条件:
while( j其中一条就是栈中的数据不能为空,否则我们使用 stack.peek( ) 访问栈中数据时会抛出异常,因为我们猜想:栈在源代码中,就是通过数组实现的,如果数组长度为0,我们再去访问元素,这就会造成数组越界!下图是我通过 IDEA 验证出来的结果:
题目三 中缀表达式 与 后缀表达式其中后缀表达式又称为逆波兰表达式
leetcode 150
程序清单7:
class Solution { public int evalRPN(String[] tokens) { Stackstack = new Stack<>(); for(int i =0;i String val = tokens[i]; if(judge(val) == false){ int n = Integer.parseInt(val); stack.push(n); }else{ int num2 = stack.pop(); int num1 = stack.pop(); switch(val){ case "+": stack.push(num1 + num2); break; case "-": stack.push(num1 - num2); break; case "*": stack.push(num1 * num2); break; case "/": stack.push(num1 / num2); } } } return stack.pop(); } public boolean judge(String val){ if(val.equals("+") || val.equals("-") || val.equals("*") || val.equals("/")){ return true; }else{ return false; } } } 思路:
① 创建一个数组 tokens,里面都是字符串类型,表示我们需要操作的数据。
② 模拟一个栈 stack,准备用来存储整数。
③ 通过 for 循环遍历数组 tokens,并用 judge( ) 方法来判断每次拿到的是整数还是操作数 [ 加减乘除 ]。
④ 如果拿到的是整数,我们通过 stack.push( ) 方法进行入栈操作。
⑤ 如果拿到的是操作数,我们通过 stack.pop( ) 方法出栈操作,并使用栈顶的前两个整数进行数据运算。
⑥ 最终,我们 return 的值,也就是栈中最后一个值。下图为辅助理解:
题目四 有效的括号
leetcode 20
程序清单8:
class Solution { public boolean isValid(String s) { Stackstack = new Stack<>(); for(int i=0; i< s.length(); i++){ char ch = s.charAt(i); //如果遇到了左边的括号,那么就入栈 if(ch =='(' || ch =='{' || ch =='['){ stack.push(ch); }else{ //如果遇到了右边的括号,那么就判断栈顶元素 if(stack.isEmpty() == true){ return false; } char top = stack.peek(); //如果还未遍历完字符串,栈中已为空,也就是右括号多于左括号的情况,直接返回 false if(top == '(' && ch == ')' || top == '{' && ch == '}' || top == '[' && ch == ']'){ stack.pop(); }else{ return false; //如果左右括号不匹配,直接返回 false } } } //当遍历完字符串时,栈中还有元素,也就是左括号多于右括号的情况,直接返回 false if(stack.isEmpty() == false){ return false; } return true; } } 思路:
正常情况:
((( )))
([ ])考虑三种特殊情况
① ((( ))
当遍历完字符串时,栈中还有元素,也就是左括号多于右括号的情况,直接返回 false
② (( )))
如果还未遍历完字符串,栈中已为空,也就是右括号多于左括号的情况,直接返回 false
③ ([ )]
如果左右括号不匹配,直接返回 false分析图解:
题目五 最小栈
leetcode 155
程序清单9:
class MinStack { Stackstack = new Stack<>(); Stack minStack = new Stack<>(); public MinStack() { } public void push(int val) { int topVal = stack.push(val); //最小栈为空时,往最小栈放元素 if(minStack.isEmpty() == true){ minStack.push(topVal); }else{ //最小栈不为空,就要判断情况,如果普通栈的栈顶元素值>最小栈的栈顶元素值,那么就不往最小栈放元素 if(topVal <= minStack.peek()){ minStack.push(topVal); } } } public void pop() { int topVal = stack.pop(); //如果两个栈栈顶的元素是相同的,那么就删除最小栈的栈顶元素 if(topVal == minStack.peek()){ minStack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } } 思路:
创建两个栈,一个是普通栈 stack ,一个是最小栈 minStack,不管我们实现入栈操作,还是出栈操作,目的只有一个:最小栈的栈顶永远是最小的元素。因为在 getMin( ) 方法中,我们必须实现【 在常数时间内检索到最小元素的栈 】。
举例并分析图解:



