了解完算法的基本数据结构链表和数组后，我们就可以开始了解基于这些基本数据衍生出来的其它数据结构，如堆、栈、队列等，今天详细聊聊栈，其它文章参考
数组简介
链表简介
什么是栈栈是一种线性结构，最常见的生活中的例子就是羽毛球筒
羽毛球筒只开放一端入口，那么先放入的球一定是在底部，最后放入的球在最顶部，拿球时先获取的就是靠近顶部的球，只有不停的获取才能将底部的球拿到。
栈也就是这样，只能从一端入栈和出栈，这种顺序我们称为FILO（First In Last Out）先进后出，最早进入的元素称为栈底，最后进入的元素我们称为栈顶，如下
栈是链表和数组的基本数据的衍生结构，所以可以采用链表或者数据实现，具体思路如下
数组实现栈用数组来实现栈太简单，我们可以参考之前数组的相关文章
数组简介
入栈就是在数组的尾部插入元素不涉及到数组元素移动，出栈就是将数组尾部的元素清除，示意图如下
入栈
出栈
实现代码
/**
*用数组实现栈
*/
classMyStack1{
//数组的实际大小
privateintsize;
privateObject[]arr;
publicMyStack1(intcapacity){
arr=newObject[capacity];
size=0;
}
//入栈
publicvoidpush(Objectdata){
if(size==arr.length){
thrownewRuntimeException("超过栈的最大容量");
}
arr[size]=data;
size ;
}
//出栈
publicObjectpull(){
if(size==0){
thrownewRuntimeException("栈为空！");
}
Objectdata=arr[size-1];
//恢复数组指定位置默认值
arr[size-1]=null;
size--;
returndata;
}
publicvoidshow(){
System.out.println("打印栈存放数据：" Arrays.toString(arr));
}
}
链表实现栈同样是尾部指针的移动，如下是链表实现的示意图
入栈就是将原队尾的next指针指向新节点即可，而出栈就是将原队尾节点的上一个节点的next指针指向null。
入栈
出栈
实现代码如下
/**
*用链表实现栈
*/
classMyStack2{
//链表元素个数
privateintsize;
//头节点
privateNodehead;
//尾节点
privateNodelast;
//入栈
publicvoidpush(Objectdata){
Nodenode=newNode(data);
if(size==0){
head=node;
last=node;
}else{
last.next=node;
last=node;
}
size ;
}
//出栈
publicObjectpull(){
if(size==0){
thrownewRuntimeException("栈数据为空");
}
Objectdata=last.data;
if(size==1){
head=null;
last=null;
}else{
//获取倒数第二个节点
Nodeindex=getIndex(size-2);
index.next=null;
last=index;
}
size--;
returndata;
}
//获取指定下标的元素从0开始
publicNodegetIndex(intindex){
if(index<0||index>=size){
thrownewRuntimeException("数组下标异常");
}
Nodetemp=head;
for(inti=0;i<index;i ){
temp=temp.next;
}
returntemp;
}
publicvoidshow(){
Nodetemp=head;
while(temp!=null){
System.out.println(temp);
temp=temp.next;
}
}
}
classNode{
//数据
Objectdata;
//下一个节点指针
Nodenext;
publicNode(Objectdata){
this.data=data;
next=null;
}
@Override
publicStringtoString(){
return"Node{"
"data=" data
",next=" next
'}';
}
}
从操作代码可以看出，无论栈的实现方式是采用数组还是链表，入栈出栈都非常简单仅仅是一个元素的移动，所以入栈和出栈操作时间复杂度都为O(1)。
,
