算法入门复习（算法入门之栈）

了解完算法的基本数据结构链表和数组后，我们就可以开始了解基于这些基本数据衍生出来的其它数据结构，如堆、栈、队列等，今天详细聊聊栈，其它文章参考

数组简介

链表简介

栈是一种线性结构，最常见的生活中的例子就是羽毛球筒

羽毛球筒只开放一端入口，那么先放入的球一定是在底部，最后放入的球在最顶部，拿球时先获取的就是靠近顶部的球，只有不停的获取才能将底部的球拿到。

栈也就是这样，只能从一端入栈和出栈，这种顺序我们称为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)。