目錄
- 簡介
- 棧的構成
- 棧的實作
- 使用數組來實作棧
- 使用動态數組來實作棧
- 使用連結清單來實作
棧應該是一種非常簡單并且非常有用的資料結構了。棧的特點就是先進後出FILO或者後進先出LIFO。
實際上很多虛拟機的結構都是棧。因為棧在實作函數調用中非常的有效。
今天我們一起來看學習一下棧的結構和用法。
棧一種有序的線性表，隻能在一端進行插入或者删除操作。這一端就叫做top端。
定義一個棧，我們需要實作兩種功能，一種是push也就是入棧，一種是pop也就是出棧。
當然我們也可以定義一些其他的輔助功能，比如top：擷取棧上最頂層的節點。isEmpty:判斷棧是否為空。isFull:判斷棧是否滿了之類。
先看下入棧的動畫：
再看下出棧的動畫：
具有這樣功能的棧是怎麼實作呢？
一般來說棧可以用數組實作，也可以用連結清單來實作。
如果使用數組來實作棧的話，我們可以使用數組的最後一個節點作為棧的head。這樣在push和pop棧的操作的時候，隻需要修改數組中的最後一個節點即可。
我們還需要一個topIndex來儲存最後一個節點的位置。
實作代碼如下：
public class ArrayStack {
//實際存儲資料的數組
private int[] array;
//stack的容量
private int capacity;
//stack頭部指針的位置
private int topIndex;
public ArrayStack(int capacity){
this.capacity= capacity;
array = new int[capacity];
//預設情況下topIndex是-1，表示stack是空
topIndex=-1;
}
/**
* stack 是否為空
* @return
*/
public boolean isEmpty(){
return topIndex == -1;
}
/**
* stack 是否滿了
* @return
*/
public boolean isFull(){
return topIndex == array.length -1 ;
}
public void push(int data){
if(isFull()){
System.out.println("Stack已經滿了，禁止插入");
}else{
array[++topIndex]=data;
}
}
public int pop(){
if(isEmpty()){
System.out.println("Stack是空的");
return -1;
}else{
return array[topIndex--];
}
}
}
上面的例子中，我們的數組大小是固定的。也就是說stack是有容量限制的。
如果我們想建構一個無限容量的棧應該怎麼做呢？
很簡單，在push的時候，如果棧滿了，我們将底層的數組進行擴容就可以了。
public void push(int data){
if(isFull()){
System.out.println("Stack已經滿了，stack擴容");
expandStack();
}
array[++topIndex]=data;
}
//擴容stack，這裡我們簡單的使用倍增方式
private void expandStack(){
int[] expandedArray = new int[capacity* 2];
System.arraycopy(array,0, expandedArray,0, capacity);
capacity= capacity*2;
array= expandedArray;
}
當然，擴容數組有很多種方式，這裡我們選擇的是倍增方式。
除了使用數組，我們還可以使用連結清單來建立棧。
使用連結清單的時候，我們隻需要對連結清單的head節點進行操作即可。插入和删除都是處理的head節點。
public class LinkedListStack {
private Node headNode;
class Node {
int data;
Node next;
//Node的構造函數
Node(int d) {
data = d;
}
}
public void push(int data){
if(headNode == null){
headNode= new Node(data);
}else{
Node newNode= new Node(data);
newNode.next= headNode;
headNode= newNode;
}
}
public int top(){
if(headNode ==null){
return -1;
}else{
return headNode.data;
}
}
public int pop(){
if(headNode ==null){
System.out.println("Stack是空的");
return -1;
}else{
int data= headNode.data;
headNode= headNode.next;
return data;
}
}
public boolean isEmpty(){
return headNode==null;
}
}
本文的代碼位址：
learn-algorithm
本文已收錄于 http://www.flydean.com/10-algorithm-stack/
最通俗的解讀，最深刻的幹貨，最簡潔的教程，衆多你不知道的小技巧等你來發現！
歡迎關注我的公衆号:「程式那些事」,懂技術，更懂你！