-
压栈弹栈的判断
2020-03-22 16:35:471,2,3,4,5是栈的压入顺序,判断4,5,3,2,1和4,3,5,1,2是不是对应的一个弹出序列。 自己脑子里模拟栈来顺一遍的话很简单,可是今天我遇到了用代码实现这个判断,我变得十分无知… 当然,依旧是看讨论区大佬们的代码偷...大学的数据结构考试就有一道这样的题:
1,2,3,4,5是栈的压入顺序,判断4,5,3,2,1和4,3,5,1,2是不是对应的一个弹出序列。
自己脑子里模拟栈来顺一遍的话很简单,可是今天我遇到了用代码实现这个判断,我变得十分无知…
当然,依旧是看讨论区大佬们的代码偷学~
解决这个问题的思路就是:
压入顺序:pushA:1,2,3,4,5
弹出顺序: popA:4,5,3,2,1
1.引用一个真正的栈s来作为中介
2.把pushA的第一个元素放入栈,用这个元素比较pushA中的第一个元素,如果不相等,就把pushA中的元素继续压入栈;如果相等,就把该元素弹出。接着把popA的第二个元素进行比对,pushA 1 2 3 4 5 popA 4 栈操作 s.push(1) s.push(2) s.push(3) s.push(4);s.pop() 栈s中:1 2 3 4➡1 2 3
pushA 1 2 3 4 5 popA 5 栈操作 出栈 s.push(5);s.pop() 栈s中:1 2 3 5➡1 2 3
pushA 1 2 3 4 5 popA 3 栈操作 s.pop() 出栈 出栈 栈s中:1 2 3 ➡1 2
pushA 1 2 3 4 5 popA 2 栈操作 s.pop() 出栈 出栈 出栈 栈s中:1 2 ➡1
pushA 1 2 3 4 5 popA 1 栈操作 s.pop() 出栈 出栈 出栈 出栈 栈s中:1 ➡空
pushA 1 2 3 4 5 popA 4 5 3 2 1 栈操作 出栈 出栈 出栈 出栈 出栈 3.直到popA中元素全部比对结束,如果栈s已经为空,说明这是正确的顺序,如果栈不为空,说明这是错误的顺序。
public boolean IsPopOrder(int [] pushA,int [] popA) { if(pushA.length!=popA.length) return false; Stack<Integer> s=new Stack<Integer>(); int j=0; for(int i=0;i<popA.length;i++){ s.push(pushA[i]); while(j<popA.length&&popA[j]==s.peek()){ s.pop(); j++; } } return s.isEmpty()?true:false; }
-
JZ21 压栈弹栈
2021-01-05 00:56:03python2:list==[] instead of not list(python3) core code: j =0 for i in pushV: stack.append(i) while stack and stack[-1] == popV[j]: stack.pop() j +=1python2: list==[]
instead of
not list(python3)
core code:
j =0 for i in pushV: stack.append(i) while stack and stack[-1] == popV[j]: stack.pop() j +=1
-
Java数组实现压栈弹栈操作【基础版】
2020-06-23 16:13:15永远指向栈部元素2压栈2.1(1)和(2)本质上一样,注意分清楚是先自加1,在赋值2.2注意:所有的System.out.println()方法执行时,如果输出饮用的话,自动调用引用的toString()方法2.3完整压栈代码2.4测试结果3弹栈4...目录标题
要求:
1.栈可以存储java中的任何引用类型的数据
2.在这个栈中提供push方法模拟压栈(栈满了,要有提示信息)
3.在栈中提供给pop方法模拟弹栈。(栈空了。也要有提示信息)
4.编写测试程序,new 栈对象,调用push 和pop方法来模拟压栈弹栈的动作
5.假设栈的默认初始化容量是10,(请注意无参构造方法的编写方式)栈类:MyStcck
1定义属性
1.1定义Object类型一维数组
向栈当中存储元素,我们这里使用一维数组模拟。存到栈中,就表示存储到数组中
因为数组是我们学习java的第一个容器
为什么选择Object类型数据?因为这个栈可以存储java中任何引用类型的数据
new Animal()对象可以放进去,new person()对象也可以放进去。因为Animal和Person的超级父类就是Object
包括String也可以存储进去,因为String父类也是Objectprivate Object[] elements; //属性私有化
1.2栈帧,永远指向栈元素
那么这个默认称呼是指应该是多少。注意:最初的栈是空的,一个元素都没有 private int index = 0; //如果index采用0,表示栈帧指向了底部元素的上方 private int index = -1; //如果index采用1,表示栈帧指向了底部元素
private int index = -1;
2压栈
2.1(1)和(2)本质上一样,注意分清楚是先自加1,在赋值
(1)
this.index++; elements[index] = obj;
(2)
elements[++index] = obj
2.2注意:所有的System.out.println()方法执行时,如果输出引用的话,自动调用引用的toString()方法
//声明:所有的System.out.println()方法执行时,如果输出饮用的话,自动调用引用的toString()方法 System.out.println("压栈"+ obj + "成功,栈帧指向" + index);
2.3完整压栈代码
public void push(Object obj){ if(this.index >= this.elements.length - 1){ System.out.println("压栈失败,栈已满!"); } //程序能走到这里,说明栈没满 this.index++; elements[index] = obj; //以上两句可以写成elements[++index] = obj 先自加一后赋值 //再声明一次:所有的System.out.println()方法执行时,如果输出引用的话,自动调用引用的toString()方法 System.out.println("压栈"+ obj + "成功,栈帧指向" + index); }
2.4测试结果
3弹栈
public void pop(){ if(index <0){ System.out.println("弹栈失败,栈已空!"); return; } //程序能够执行到此处,说明栈没有空 System.out.print("弹栈" + elements[index] + "元素成功"); //栈帧向下移动一位 index--; System.out.println("栈帧指向" + index); }
4完整代码
4.1栈类
package com.power.Javase.array.homework; /* 要求: 1.栈可以存储java中的任何引用类型的数据 2。在这个栈中提供push方法模拟压栈(栈满了,要有提示信息) 3.在栈中提供给pop方法模拟贪占。(栈空了。也要有提示信息) 4。编写测试程序,new 站对象,调用push 和pop方法来模拟压栈弹栈的动作 5.假设栈的默认初始化容量是10,(请注意无参构造方法的编写方式) */ public class MyStcck { //向栈当中存储元素,我们这里使用一维数组模拟。存到栈中,就表示存储到数据中心 //因为数组是我们学习java的第一个容器 //为什么选择Object类型数据?因为这个站可以存储java中任何引用类型的数据 // new Animal()对象可以放进去,new person()对象也可以放进去。因为Animal和Person的超级父类就是Object //包括String也可以存储进去,因为String父类也是Object private Object[] elements; //属性私有化 //栈帧,永远指向栈部元素 //那么这个默认称呼是指应该是多少。注意:最初的栈是空的,一个元素都没有 //private int index = 0; //如果index采用0,表示栈帧指向了顶部元素的上方 //private int index = -1; //如果index采用1,表示栈帧指向了顶部元素 private int index = -1; public MyStcck() { //一维数组动态初始化 //栈的默认初始化容量是10 this.elements = new Object[10]; //给index动态初始化 this.index = -1; } /** * 压栈的方法 * * @param obj */ public void push(Object obj){ if(this.index >= this.elements.length - 1){ System.out.println("压栈失败,栈已满!"); } //程序能走到这里,说明栈没满 this.index++; elements[index] = obj; //以上两句可以写成elements[++index] = obj 先自加一后赋值 //再声明一次:所有的System.out.println()方法执行时,如果输出饮用的话,自动调用引用的toString()方法 System.out.println("压栈"+ obj + "成功,栈帧指向" + index); } /** * 从数组中望外取元素 * 每去一个元素,栈帧减一 */ public void pop(){ if(index <0){ System.out.println("弹栈失败,栈已空!"); return; } //程序能够执行到此处,说明栈没有空 System.out.print("弹栈" + elements[index] + "元素成功"); //栈帧向下移动一位 index--; System.out.println("栈帧指向" + index); } //set和get也许用不上,但是你必须写上,这是规矩 //封装:第一步:属性私有化,第二步:对外提供setter和getter public Object[] getElements() { return elements; } public void setElements(Object[] elements) { this.elements = elements; } }
4.2测试类
package com.power.Javase.array.homework; public class MyStackTest { public static void main(String[] args) { //创建一个栈对象,初始化容量是10个 MyStcck stack = new MyStcck(); //调用方法压栈 stack.push(new Object()); stack.push(new Object()); stack.push(new Object()); stack.push(new Object()); stack.push(new Object()); stack.push(new Object()); stack.push(new Object()); stack.push(new Object()); stack.push(new Object()); stack.push(new Object()); //压这个元素失败了 //stack.push(new Object()); //System.out.println("================================"); stack.pop(); stack.pop(); stack.pop(); stack.pop(); stack.pop(); stack.pop(); stack.pop(); stack.pop(); stack.pop(); stack.pop();stack.pop(); } }
4.3执行结果
可以看出栈的特点,后进先出
-
java一维数组模拟压栈弹栈
2021-04-11 20:38:22java一维数组模拟入栈出栈弹栈 萌新代码,面向过程,勿喷,对栈内存理解不深! 希望一些对于此类作业烦恼的同级生有些许帮助,也可以在评论区提供帮助和修改以及错误的地方! import java.util.Scanner; public ...萌新代码,面向过程,勿喷,对栈内存理解不深!
希望一些对于此类作业烦恼的同级生有些许帮助,也可以在评论区提供帮助和修改以及错误的地方!
思路
先进后出,优先解决压栈的问题,之后解决弹栈和main方法
功能
1)随时模拟压栈
2)随时模拟弹栈
3)防止异常和各种错误
4)随时可以遍历“栈”中存在的变量的方法,压栈弹栈栈帧清晰可见!
使用演示:
压栈:
栈满检测:
遍历栈内存和栈帧:
只要栈中有变量就会输出栈帧:
弹栈:
栈空检测:(没有变量,栈帧不输出!)
源码:import java.util.Scanner; public class MoveTest01 { //局部变量供栈方法的遍历数组使用 static int i; //创建Object[]数组,作为栈,并且限制“内存上限”为5; static Object[] os = new Object[5]; //创建数组,模拟入栈 static num[] l = {new A(),new B(),new C(),new D(),new E(),new F()}; public static void main(String[] args) { int a =0;//遍历Object[]数组时的控制 boolean c = true;//控制循环 boolean d = true;//检测栈内存使用量防止异常 Scanner s = new Scanner(System.in); do { System.out.println("==========================="); System.out.print("请选择”压栈““弹栈”或“列出栈内存中储存的变量指向的方法”,输入“退出”将会结束程序!:"); String z = s.next(); //判定用户输入 if (z.equals("压栈")) { //防止数列超限 if(a > (os.length - 1)){ d = false; System.out.println("栈内存已满!请弹栈后压栈!"); } if(d){ //调用num[]数组模拟入栈 l[a].leng(); a++; } //防止if(d)锁死 d = true; } else if (z.equals("弹栈")) { //调用pop方法,模拟弹栈,并初始化计数 pop(); a = 0; i = 0; } else if (z.equals("退出")) { //结束do...while循环体 c = false; } else if (z.equals("列出栈内存中储存的变量指向的方法")) { int index = -1;//创建栈帧 if(os[0] == null){ System.out.println("栈内没有已装载的变量!"); } for (int k = os.length - 1; k > -1; k--) { //判定如果Object[]数组内的各个属性,如果不等于null则输出声明 if(!(os[k] == null)){ index++; System.out.println("栈内存中已入栈的变量的方法有:" + os[k]); } } //如果栈帧的值不为0,则输出结果 if(!(index == -1)){ System.out.println(os[index] + "《== 栈帧指向"); } } }while (c); } //模拟栈 public static void Zhan(Object o){ if(i < os.length) { //给Object[]数组赋值 os[i] = o; System.out.println("目标:" + os[i] + "的所有变量已压入栈内!"); i++; } } public static void push(String c){ //接收下面类传来的参数并赋值给Zhan() Zhan(c); } public static void pop(){ //检测数组第一位的值是不是空,如果是则输出消息 if(os[0] == null){ System.out.println("栈内没有已装载的变量!无法弹栈!"); } //模拟弹栈 for(int k = (os.length - 1);k >= 0;k--){ //遍历数组,将数组内不是null的值全部输出并初始化为null if(!(os[k] == null)) { System.out.println(os[k] + "的所有变量:已弹出内存!"); os[k] = null; } } } } class num{ public void leng(){ //让下面的方法有个共同的父类,并且调用时统一输出自己的名字给栈 MoveTest01.push(getClass().getName()); } } //即将入方法区的方法,假设里面有变量(也可以直接把这些方法看成变量); class A extends num{ public A() {} } class B extends num{ public B() {} } class C extends num{ public C() {} } class D extends num{ public D() {} } class E extends num{ public E() {} } class F extends num{ public F() {} }
-
栈的复习-用链表实现压栈弹栈
2020-06-30 13:21:19栈可以用顺序表和链表实现,在这里用链表实现最基本的入栈,弹栈操作。 代码 #include<iostream> #include<cstdlib> using namespace std; typedef struct data { int data; }datas; struct stack { ... -
用Java实现模拟压栈弹栈
2020-07-16 02:25:54//index为栈帧,index的数据表示当前栈中有多少个元素 //当index=objs.length-1的时候,表示栈中元素已满 //当index=0的时候,表示栈中元素为0个 //默认的栈空间为10个 public MyStack() { . -
顺序栈的功能实现(初始化,判空,压栈,弹栈,打印栈顶元素,批量手动输入元素压栈弹栈) ——以c语言为例
2020-11-03 19:16:44顺序栈特点:FILO(先进后出) 计算顺序栈的长度方法:length=s.top-s.base; 时间复杂度:O(1) #include <stdio.h> #include <iostream> using namespace std; #define sElemType int //预定义... -
用一维数组模拟栈数据结构的压栈弹栈
2020-03-08 12:01:44//创建栈类 用一维数组模拟栈数据结构 public class Stack { Object[] obj;//属性 栈,模拟栈的容量,由构造方法赋值容量大小。objec可以存储任何数据类型 int index;//模拟栈帧,栈帧等于obj容量时,表示栈满并... -
使用List集合实现 压栈 弹栈功能
2017-07-04 20:05:15* 压栈,,弹栈 * push,,pop * @author RayLu * */ public class StackDemo { @Test public void test1(){ Stack stack = new Stack(); stack.push("小明"); stack.push(new Date()); stack.push("小... -
数据结构-栈的动态顺序存储表示-初始化压栈弹栈
2017-09-17 12:56:56由于没有设置index参数,所以该code不能随时的输出,然后再继续进行push和pop,因为一次输出栈,就把top压到了bottom,可以通过增加index,进行恢复。 #include #include #define STACK_SIZE 100 #define ... -
数据结构-栈的静态顺序存储表示-初始化压栈弹栈
2017-09-19 21:56:10cout压栈1弹栈2显示3"; cin>>temp; if(temp==1) { int num; cin>>num; if(!insert_stack(num)) { cout插入失败"; } } else if(temp==2) { int num; if(pop_stack(&num)) ... -
再读C++ Primer 写了个小例子——实现stack类的压栈弹栈功能(08-12-10)
2008-03-19 22:01:00再读C++ Primer 写了个小例子——实现stack类的压栈弹栈功能#pragma once#define MAX 100template class T>class Stack...{public: Stack(void) ...{ top=0; total=0; } ~Stack(void) ...{} void -
使用一维数组,模拟栈数据结构。(压栈,弹栈)
2020-07-06 16:51:344、编写测试程序,new栈对象,调用push pop方法来模拟压栈弹栈的动作。 5.假设栈的默认初始化为10. public class MyStack{ // 栈类 // 提供一个数组来存储栈中的元素 Object[] elements; // 栈帧(永远... -
栈的压栈和栈的弹出序列
2021-03-16 00:40:42例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 示例 1: 输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出... -
【Java实现栈】压栈,弹栈,扩容,降容...
2021-03-11 11:06:47* @Description: 手动实现栈 压栈 弹栈 判空 判满 * * top=1 2 * top=-1 top=0 1 top=0 1 * @Author: juwei * @Date: 2021/3/1 19:12 * @Version: 1.0 * */ public class MyStack { private int top; -
Java中使用数组模拟栈的压栈和弹栈
2021-04-11 20:20:37Java中使用数组模拟栈的压栈和弹栈 栈stack的知识 栈是一种数据结构 压栈:将元素放入栈中 弹栈:将元素移除栈中 栈帧:指向栈顶元素 栈顶:栈最上面的那个元素 特点:先进后出,后进先出 Java实现 MyStack类 ... -
压栈,弹栈
2019-12-04 14:39:06* 弹出最后一个栈顶元素 * @return */ public int prop ( ) { if ( elements . length - 1 0 ) { throw new RuntimeException ( "元素为空" ) ; } //取出最后一个元素 int element...