棧---順序棧的實作

一、

（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]

[]