五分钟“手撕”栈

实现代码放开头，供大家学习与查阅 

目录

一、实现代码

二、什么是栈

三、栈的常见操作

底层实现是链表。

入栈

出栈 

四、Stack的使用

五、栈的习题

第一题

第二题

第三题

第四题

第五题 

第六题 

第七题 

六、栈、虚拟机栈、栈帧的区别

---

目录

一、实现代码

二、什么是栈

三、栈的常见操作

底层实现是链表。

入栈

出栈 

四、Stack的使用

五、栈的习题

第一题

第二题

第三题

第四题

第五题 

第六题 

第七题 

六、栈、虚拟机栈、栈帧的区别

---

一、实现代码

package demo1;import java.util.Arrays;
import java.util.Stack;public class MyStack {int[] array;int size;public MyStack() {array = new int[3];}private void ensureCapacity() {if (array.length == size) {array = Arrays.copyOf(array, 2 * array.length);}}public int push(int e) {ensureCapacity();array[size++] = e;return e;}public int pop() {int i = peek();size--;return i;}public int peek() {if (empty()) {throw new RuntimeException("栈为空，无法获取栈顶元素");}return array[size - 1];}public int size() {return size;}public boolean empty() {return 0 == size;}
}

二、什么是栈

简单来说，先进后出的队伍！ 

堆叠这些元素的底部，我们叫栈底，顶部我们叫栈顶。 元素进入栈，叫入栈。元素离开栈，叫出栈。生活有很多类似于栈：

三、栈的常见操作

底层实现是链表。

入栈

只需要把节点添加到链表中的头节点即可。 

出栈 

只需要和删除链表的头节点即可

四、Stack的使用

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size()); // 获取栈中有效元素个数---> 4System.out.println(s.peek()); // 获取栈顶元素---> 4s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
if(s.empty()){System.out.println("栈空");
}else{System.out.println(s.size());}
}

五、栈的习题

第一题

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1 

答案选C，因为栈遵循先进后出。所以后面进来的数字可以先出去，

对于A：1入栈后出栈，就是4入栈后出栈（这里2和3已经入栈了，栈顶3），3出栈，2出栈

对于B：2入栈后出栈（这里1已经入栈了）3入栈后出栈，4入栈后出栈，1出栈

对于C：3入栈后出栈（这里1和2已经入栈，栈顶2）因为栈顶为2，只能出2，不能是1

对于D：3入栈后出栈（这里1和2已经入栈，栈顶2）4入栈后出栈。2出栈，1出栈 

第二题

2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺 序是（ ）。

A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA 

选B，依次进栈，栈底为1，栈顶为E，先出E，最后是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 + " ");
}
}

第四题

括号匹配

思路如下：

1.我们先new一个栈，来存放左括号，如果遇到右括号，就pop出来看看匹不匹配 

2.循环走完，如果栈刚好为空，则true；如果没走完循环，栈就空了，说明不匹配false。

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.empty()){return false;}char chL=Stack.peek();if(chL=='('&&ch==')'||chL=='{'&&ch=='}'||chL=='['&&ch==']'){Stack.pop();}else{return false;}}}return Stack.empty();}

第五题 

逆波兰表达式

什么是逆波兰表达式？

答：逆波兰表达式也叫后缀表达式，我们平常见的数学计算式比如10+（1-2）就是中缀表达式，它的后缀表达式为1012-+。

拓展：如何中缀转后缀？

思路如下：

new一个栈存放数字，如果遇到操作符就pop栈里面的两个数字出来，然后把操作后的数字再push到栈顶，最后pop出栈里面的最后一个数 

public int evalRPN(String[] tokens) {Stack<Integer> Stack = new Stack<>();for (int i = 0; i < tokens.length; i++) {if (!isOparation(tokens[i])) {Integer var = Integer.valueOf(tokens[i]);Stack.push(var);} else {Integer var2 = Stack.pop();Integer var1 = Stack.pop();switch (tokens[i]) {case "+":Stack.push(var1 + var2);break;case "-":Stack.push(var1 - var2);break;case "*":Stack.push(var1 * var2);break;case "/":Stack.push(var1 / var2);break;}}}return Stack.pop();}public boolean isOparation(String s) {if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {return true;}return false;}

第六题 

 出栈入栈顺序匹配

思路如下：

 new一个栈存放数据，

1.遍历pushV数组，每次入栈之后，判断是否和popV数组下标的数一致

2.不一样，继续i++；一样，出栈，j++

3.出栈的过程当中，如果一直是一样的，那么一直出，遇到不一样的，i++继续入栈

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

第七题 

最小栈

思路如下：

存放元素的过程：push（）

1.如果第一次存放元素，普通栈和最小栈都得存放

2.如果不是第一次存放的时候，普通栈肯定得放，但是最小栈我们需要和最小栈的栈顶元素比较，是否比最小栈的元素小或等于，只有小于等于才能放

取元素的过程： pop（）

1. 每次pop元素的是很好，都需要判断pop的元素是不是和最小栈的栈顶元素一样？

一样：最小栈也得pop。

top==》peek（）返回值是普通栈的值

getMIn（）获取最小栈的栈顶元素

import java.util.Stack;class MinStack {Stack<Integer> Stack;Stack<Integer> MinStack;public MinStack() {Stack = new Stack<>();MinStack = new Stack<>();}public void push(int val) {Stack.push(val);if (MinStack.empty()) {MinStack.push(val);} else {Integer peekVal=MinStack.peek();if (val <= MinStack.peek()) {MinStack.push(val);}}}public void pop() {if (Stack.empty()) {return;} else {int popVal=Stack.pop();if (popVal == MinStack.peek()) {MinStack.pop();}}}public int top() {if (Stack.empty()) {return -1;}return Stack.peek();}public int getMin() {if (MinStack.empty()) {return -1;}return MinStack.peek();}
}

六、栈、虚拟机栈、栈帧的区别

栈：先进后出的数据结构，这篇博客写的

虚拟机栈：存放局部变量的

栈帧：给方法开辟内存的 

参考书籍：《Hello！算法》