看動畫學算法之:棧stack
簡介
棧應該是一種非常簡單並且非常有用的數據結構了。棧的特點就是先進後出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;
}
}
本文的代碼地址：
本文已收錄於 //www.flydean.com/10-algorithm-stack/
最通俗的解讀，最深刻的乾貨，最簡潔的教程，眾多你不知道的小技巧等你來發現！
歡迎關注我的公眾號:「程序那些事」,懂技術，更懂你！
