栈---顺序栈的实现

一、

（1）栈是在一种特殊的线性表，它代表只能在某一端进行插入、删除操作，通常在线性表的尾端进行插入、删除操作.

（2）对于栈而言，通常允许插入、删除操作的一端被称为栈顶（top），另一端被称为栈底（buttom）.

（3）从栈顶压入元素称为进栈（push）.

（4）从栈顶删除元素称为出栈（pop）.

栈是一种先进后出的线性表.

二、顺序栈的实现

   顺序栈就是顺序储存结构的栈，它利用一组地址连续的储存单元依次存放从从栈底到栈顶的元素。栈底的位置保持不变，栈顶元素可以直接通过顺序栈的底层数组的数组元素array[size-1]来访问。

   顺序栈中数据元素的物理关系和逻辑关系是一致的，先进栈的元素位于栈底。

   （1）进栈

       1）将新的数据元素存入栈内（需要判断栈是否已满）；

       2）让记录栈内元素个数的变量+1；

   （2）出栈

       1）让记录栈内元素个数的变量-1；

       2）释放数组对栈顶元素的引用；   

实现：

public class SquenceStack<T>
{
   private int DEFAULT_SIZE = 10;//数组初始化时的长度默认值
   private int capacity;//保存数组的长度容量
   private int capacityIncream;//
   private Object[] elementData;//指向数组的引用变量
   private int size;
   
   public SquenceStack()//顺序栈地无参构造器
   {
	   capacity = DEFAULT_SIZE;
	   elementData = new Object[capacity];
   }
   
 public  SquenceStack(T element)//以一个初始化元素来创建顺序栈
 {
  this();
  elementData[0]=element;
  size++;
 }
  public  SquenceStack(T element,int intSize)//以一个初始化元素和初始化长度来创建一个顺序栈
  {
     this.capacity = intSize;
     this.capacityIncream = intSize;
     elementData = new Object[capacity];
     elementData[0]=element;
     size++;
    }
  
  public int length()//返回顺序栈的大小
  {
	  return size++;
  }
  
  //入栈  把指定的元素压入栈中
  public void push(T element)
  {
	  ensureCapacity(size + 1);//压入前判断此时顺序栈是否已满，若满了进行扩容
	  elementData[size++] = element;
	 
  }
  
  //判断数组容量是否已满 若满的话就进行扩容
   private void ensureCapacity(int miniCapacity)
   {
	   if(capacity < miniCapacity) //如果容量已经满了
	   {
		  if (capacityIncream > 0)  //若顺序栈在创建时指定了其初始长度 那么每次扩大其指定长度的长度，直到容量大于传进来的数值
		{
			while(capacity < miniCapacity)
			{
				capacity += capacityIncream;
			}
		}
		 else  //如果创建时没有指定容量大小，则容量大小每次右移一位（是原来的两倍），直到容量值大于传进来的值
		  {
			  while (capacity < miniCapacity)
			{
				capacity <<= 1;
				
			}
		  }
	   }
   }
   
   //出栈  栈顶元素出栈
   public T pop()
   {
	   
	T oldValue = (T)elementData[size - 1];//把要出栈的元素赋值给oldValue
	   elementData[--size] = null;//把出栈的元素的引用指向空，释放栈顶元素的内存
	   return oldValue;
   }
   
   //返回栈顶元素但是不删除
   
  
  public T peek()
   {
	   return   (T)elementData[size - 1];
	  
   }
   
   //判断栈是否为空
   public boolean isEmpty()
   {
	  return size == 0;
   }
   
   //将栈清空
   public void clear()
   {
	   Arrays.fill(elementData,null);//将底层数组中所有引用都指向空
	   size = 0;
   }
   @Override
   public String toString()
   {
	   if (size == 0)
	   {
		return "[]";
	   }
	   else
	   {
		   StringBuilder sb = new StringBuilder("[");
		 
		   for (int i = size - 1; i >= 0; i--)
		   {
			   sb.append(elementData[i].toString() + ",");
			  
		   }
		   int len  = sb.length();
		   return sb.delete(len-1,len).append("]").toString();
		   
	   }
   }
}
           

测试：

public class SquenceStackTest
{
  public static void main(String[] args)
{
	SquenceStack<String> stack = new SquenceStack<String>();
	stack.push("hello");
	stack.push("world");
	stack.push("java");
    System.out.println("访问栈顶元素："+ stack.peek());
    System.out.println("栈中所有元素："+stack);
    stack.pop();
    System.out.println("出栈一个元素后栈中的元素："+stack);
    stack.clear();
    System.out.println(stack);
}
}
           

结果：

访问栈顶元素：java

栈中所有元素：[java,world,hello]

出栈一个元素后栈中的元素：[world,hello]

[]