栈生活中的栈----客栈存储货物或供旅客住宿的地方,可引申为仓库、中转站 。例如我们现在生活中的酒店在古时候叫客栈是供旅客休息的地方旅客可以进客栈休息休息完毕后就离开客栈。计算机中的栈:我们把生活中的栈的概念引入到计算机中就是供数据休息的地方它是一种数据结构数据既可以进入到栈中又可以从栈中出去。栈是一种基于先进后出(FILO)的数据结构是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据先进入的数据被压入栈底最后的数据在栈顶需要读数据的时候从栈顶开始弹出数据最后一个数据被第一个读出来。栈是一种基于先进后出(FILO)的数据结构first in last out我们称数据进入到栈的动作为压栈数据从栈中出去的动作为弹栈。栈代码实现数组实现链表实现数组实现:对于数组来说我们模拟栈的过程很简单因为栈是后进先出我们很容易在数组的末尾进行插入和删除。所以我们选定末尾为栈顶。所以对于一个栈所需要的基础元素是 一个data数组和一个top(int)做指针表示栈顶位置。push入栈如果top数组长度-1。入栈。top;a[top]value;如果top数组长度-1栈满。pop出栈并返回首位如果top0,栈不为空可以弹出。return data[top–];如下图本来栈为1234栈顶执行pop操作。top变为3的位置并且返回4代码实现:选定数组末尾为栈顶,设计top指针 指向栈顶元素publicclassStack01TimplementsIterableT{//数组privateTdata[];//top指针 指向栈顶元素privateinttop;publicStack01(){data(T[])newObject[10];top-1;}publicStack01(intmaxsize){data(T[])newObject[maxsize];top-1;}booleanisEmpty(){returntop-1;}intsize(){returntop1;}//入栈booleanpush(Tvalue)throwsException{if(top1data.length-1){thrownewException(栈已满);}else{data[top]value;returntrue;}}//返回栈顶元素不移除Tpeek()throwsException{if(!isEmpty()){returndata[top];}else{thrownewException(栈为空);}}//出栈Tpop()throwsException{if(isEmpty()){thrownewException(栈为空);}else{returndata[top--];}}OverridepublicIteratorTiterator(){returnnewStack01.SIterator();}privateclassSIteratorimplementsIterator{privateintcusor;publicSIterator(){this.cusortop;}OverridepublicbooleanhasNext(){returncusor0;}OverridepublicObjectnext(){if(top-1){returnnull;}returndata[cusor--];}}}测试publicclassStackTest01{publicstaticvoidmain(String[]args)throwsException{//创建栈对象Stack01StringstacknewStack01(12);//测试压栈stack.push(a);stack.push(b);stack.push(c);stack.push(d);for(Stringitem:stack){System.out.println(item);}System.out.println(------------------------------);//测试弹栈Stringresultstack.pop();System.out.println(弹出的元素是result);System.out.println(剩余的元素个数stack.size());}}链表实现:栈API设计push入栈单向链表头插法pop出栈代码实现:importjava.util.Iterator;publicclassStackTimplementsIterableT{//记录首结点privateNodehead;//栈中元素的个数privateintN;//单向链表 节点NodeprivateclassNode{publicTitem;publicNodenext;publicNode(Titem,Nodenext){this.itemitem;this.nextnext;}}publicStack(){this.headnewNode(null,null);this.N0;}//判断当前栈中元素个数是否为0publicbooleanisEmpty(){returnN0;}//获取栈中元素的个数publicintsize(){returnN;}//把t元素压入栈publicvoidpush(Tt){//找到首结点指向的第一个结点NodeoldFirsthead.next;//创建新结点NodenewNodenewNode(t,null);//让首结点指向新结点head.nextnewNode;//让新结点指向原来的第一个结点newNode.nextoldFirst;//元素个数1N;}//弹出栈顶元素publicTpop(){//找到首结点指向的第一个结点NodeoldFirsthead.next;if(oldFirstnull){returnnull;}//让首结点指向原来第一个结点的下一个结点head.nextoldFirst.next;//元素个数-1N--;returnoldFirst.item;}OverridepublicIteratorTiterator(){returnnewSIterator();}privateclassSIteratorimplementsIterator{privateNoden;publicSIterator(){this.nhead;}OverridepublicbooleanhasNext(){returnn.next!null;}OverridepublicObjectnext(){nn.next;returnn.item;}}}测试:publicclassStackTest{publicstaticvoidmain(String[]args){//创建栈对象StackStringstacknewStack();//测试压栈stack.push(a);stack.push(b);stack.push(c);stack.push(d);for(Stringitem:stack){System.out.println(item);}System.out.println(------------------------------);//测试弹栈Stringresultstack.pop();System.out.println(弹出的元素是result);System.out.println(剩余的元素个数stack.size());}}java自带的 StackStackpackage java.util;Vectorjava.util.Stack 是由数组实现