数据结构——栈的实现（java实现）与相应的oj题

---

一 栈

栈的概念:

栈也是一种线性表，栈只允许在表的一端进行插入与删除操作，所以栈中数据的特征的先进后出（先进来的后出去）。
栈顶：是栈进行插入与删除操作的表的一端
栈底：不允许插入删除操作的一端
压栈：将数据插入到栈中
出栈：将数据移除栈

栈的实现：

栈的底层可以由数组实现，也可以由链表实现
栈由数组实现时，栈的压栈与出栈的时间复杂度均为O（1）。
栈由单链表实现时，
如果采用尾插法，压栈操作时间复杂度为O（n）,如果有last指针，则
压栈时间复杂度为O(1),但是出栈的时间复杂度一定为O（n）。
如果采用头插法，则压栈与出栈的时间复杂度均为O（1）.
栈由双链表实现时，不论采用头插法与尾插法，时间复杂度均为O(1)。

栈的数组实现

当栈使用数组实现时，栈的插入与删除操作，时间复杂度均为O（1）；

public class MyStack {static   int  DEFAULT_SIZE  = 10; //设置默认的数组大小private   int [] element ;        //实现栈的数组int usedsize = 0 ;                //栈中有效元素的个数//默认构造方法public MyStack() {}//入栈public void push(int val) {}//出栈public int pop() {}//获取栈顶元素 但是不删除public int peek() { }//获取栈元素个数public int size(){} //判空public boolean isEmpty() { }       
}

默认构造方法

默认申请10个空间

public MyStack(){this.element = new int[10];}

压栈

思想：先判断栈满没满，如果满了则扩容，然后进行压栈

  public void push(int data){//先判断栈是否有空间if(usedsize==element.length){//如果没有空间//则扩容this.element = Arrays.copyOf(element,2*element.length);}//保证空间后this.element[usedsize++] = data;}

获取栈元素的个数

思想：直接返回usedsize

 public int size(){return usedsize;}

出栈

思想：先判断栈是否为空，为空则抛出异常，不为空，则返回栈顶元素值，并且usedsize-1.

  public int pop(){//要判断栈是否为空，如果为空，则退出try{if (isEmpty()) {//2. 问题出现,构造参数的形参问题，super()调用父类的构造方法throw new EmptyException("EmptyException异常报错");}}catch (EmptyException e){e.printStackTrace();}int val =   this.element[usedsize-1];usedsize -- ;return val;}

获取栈顶元素

思想：与出栈逻辑相同，只是usedsize值不需-1 。

 public int  peek(){try{if (isEmpty()) {throw new EmptyException("EmptyException异常报错");}}catch (EmptyException e){e.printStackTrace();}return    this.element[usedsize-1];}

判断当前栈是否为空

思想：直接判断usedsize 是否为0即可。

 public boolean isEmpty(){return usedsize == 0;}

java提供的Stack类

Stack实现的接口：

  接口说明   1.  继承Cloneable接口支持克隆其他接口，暂时还没搞明白，以后更新补充

LinkedList也可以当Stack使用

java提供的LinkedList类也可以当做栈来使用，LinkedList的方法列表如下：

public class Test {public static void main(String[] args) {LinkedList<Integer> stack =  new LinkedList<>();stack.push(5);stack.push(2);stack.pop();stack.pop();stack.pop();}
}

虚拟机栈，栈帧，栈的三个概念

虚拟机栈是JVM中的一块内存。
栈帧是为一个方法，函数分配的内存。
栈是一种数据结构。

二 栈的一些算法题：

（1） 逆序打印单链表。

采用递归的方法：

// 递归方式
void printList(Node head){if(null != head){printList(head.next);System.out.print(head.val + " ");}
}

采用栈的方法：

void printList(Node head){if(null == head){return;}Stack<Node> s = new Stack<>();// 将链表中的结点保存在栈中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}
// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val + " ");}
}

（2）括号匹配

题解：1 . 对于这个题无法直接看出其数学模型，必须先画图，列出各种情况，再判断

从图中可以分析出，要实现判断括号匹配

1. 就要使得每一个左括号和右括号能够与对应位置的右括号进行匹配判断
2. 且当所有的左括号（右括号）判断完时，其对应的右括号（左括号）也判断完毕，即满足左括号个数与右括号个数相当的情况。
3. 如果第一个括号是右括号，说明此括号没有对应的左括号，说明一定为字符串一定括号不匹配。

实现思想：遍历字符串，遇到左括号则存入栈中，遇到右括号则与栈顶元素比较，相匹配，则继续循环，如果不匹配或栈为空，则返回false。

class Solution1 {public boolean isValid(String s) {Stack <Character> stack = new Stack<>();//采用for循环，这样可以找到字符串中的字符for(int i =0;i<s.length();i++) {char ch = s.charAt(i);if (ch == '{' || ch == '[' || ch == '(') {//问题，java提供的栈是否需要手动扩容？stack.push(ch);} else {//如果是右括号的内容if (stack.isEmpty()) {return false;} else {char ch2 = stack.peek();   //当获取栈顶元素时，栈可能为空//栈区不能为空if (((ch == '}' && ch2 == '{') || (ch == ']' && ch2 == '[') || (ch == ')' && ch2 == '('))) {//说明匹配，//将栈顶的元素去除stack.pop();} else {//如果不匹配，情况1 如果栈中还没有左括号，则一定不匹配，return false;}}}}// 如果栈表为空，说明匹配完毕if(stack.isEmpty()){return true;}return false;}
}

（3）逆波兰表达式求值

逆波兰表达式

逆波兰表达式即后缀表达式，后缀表达式是由中缀表达式转换而成。
所谓中缀表达式即我们平常所写的±*/的算式
我们平常所写的中缀表达式中是有优先级的，即先乘除，后加减，有括号先算括号里面的
但是计算机是不能够识别优先级的，为了能够使计算机计算，我们将中缀表达式的规则
表达成后缀表达式的形式，这样计算机便能够计算算式。

中缀表达式转换成后缀表达式的的规则：

1. 先将中缀表达式中能够加括号的部分都加上括号
2. 然后将所有的运算符移到所在 最近扩号之外。
3. 然后去除掉所有括号即得到后缀表达式。

后缀表达式的运算规则：
遍历整个表达式，遇到运算符时，则将运算符前面的两个数作为操作数计算
得出的结果替代两个操作数，然后继续遍历表达式，循环上次操作。

本题：只是要求按照后缀表达式的规则计算结果
实现思想：遍历表达式，遇到操作数即将操作数压入栈中，遇到运算符，则进行两次出栈
，获取两个操作数进行计算（需要注意的是第一次出栈的是右操作数，第二次出栈的是左操作数）
然后将计算的结果再进行压栈，然后循环此操作。

class Solution {public int evalRPN(String[] tokens) {//创建一个栈，创建栈时不需要考虑栈的空间大小Stack<Integer> stack = new Stack<>();//采用foreach进行遍历栈for (String str : tokens) {if (!isOperator(str)) {int a = Integer.parseInt(str);stack.push(a);} else {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.peek();}

总结
1. 字符串形式的运算符不能直接转换成运算符
2. 后缀表达式先进栈的是左操作数，后进栈的是右操作数，当我们需要出栈时，第一次获取栈顶元素是右操作数，第二次获取栈顶元素才是左操作数。

（4） 出入栈次序匹配

class Solution2{public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> stack = new Stack<>();int j = 0;for(int i = 0; i< pushV.length;i++) {stack.push(pushV[i]);while(!stack.empty() && j < popV.length &&stack.peek() == popV[j]) {stack.pop();j++;}}return stack.empty();}
}

（5）最小栈

题解：
如果只用一个栈的话，我们不可能实现题目的要求，只有能将栈的最小值时刻储存起来才能实现题目的要求。因此我们实现两个栈，一个栈用于存储数据，另一个最小栈用于存放栈当前的最小值。

实现思想：入栈的规则：

1. 普通栈一定要放，最小栈如果为空，或者栈顶元素小于压入的数据，则放入最小栈中
2. 如果压入的数据与最小栈栈顶元素相当，也放入最小栈中。（因为最小栈中的元素必须与普通栈的最小值保持同步即必须与出栈的规则相匹配）。
   出栈的规则：
   如果普通栈的栈顶元素与最小栈栈顶元素相同，则最小栈也需要出栈。

class MinStack {//创建两个栈Stack <Integer> stack  =  new Stack<>(); //普通栈Stack <Integer> minStack = new Stack<>();//最小栈public MinStack() {}
public void push(int val) {//压栈，压入数据//普通栈一定要压入stack.push(val);//然后判断最小栈是否压入if(minStack.empty()){minStack.push(val);}else{if(val<=minStack.peek()){minStack.push(val);}}}public void pop() {//出栈//普通栈一定出栈int val =  stack.pop();//最小栈出栈：//如果两栈的栈顶元素相同，则出栈if(val == minStack.peek()){minStack.pop();}}public int top() {//获取栈顶元素if(!stack.empty()){return stack.peek();}return -1 ;}public int getMin() {if(minStack.empty()){return -1;}return minStack.peek();}}

总结：

在使用栈时，最常用的运用是根据栈先进后出的特性，将一段有序的数据转为逆序后，再进行操作使用。