Java中栈的实现(1)-使用顺序存储结构(数组)以及实现

栈和队列其实是与普通的线性发展而来的，为普通的线性表增加一些特殊的限制就可以得到栈和队列了。从功能上看，栈和队列比普通的线性表功能相对弱一点，但是在特殊的场合下，使用栈和队列更有利，例如，编译器在实现函数的调用的时候需要使用栈来存储断点，实现递归算法时候也需要用栈来存储。

栈：一种数据结构，代表只能从一端进行插入、删除操作的特殊线性表，通常情况下在栈的尾巴进行插入、删除操作。

对于栈而言，允许插入和删除操作的是栈顶(top)，另一端是栈底(bottom)。一个栈不包含任何元素的时候是一个空栈。从栈顶插入一个元素是进栈，将一个元素插入栈顶被称为“压入栈”----对应于英文(push)。从栈顶删除一个元素被称为出栈，将一个元素从栈顶删除被称为“弹出栈”----对应于英文(pop).

栈：就是一个后进先出(LIFO)线性表。

注意：栈是一个被限制的线性表，不提供从中间任何位置删除、插入、访问元素的方法。也就是说栈只能够在栈顶插入和删除元素。

栈来自与线性表，因此栈可以使用顺序表的方式来实现也可以使用链表的方式来实现。

本文是根据顺序表来实现栈的使用的语言是Java，下一篇文章中使用链表来实现栈

package com.wpl.stackimpl;

import java.util.Arrays;

public class StackImplByArray {
	
	private int DEFAULT_SIZE=10;
	//保存数组的长度
	private int capacity;
	//定义当数组容量不够的时候，每次增加多少
	private int capacityIncrement=0;
	//定义一个数组来保存栈的元素
	private Object[] elementData;
	//保存数序数组中个数
	private int size=0;
	//一个构造函数
	public StackImplByArray(){
		capacity=DEFAULT_SIZE;
		elementData=new Object[capacity];
		
	}
	
	//获取栈的大小
	public int getLength()
	{
		return size;
	}
	
	//入栈
	public void push(Object element){
		
		//可能要考虑到数组的大小是否合适
		elementData=arrayIsFull();
		elementData[size]=element;
		size++;
		
	}
	
	//出栈
	public Object pop(){
		if(size==0)
		{
			throw new NullPointerException("栈为空！");
		}
		
		Object popElement=elementData[size-1];
		elementData[size-1]=null;
		size=size-1;
		return popElement;
		
	}
	
	//来确定看看是否需要添加数组的大小
	//这种方法效率很低，而且很是麻烦哈
	public Object[] arrayIsFull()
	{
		
		//查看是否要吧数组的容积扩大的条件
		if(elementData.length<=size)
		{
			System.out.println("进来！");
			//每次递增的就是数组长度的一半
			capacityIncrement=elementData.length/2;
			capacity=elementData.length+capacityIncrement;			
			Object []tempArray=new Object[capacity];
			//注意使用copyOf的这个函数哈，参数不要使用有误哈！
			tempArray=Arrays.copyOf(elementData, capacity);
			elementData=new Object[capacity];
			elementData=tempArray;
			return elementData;
			
		}else{
			return elementData;
		}
		
		
	}
	
	
	public static void main(String[] args) {
		
		StackImplByArray test=new StackImplByArray();
		test.push(123);
		test.push("wang");
		test.push("test1");
		test.push("test2");
		test.push("test3");
		test.push("test4");
		test.push("test5");
		test.push("test6");
		test.push("test7");
		test.push("test8");
		test.push("test9");
		test.push("test10");
		test.push("test11");
		
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());		
		System.out.println(test.pop());
		
	}
}