重走算法路之数组栈的实现

        对待就要来临的期中考试，感觉头好大，看书看不下去的时候就敲敲代码，换个口味，今天敲了一下栈，是用数组实现的，当然也可以用链表来实现。

       栈的最大的特点就是“先进后出”，其实很像我们平时一起交作业，老师批改作业，越早交老师往往是最后才帮你改的，因为你的作业本被别人的作业本压在了下面嘛。但是也有喜欢好学生的老师，他会首先把成绩好的同学的作业或者卷子拿出来改，这样就不是栈的问题了，而是有一个优先级的考虑，也就是“优先级队列结构”。

          栈在计算机系统中的作用很大。主要在两个方面。

  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()超过数组的最大容量的时候会有异常抛出，这个可以在操作前先进行判断，确定栈还没满的情况下再往里面压入元素。