文章目录
- 前言
- 1.什么是栈(Stack)?
- 2. 栈的模拟实现
- 3.stack的使用
- 4.关于栈的oj题
- 4.1.有效的括号
- 4.2.逆波兰表达式
- 4.3.栈的压入、弹出序列
- 4.4.最小栈
前言
前面几篇我们学习了顺序表以及链表的模拟使用，和一些oj题，下面我们学习两个比较特别的数据结构—栈和队列。
由于篇幅的限制，这一次，我们先学习栈。
1.什么是栈(Stack)?
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
栈在现实生活中的例子：
2. 栈的模拟实现
底层使用顺序表进行维护，以次实现下面功能。
public class MyStack {public int[] elem;public int useSize;public MyStack(){this.elem = new int[10];}public void push(int data){if (isFull()){this.elem = Arrays.copyOf(elem,2 * elem.length);}elem[useSize++] = data;}public boolean isFull(){return useSize == this.elem.length;}public int pop(){if (isEmpty()){throw new EmptyStackException();}int val = elem[useSize-1];useSize--;return val;}public int peek(){if (isEmpty()){throw new EmptyStackException();}return elem[useSize - 1];}public boolean isEmpty(){return useSize == 0;}
}
其主要逻辑跟顺序表的一模一样，可以先把之前顺序表的重新再看一遍，再过来看上述代码，就迎刃而解了。
3.stack的使用
public static void main(String[] args) {Stack<Integer> stack= new Stack();stack.push(1);stack.push(2);stack.push(3);stack.push(4);System.out.println(stack.size()); // 获取栈中有效元素个数---> 4System.out.println(stack.peek()); // 获取栈顶元素---> 4stack.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3System.out.println(stack.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3if(stack.empty()){System.out.println("栈空");}else{System.out.println(stack.size());}}
4.关于栈的oj题
4.1.有效的括号
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{if (stack.isEmpty()){return false;}char chr = stack.peek();if ((chr=='['&&ch ==']')||(chr == '('&& ch == ')')||(chr == '{')&&(ch == '}')){stack.pop();}else{return false;}}}if(!stack.isEmpty()) {return false;}return true; }
}
4.2.逆波兰表达式
首先要学习什么是逆波兰表达式，又称为后缀表达式，而波兰表达式，称为中缀表达式。
中缀表达式：有利于人们阅读与表达。
后缀表达式，有利于机器进行运算。
咱们举一个中缀表达式转化为后缀表达式的一个例子。
中缀表达式：a + b * c + ( d * e + f ) * g
后缀表达式：abc* + de* f + g* +
怎么进行转化的？
然后后缀表达式转化为中缀表达式，并且把值算出来，就是用栈来实现。
class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack();for (String str : tokens) {if (!operation(str)) {int x = Integer.parseInt(str);stack.push(x);} else {// 要注意 val1 和 val2 的位置int val2 = stack.pop();int val1 = stack.pop();switch (str) {case "+":stack.push(val1 + val2);break;case "-":stack.push(val1 - val2);break;case "*":stack.push(val1 * val2);break;case "/":stack.push(val1 / val2);break;}}}return stack.pop();}public boolean operation(String str) {if (str.equals("+") || str.equals("-")|| str.equals("*") || str.equals("/")) {return true;}return false;}
}
4.3.栈的压入、弹出序列
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack();int i = 0;int j = 0;while(i < pushV.length){stack.push(pushV[i]);while(j < popV.length&&!stack.empty()&&stack.peek() == popV[j]){stack.pop();j++;}i++;}return stack.empty();}
}
4.4.最小栈
class MinStack {public Stack<Integer> stack;public Stack<Integer> minstack;public MinStack() {stack = new Stack();minstack = new Stack();}public void push(int val) {stack.push(val);if (minstack.isEmpty()){minstack.push(val);}else{int peek = minstack.peek();if (val <= peek){minstack.push(val);}}}public void pop() {if (minstack.isEmpty()){return;}int popVal = stack.pop();if (popVal == minstack.peek()){minstack.pop();}}public int top() {if (stack.isEmpty()){return -1;}return stack.peek();}public int getMin() {if (minstack.isEmpty()){return -1;}return minstack.peek();}
}
下一篇我们学习队列的使用，我们不见不散！
