目录
1、定义
2、实现
2.1 简单数组实现
2.1.1 代码实现
2.1.2 性能和局限性
2.2 动态数组实现
2.2.1 代码实现
2.2.2 性能
2.3 链表实现
2.3.1 代码实现
2.3.2 性能
2.4 基于数组实现和基于链表实现的比较
2.4.1 基于数组实现的栈
2.4.2 基于链表实现的栈
正文
1、定义
栈是一个有序线性链表，只能在表的一端（称为栈顶，top）执行插入和删除。
- 入栈（push），表示在栈中插入一个元素。
- 出栈（pop），表示从栈中删除一个元素。
- 下溢（underflow），试图对一个空栈执行出栈操作。
-
溢出（overflow），试图对一个满栈执行入栈操作。
图1-1 例子
2、实现
有以下三种常见的实现方法：
- 基于简单数组的实现方法
- 基于动态数组的实现方法
- 基于链表的实现方法
2.1 简单数组实现
如下图所示，从左至右向数组添加所有元素，并定义一个变量来记录数组当前栈顶（top）元素的下标。
图2-1 简单数组实现
2.1.1 代码实现
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;
}
//销毁
public void deleteStack(){
top=-1;
}
}
2.1.2 性能和局限性
-
性能：假设n为栈中元素的个数，下图为各算法的时间复杂度。
图2-2 性能 - 局限性：栈的最大空间必须预先声明且不能改变，试图对一个满栈执行入栈操作将报溢出异常。
2.2 动态数组实现
上述存在的问题是在固定大小的数组中，如何处理所有空间都已经保存了栈元素这种情况呢？可以使用重复倍增技术来提高性能，如果数组空间已满，新建一个比原来数组空间大一倍的新数组，然后复制元素。
2.2.1 代码实现
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;
}
//销毁
public void deleteStack(){
top=-1;
}
}
2.2.2 性能
假设n为栈中元素的个数，下图为各算法的时间复杂度。
图2-3 性能
2.3 链表实现
通过在链表的表头插入元素的方式实现push操作，删除链表的表头结点（栈顶结点）实现pop操作。
图2-4 链表实现
2.3.1 代码实现
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;
}
}
//销毁
public void deleteStack(){
headNode=null;
}
}
2.3.2 性能
假设n为栈中元素的个数，下图为各算法的时间复杂度。
图2-5 性能
2.4 基于数组实现和基于链表实现的比较
2.4.1 基于数组实现的栈
- 各个操作都是常数时间的开销。
- 每隔一段时间倍增操作的开销较大。
- n个操作的任意序列的平摊时间开销为O(n)。
2.4.2 基于链表实现的栈
- 栈规模的增加和减少都很简洁。
- 各个操作都是常数时间开销。
- 每个操作都需要使用额外的空间和时间开销来处理指针。
