代做网站修改维护,上海哪家网站建得好,邯郸做网站就找安联网络,上海网站被查实现代码放开头#xff0c;供大家学习与查阅 目录
一、实现代码
二、什么是栈
三、栈的常见操作
底层实现是链表。
入栈
出栈
四、Stack的使用
五、栈的习题
第一题
第二题
第三题
第四题
第五题
第六题
第七题
六、栈、虚拟机栈、栈帧的区别 目录
一、… 实现代码放开头供大家学习与查阅 目录
一、实现代码
二、什么是栈
三、栈的常见操作
底层实现是链表。
入栈
出栈
四、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入栈并返回eE pop()将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中有效元素个数boolean empty()检测栈是否为空 public static void main(String[] args) {StackInteger 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因为栈遵循先进后出。所以后面进来的数字可以先出去 对于A1入栈后出栈就是4入栈后出栈这里2和3已经入栈了栈顶33出栈2出栈 对于B2入栈后出栈这里1已经入栈了3入栈后出栈4入栈后出栈1出栈 对于C3入栈后出栈这里1和2已经入栈栈顶2因为栈顶为2只能出2不能是1 对于D3入栈后出栈这里1和2已经入栈栈顶24入栈后出栈。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;
}StackNode 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) {StackCharacter Stacknew Stack();for(int i0;is.length();i){char chs.charAt(i);if(ch(||ch{||ch[){Stack.push(ch);}else{if(Stack.empty()){return false;}char chLStack.peek();if(chL(ch)||chL{ch}||chL[ch]){Stack.pop();}else{return false;}}}return Stack.empty();}
第五题
逆波兰表达式 什么是逆波兰表达式 答逆波兰表达式也叫后缀表达式我们平常见的数学计算式比如101-2就是中缀表达式它的后缀表达式为1012-。 拓展如何中缀转后缀 思路如下 new一个栈存放数字如果遇到操作符就pop栈里面的两个数字出来然后把操作后的数字再push到栈顶最后pop出栈里面的最后一个数 public int evalRPN(String[] tokens) {StackInteger 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 j0;StackInteger stacknew Stack();for(int i0;ipushV.length;i){stack.push(pushV[i]);while(jpopV.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 {StackInteger Stack;StackInteger 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 peekValMinStack.peek();if (val MinStack.peek()) {MinStack.push(val);}}}public void pop() {if (Stack.empty()) {return;} else {int popValStack.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算法》
