目錄
1、定義
2愧哟、實(shí)現(xiàn)
2.1 簡(jiǎn)單數(shù)組實(shí)現(xiàn)
2.1.1 代碼實(shí)現(xiàn)
2.1.2 性能和局限性
2.2 動(dòng)態(tài)數(shù)組實(shí)現(xiàn)
2.2.1 代碼實(shí)現(xiàn)
2.2.2 性能
2.3 鏈表實(shí)現(xiàn)
2.3.1 代碼實(shí)現(xiàn)
2.3.2 性能
2.4 基于數(shù)組實(shí)現(xiàn)和基于鏈表實(shí)現(xiàn)的比較
2.4.1 基于數(shù)組實(shí)現(xiàn)的棧
2.4.2 基于鏈表實(shí)現(xiàn)的棧
正文
1、定義
棧是一個(gè)有序線性鏈表鸵闪，只能在表的一端（稱(chēng)為棧頂梯皿，top）執(zhí)行插入和刪除主儡。
- 入棧（push），表示在棧中插入一個(gè)元素。
- 出棧（pop），表示從棧中刪除一個(gè)元素。
- 下溢（underflow），試圖對(duì)一個(gè)空棧執(zhí)行出棧操作。
-
溢出（overflow）吝羞，試圖對(duì)一個(gè)滿(mǎn)棧執(zhí)行入棧操作。
圖1-1 例子
2负懦、實(shí)現(xiàn)
有以下三種常見(jiàn)的實(shí)現(xiàn)方法：
- 基于簡(jiǎn)單數(shù)組的實(shí)現(xiàn)方法
- 基于動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)方法
- 基于鏈表的實(shí)現(xiàn)方法
2.1 簡(jiǎn)單數(shù)組實(shí)現(xiàn)
如下圖所示颗品，從左至右向數(shù)組添加所有元素槐臀，并定義一個(gè)變量來(lái)記錄數(shù)組當(dāng)前棧頂（top）元素的下標(biāo)。
圖2-1 簡(jiǎn)單數(shù)組實(shí)現(xiàn)
2.1.1 代碼實(shí)現(xiàn)
public class ArrayStack {
private int top;
private int capacity;
private int[] array;
//初始化
public ArrayStack(){
capacity=5;
array=new int[capacity];
top=-1;
}
//是否下溢
public boolean isEmpty(){
return (top==-1);
}
//是否溢出
public boolean isStackFull(){
return (top==capacity-1);
}
//入棧
public void push(int data){
if(isStackFull()){
System.out.print("溢出");
}else {
array[++top]=data;
}
}
//出棧
public int pop(){
if(isEmpty()){
System.out.print("下溢");
return 0;
}else {
return(array[top--]);
}
}
//大小
public int size(){
return capacity;
}
//銷(xiāo)毀
public void deleteStack(){
top=-1;
}
}
2.1.2 性能和局限性
-
性能：假設(shè)n為棧中元素的個(gè)數(shù)侮邀，下圖為各算法的時(shí)間復(fù)雜度。
圖2-2 性能 - 局限性：棧的最大空間必須預(yù)先聲明且不能改變题暖，試圖對(duì)一個(gè)滿(mǎn)棧執(zhí)行入棧操作將報(bào)溢出異常按傅。
2.2 動(dòng)態(tài)數(shù)組實(shí)現(xiàn)
上述存在的問(wèn)題是在固定大小的數(shù)組中捉超，如何處理所有空間都已經(jīng)保存了棧元素這種情況呢？可以使用重復(fù)倍增技術(shù)來(lái)提高性能唯绍，如果數(shù)組空間已滿(mǎn)拼岳，新建一個(gè)比原來(lái)數(shù)組空間大一倍的新數(shù)組，然后復(fù)制元素况芒。
2.2.1 代碼實(shí)現(xiàn)
public class DynArrayStack {
private int top;
private int capacity;
private int[] array;
//初始化
public DynArrayStack(){
capacity=5;
array=new int[capacity];
top=-1;
}
//是否下溢
public boolean isEmpty(){
return (top==-1);
}
//是否溢出
public boolean isStackFull(){
return (top==capacity-1);
}
//入棧
public void push(int data){
if(isStackFull()){
doubleStack();
}
array[++top]=data;
}
//出棧
public int pop(){
if(isEmpty()){
System.out.print("下溢");
return 0;
}else {
return(array[top--]);
}
}
//倍增
private void doubleStack(){
int newArray[]=new int[capacity*2];
System.arraycopy(array,0,newArray,0,capacity);
capacity=capacity*2;
array=newArray;
}
//銷(xiāo)毀
public void deleteStack(){
top=-1;
}
}
2.2.2 性能
假設(shè)n為棧中元素的個(gè)數(shù)惜纸，下圖為各算法的時(shí)間復(fù)雜度。
圖2-3 性能
2.3 鏈表實(shí)現(xiàn)
通過(guò)在鏈表的表頭插入元素的方式實(shí)現(xiàn)push操作绝骚，刪除鏈表的表頭結(jié)點(diǎn)（棧頂結(jié)點(diǎn)）實(shí)現(xiàn)pop操作耐版。
圖2-4 鏈表實(shí)現(xiàn)
2.3.1 代碼實(shí)現(xiàn)
public class LLStack {
private ListNode headNode;
//初始化
public LLStack(){
this.headNode=null;
}
//入棧
public void push(int data){
if(headNode==null){
headNode=new ListNode(data);
}else{
ListNode llNode=new ListNode(data);
llNode.setNext(headNode);
headNode=llNode;
}
}
//棧頂元素
public int top(){
if(headNode==null){
return -1;
}else {
return (headNode.getData());
}
}
//出棧
public int pop(){
if(headNode==null){
return -1;
}else {
int data=headNode.getData();
headNode=headNode.getNext();
return data;
}
}
//是否下溢
public boolean isEmpty(){
if(headNode==null){
return true;
}else {
return false;
}
}
//銷(xiāo)毀
public void deleteStack(){
headNode=null;
}
}
2.3.2 性能
假設(shè)n為棧中元素的個(gè)數(shù)，下圖為各算法的時(shí)間復(fù)雜度压汪。
圖2-5 性能
2.4 基于數(shù)組實(shí)現(xiàn)和基于鏈表實(shí)現(xiàn)的比較
2.4.1 基于數(shù)組實(shí)現(xiàn)的棧
- 各個(gè)操作都是常數(shù)時(shí)間的開(kāi)銷(xiāo)粪牲。
- 每隔一段時(shí)間倍增操作的開(kāi)銷(xiāo)較大。
- n個(gè)操作的任意序列的平攤時(shí)間開(kāi)銷(xiāo)為O(n)止剖。
2.4.2 基于鏈表實(shí)現(xiàn)的棧
- 棧規(guī)模的增加和減少都很簡(jiǎn)潔腺阳。
- 各個(gè)操作都是常數(shù)時(shí)間開(kāi)銷(xiāo)。
- 每個(gè)操作都需要使用額外的空間和時(shí)間開(kāi)銷(xiāo)來(lái)處理指針穿香。
