栈
简单介绍一下数据结构中的栈.栈是什么呢?通俗的打个比喻.栈就是有一个死胡同,胡同宽度是只能容一个人进入的宽度,这时候小明进去了,走到了胡同的最里面,小明就到了栈底,然后小东又进来了就到了这种状况.
这个时候假如小明想出来的话,由于前面有小东挡着,他就出不来,所以,只能小东先出来,小明再出来.
栈是属于 后进先出 的,新进来的可以最先出去,如果这时候小云再进来的话,栈就如图所示
这时候小东和小明在小云不出来的前提下,是出不来的,小明如果想出来,必须让小云先出来,小东再出去,小明才可以出来. 符合后进先出的原则.
只要一个人(元素)前面还有其他的人(元素),他就不能被弹出,小云进入胡同是属于PUSH(压入)栈,小云出胡同是属于POP(弹出)栈.
相关实现的代码,我都用JAVA来写.
下面上一波代码吧
首先是栈的接口
package com.utils.inter; public interface Stack { /*验证栈是否为空*/ public boolean isEmpty(); /*取出栈顶元素*/ public Object peek(); /*弹出栈顶元素*/ public Object pop(); /*向栈内压入一个元素*/ public void push(Object obj); }如果不知道什么是接口,好吧,个人的理解可能有所偏见,我就把我的理解说一下吧.
接口说白了就是,一个总体的东西,包含什么功能,举个例子吧.
一个车的接口,车会干啥?车可以跑吧,需要加油吧,可以加速吧.大多数的车都有这些功能,然而车和车是不一样的.
比如,一个外面的出租车,速度最大能到多少?有安全气囊这种东西吗?没有对吧,但是像玛拉莎蒂这种好车就有,我们只是把它所具备的大致功能写出来,说白了就是把功能写好,你再自己实现.
当你制作一辆车的时候,必须要考虑到,它要可以跑,要加油,可以加速. 具体可以跑多快,加油需要加多少是加满,那就要看你具体的零件怎么配置啦,不是我所关心的了.
可能我对接口的理解并不正确,本人就是个渣渣,凑合先看着吧,如果有了其他理解,随时改正.
下面是栈的具体实现代码
package com.utils.instan; public class ArrayStack implements com.utils.inter.Stack { /*用一个整型数组来模拟栈*/ int []stack = new int[5]; /*类似指针的一个玩意,一直指向栈顶元素,初始为-1*/ int index=-1; /*看此栈是否为空,空的话返回true,并在控制台打印一句话*/ public boolean isEmpty() { if(index==-1){ System.out.println("不好意思,栈空了"); return true;} else{ return false;} } /*得到栈顶元素,先看栈是否为空,为空的话肯定不能得到相应的元素了,所以返回null,否则返回栈顶元素*/ public Object peek() { if(isEmpty()) return null; else return stack[index]; } /*弹出栈顶元素,弹出前也要进行验证,如果栈内没有元素的话弹个锤子??有元素的话并返回栈顶元素,游标减一*/ public Object pop() { if(isEmpty()){ return null;} else{ int k = index; index-=1; return stack[k]; } } /*入栈操作,先判断栈是否满了,如果满了就创建一个新的数组,是之前数组的二倍. * 然后将之前数组中的元素复制到新的数组,然后再把stack指向新的 stack2 * 再向栈中添加元素 * 没满的话就直接将新元素压入栈内就好了 */ public void push(Object obj) { if(index==stack.length-1){ int stack2[]=new int[index*2]; for(int i = 0;i<stack.length;i++){ stack2[i]=stack[i]; } stack = stack2; index++; stack[index]=(int) obj; }else{ index++; stack[index]=(int) obj; } } <span style="white-space:pre"> </span>/*这里是进行测试,压入8个数据,然后依次弹出*/ public static void main(String[] args) { ArrayStack s = new ArrayStack(); for(int i = 0;i<8;i++){ s.push(i); } for(;!s.isEmpty();){ System.out.println("栈弹出:"+s.pop()); } } }
运行结果如下:
栈弹出:7 栈弹出:6 栈弹出:5 栈弹出:4 栈弹出:3 栈弹出:2 栈弹出:1 栈弹出:0 不好意思,栈空了
好啦,第一个栈的介绍就到这里啦,这是基于数组实现的栈,还有基于链表实现的栈,打算以后在写出来.
