数据结构——栈的实现（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）括号匹配

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）最小栈

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();}}

总结：

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