对待就要来临的期中考试,感觉头好大,看书看不下去的时候就敲敲代码,换个口味,今天敲了一下栈,是用数组实现的,当然也可以用链表来实现。
栈的最大的特点就是“先进后出”,其实很像我们平时一起交作业,老师批改作业,越早交老师往往是最后才帮你改的,因为你的作业本被别人的作业本压在了下面嘛。但是也有喜欢好学生的老师,他会首先把成绩好的同学的作业或者卷子拿出来改,这样就不是栈的问题了,而是有一个优先级的考虑,也就是“优先级队列结构”。
栈在计算机系统中的作用很大。主要在两个方面。
1.函数的返回地址和参数
2. 临时变量:包括函数的非静态局部变量以及编译器自动生成的其他临时变量。
栈的原理图 :
由图可知:
1)从哪进就重哪里出去。
2)先进去的必定是最后才能出去的。
3)有一个东西指向了栈顶的元素。用来对栈中元素进行一些操作。而且总是指在栈顶的元素的。
代码实现。注释详细。
package 数组栈的实现; public class StackX { /* *棧的最大容量 */ private int maxSize; /* * 存放数据的数组 */ private long[] stackArray; /* * 指向栈顶元素的下标 */ private static int top; /* * 构造方法,生成一个数组并初始化栈数组的大小, * 并初始化指向顶部的下标。top = -1,表明栈 * 中还没有元素 */ public StackX(int maxSize) { top = -1; this.maxSize = maxSize; stackArray = new long[maxSize]; } /* * 向栈中压入一个元素 * top先上移一个位置,再在原来的下标处添加元素 * 为的是满栈的时候不会造成栈顶的元素被覆盖 */ public void push(long value) { stackArray[++top] = value; } /* * 弹出栈顶的元素,先弹出栈顶的元素 * 然后指向栈顶的top再往下移动一个下标, * 这样做的是为了当栈里面只有一个元素的时候 * 不会照成最后一个元素pop不出来,因为如果先移动 * 栈顶元素,top=-1了,这时默认已经为空了,而实际上 * 里面还有一个元素 */ public long pop() { return stackArray[top--]; } /* * 判断栈是否为空,当top==-1的时候,返回true */ public boolean isEmpty() { return top==-1; } /* * 判断栈是否满了,当top==(maxSize-1)的时候,返回true */ public boolean isFull() { return (top >(maxSize-1)); } /* * 查看栈顶的元素 */ public long peek() { return stackArray[top]; } public static void main(String[] args) { StackX stackX = new StackX(10); //没有压入元素的时候看看栈是不是空的 System.out.println("此时栈是不是空的? "+stackX.isEmpty()); //像栈里面压入元素,栈顶的元素应该是最后一个压入的 stackX.push(23); stackX.push(13); stackX.push(2); stackX.push(123); stackX.push(233); stackX.push(3); stackX.push(209); //查看栈顶的元素 System.out.println("查看栈顶的元素此时栈顶的元素应该为最后压入的那一个: "+stackX.peek()); //查看是否栈满了 System.out.println("此时栈满了没有? "+stackX.isFull()); //弹出两个试试 System.out.println("弹出两个元素:"); System.out.println("弹出的元素为: "+stackX.pop()); System.out.println("弹出的元素为: "+stackX.pop()); //再打印栈顶的元素 System.out.println("弹出两个元素后栈顶元素变为: "+stackX.peek()); } }
运行结果:
此时栈是不是空的? true 查看栈顶的元素此时栈顶的元素应该为最后压入的那一个: 209 此时栈满了没有? false 弹出两个元素: 弹出的元素为: 209 弹出的元素为: 3 弹出两个元素后栈顶元素变为: 233
再扯几句:其中需要注意的两个地方就是push()方法,向栈里面压入元素的时候,一定要是先在指向栈顶的top先向上移动一个位置之后再往里面压入(++top)。 这样做是为了当栈已经满了的时候,如果先压入再上移的话,就会把原来栈顶的元素给覆盖掉了。pop()弹出元素的时候和压入的时候相反,是先弹出了当前的元素,再往下移动top,相应的操作位(top--),这样是为了当里面只有一个元素的时候,如果是先移动,top指到了-1位置,这是默认为空了,这样最后一个元素就弹不出来了。用数组实现的时候还有一个问题就是开始就必须指定了栈的大小,这样在我们push()超过数组的最大容量的时候会有异常抛出,这个可以在操作前先进行判断,确定栈还没满的情况下再往里面压入元素。
相关推荐
分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法
c# 中数组的算法,c# 中数组的算法 c# 中数组的算法,c# 中数组的算法
插入排序算法(动态数组实现) printf("--------插入排序算法的实现--------\n"); printf("输入数组的大小length:\n"); int length=0; scanf("%d",&length); /****动态分配内存初始化数组*********************...
关于KMP算法中next数组的计算方法研究
对存放在数组中的数据 实现了快速查找算法 利用随机函数产生10000个随机数
用倍增算法对后缀数组的实现,其中用rmq实现询问两个后缀的最长前缀。
迷宫问题的求解算法,数据结构中的难点题目,用c语言实现的,源代码经过VC调式通过,没错误,用数组实现的。
使用C语言数组实现BOOTH算法。算法思想来源于计算机组成原理。可以参考 唐朔飞.[计算机组成原理](第2版)
使用数组实现的最佳置换算法。可选择物理块的个数。
用c++编写的程序,实现对栈的数组算法。。
堆排序 归并排序 选择排序 快速排序 插入排序 可选择数组初始状态(随机、正序、逆序) 通过输出的时间可以更好地比较在不同数组状态下 各种排序算法的时间复杂度
这个程序是应用数组来实现减法运算的,定义三个数组从而实现数组间的减法运算
3.请编写程序,利用冒泡算法实现对数组{25,24,12,76,101,96,28} 的排序。
用数据结构与算法 实现的数组 用一维数组定义用 二维数组 定义三维数组 用模版
在复习数据结构课程的过程中 对kmp算法及next数组的求解过程进行了深度探索 内含具体代码 及求解next数组的详解 望对大家有所帮助
自己写的分治算法,也包括了暴力求解的部分,并比较两者的运行时间,输出最大子数组的起始位置
通过二维数组实现,不是位操作,实现了一次迭代,东软的童鞋你们懂得...
用数组实现的类似栈功能的C语言后缀表达式算法