欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結(jié)構(gòu)與算法之棧(Stack)實現(xiàn)詳解

 更新時間：2017年09月12日 11:22:15   作者：Angel_Kitty  
這篇文章主要為大家詳細介紹了Java數(shù)據(jù)結(jié)構(gòu)學習筆記第二篇，Java數(shù)據(jù)結(jié)構(gòu)與算法之棧Stack實現(xiàn)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本篇是java數(shù)據(jù)結(jié)構(gòu)與算法的第2篇，從本篇開始我們將來了解棧的設計與實現(xiàn)，以下是本篇的相關(guān)知識點：

棧的抽象數(shù)據(jù)類型順序棧的設計與實現(xiàn)鏈式棧的設計與實現(xiàn)棧的應用

棧的抽象數(shù)據(jù)類型

  棧是一種用于存儲數(shù)據(jù)的簡單數(shù)據(jù)結(jié)構(gòu)，有點類似鏈表或者順序表（統(tǒng)稱線性表），棧與線性表的最大區(qū)別是數(shù)據(jù)的存取的操作，我們可以這樣認為棧(Stack)是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進行，一般而言，把允許操作的一端稱為棧頂(Top)，不可操作的一端稱為棧底(Bottom)，同時把插入元素的操作稱為入棧(Push),刪除元素的操作稱為出棧(Pop)。若棧中沒有任何元素，則稱為空棧，棧的結(jié)構(gòu)如下圖：

由圖我們可看成棧只能從棧頂存取元素，同時先進入的元素反而是后出，而棧頂永遠指向棧內(nèi)最頂部的元素。到此可以給出棧的正式定義：棧(Stack)是一種有序特殊的線性表，只能在表的一端(稱為棧頂，top，總是指向棧頂元素)執(zhí)行插入和刪除操作，最后插入的元素將第一個被刪除，因此棧也稱為后進先出(Last In First Out,LIFO)或先進后出(First In Last Out FILO)的線性表。棧的基本操作創(chuàng)建棧，判空，入棧，出棧，獲取棧頂元素等，注意棧不支持對指定位置進行刪除，插入，其接口Stack聲明如下：

/*
* 棧接口抽象數(shù)據(jù)類型
*/
public interface Stack<T> {

 /**
 * 棧是否為空
 * @return
 */
 boolean isEmpty();

 /**
 * data元素入棧
 * @param data
 */
 void push(T data);

 /**
 * 返回棧頂元素,未出棧
 * @return
 */
 T peek();

 /**
 * 出棧,返回棧頂元素,同時從棧中移除該元素
 * @return
 */
 T pop();
}

順序棧的設計與實現(xiàn)

  順序棧，顧名思義就是采用順序表實現(xiàn)的的棧，順序棧的內(nèi)部以順序表為基礎，實現(xiàn)對元素的存取操作，當然我們還可以采用內(nèi)部數(shù)組實現(xiàn)順序棧，在這里我們使用內(nèi)部數(shù)據(jù)組來實現(xiàn)棧，至于以順序表作為基礎的棧實現(xiàn)，將以源碼提供。這里先聲明一個順序棧其代碼如下，實現(xiàn)Stack和Serializable接口：

/* 
* 順序棧的實現(xiàn)
 */
public class SeqStack<T> implements Stack<T>,Serializable {

 private static final long serialVersionUID = -5413303117698554397L;

 /**
  * 棧頂指針,-1代表空棧
  */
 private int top=-1;

 /**
  * 容量大小默認為10
  */
 private int capacity=10;

 /**
  * 存放元素的數(shù)組
  */
 private T[] array;

 private int size;

 public SeqStack(int capacity){
  array = (T[]) new Object[capacity];
 }

 public SeqStack(){
  array= (T[]) new Object[this.capacity];
 }
 //.......省略其他代碼
}

其獲取棧頂元素值的peek操作過程如下圖（未刪除只獲取值）：

以上是獲取棧頂元素的操作，代碼如下：

/**
 * 獲取棧頂元素的值,不刪除
 * @return
 */
 @Override
 public T peek() {
  if(isEmpty())
   new EmptyStackException();
  return array[top];
 }

從棧添加元素的過程如下（更新棧頂top指向）：

以上是入棧操作，代碼如下：

/**
 * 添加元素,從棧頂(數(shù)組尾部)插入
 * 容量不足時，需要擴容
 * @param data
 */
@Override
public void push(T data) {
 //判斷容量是否充足
 if(array.length==size)
  ensureCapacity(size*2+1);//擴容

 //從棧頂添加元素
 array[++top]=data;
 }

棧彈出棧頂元素的過程如下（刪除并獲取值）：

以上是出棧操作，代碼如下：

/**
 * 從棧頂(順序表尾部)刪除
 * @return
 */
 @Override
 public T pop() {
  if(isEmpty())
   new EmptyStackException();
  size--;
  return array[top--];
 }

到此，順序棧的主要操作已實現(xiàn)完，是不是發(fā)現(xiàn)很簡單，確實如此，棧的主要操作就這樣，當然我們也可以通過前一篇介紹的MyArrayList作為基礎來實現(xiàn)順序棧，這個也比較簡單，后面也會提供帶代碼，這里就不過多啰嗦了。下面給出順序棧的整體實現(xiàn)代碼：

import java.io.Serializable;
import java.util.EmptyStackException;

/*
 * 順序棧的實現(xiàn)
 */
public class SeqStack<T> implements Stack<T>,Serializable {

 private static final long serialVersionUID = -5413303117698554397L;

 /**
  * 棧頂指針,-1代表空棧
  */
 private int top=-1;

 /**
  * 容量大小默認為10
  */
 private int capacity=10;

 /**
  * 存放元素的數(shù)組
  */
 private T[] array;

 private int size;

 public SeqStack(int capacity){
  array = (T[]) new Object[capacity];
 }

 public SeqStack(){
  array= (T[]) new Object[this.capacity];
 }

 public int size(){
  return size;
 }


 @Override
 public boolean isEmpty() {
  return this.top==-1;
 }

 /**
  * 添加元素,從棧頂(數(shù)組尾部)插入
  * @param data
  */
 @Override
 public void push(T data) {
  //判斷容量是否充足
  if(array.length==size)
   ensureCapacity(size*2+1);//擴容

  //從棧頂添加元素
  array[++top]=data;

  size++;
 }

 /**
  * 獲取棧頂元素的值,不刪除
  * @return
  */
 @Override
 public T peek() {
  if(isEmpty())
   new EmptyStackException();
  return array[top];
 }

 /**
  * 從棧頂(順序表尾部)刪除
  * @return
  */
 @Override
 public T pop() {
  if(isEmpty())
   new EmptyStackException();
  size--;
  return array[top--];
 }

 /**
  * 擴容的方法
  * @param capacity
  */
 public void ensureCapacity(int capacity) {
  //如果需要拓展的容量比現(xiàn)在數(shù)組的容量還小,則無需擴容
  if (capacity<size)
   return;

  T[] old = array;
  array = (T[]) new Object[capacity];
  //復制元素
  for (int i=0; i<size ; i++)
   array[i]=old[i];
 }

 public static void main(String[] args){
  SeqStack<String> s=new SeqStack<>();
  s.push("A");
  s.push("B");
  s.push("C");
  System.out.println("size->"+s.size());
  int l=s.size();//size 在減少,必須先記錄
  for (int i=0;i<l;i++){
   System.out.println("s.pop->"+s.pop());
  }

  System.out.println("s.peek->"+s.peek());
 }
}

鏈式棧的設計與實現(xiàn)

  了解完順序棧，我們接著來看看鏈式棧，所謂的鏈式棧（Linked Stack），就是采用鏈式存儲結(jié)構(gòu)的棧，由于我們操作的是棧頂一端，因此這里采用單鏈表（不帶頭結(jié)點）作為基礎，直接實現(xiàn)棧的添加，獲取，刪除等主要操作即可。其操作過程如下圖：

從圖可以看出，無論是插入還是刪除直接操作的是鏈表頭部也就是棧頂元素，因此我們只需要使用不帶頭結(jié)點的單鏈表即可。代碼實現(xiàn)如下，比較簡單，不過多分析了：

import com.zejian.structures.LinkedList.singleLinked.Node;

import java.io.Serializable;

/*
 * 棧的鏈式實現(xiàn)
 */
public class LinkedStack<T> implements Stack<T> ,Serializable{

 private static final long serialVersionUID = 1911829302658328353L;

 private Node<T> top;

 private int size;

 public LinkedStack(){
  this.top=new Node<>();
 }

 public int size(){
  return size;
 }


 @Override
 public boolean isEmpty() {
  return top==null || top.data==null;
 }

 @Override
 public void push(T data) {
  if (data==null){
   throw new StackException("data can\'t be null");
  }
  if(this.top==null){//調(diào)用pop()后top可能為null
   this.top=new Node<>(data);
  }else if(this.top.data==null){
   this.top.data=data;
  }else {
   Node<T> p=new Node<>(data,this.top);
   top=p;//更新棧頂
  }
  size++;
 }

 @Override
 public T peek() {
  if(isEmpty()){
   throw new EmptyStackException("Stack empty");
  }

  return top.data;
 }

 @Override
 public T pop() {
  if(isEmpty()){
   throw new EmptyStackException("Stack empty");
  }

  T data=top.data;
  top=top.next;
  size--;
  return data;
 }
 //測試
 public static void main(String[] args){
  LinkedStack<String> sl=new LinkedStack<>();
  sl.push("A");
  sl.push("B");
  sl.push("C");
  int length=sl.size();
  for (int i = 0; i < length; i++) {
   System.out.println("sl.pop->"+sl.pop());
  }
 }
}

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

相關(guān)文章

最新評論