JAVA数据结构与算法：栈

栈栈⼀种特殊的线性表其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶另⼀端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。压栈栈的插⼊操作叫做进栈/压栈/⼊栈⼊数据在栈顶出栈栈的删除操作叫做出栈出数据在栈顶栈的使用方法功能Stack()构造一个空的栈E push(E e)将e入栈并返回eE pop()将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中有效元素个数boolean empty()检测栈是否为空栈的模拟实现栈的接口publicinterfaceStackInterface{// 入栈voidpush(intval);// 出栈返回栈顶元素空栈抛异常intpop();// 获取栈顶元素不弹出intpeek();// 判断栈是否为空booleanisEmpty();// 获取当前栈中元素个数intsize();// 清空栈voidclear();// 判断是否包含指定元素booleancontains(intval);}将元素压入栈publicvoidpush(intval){// 如果栈已满则扩容为原来的2倍if(isFull()){arrArrays.copyOf(arr,arr.length*2);}// 将元素放入栈顶并更新栈顶指针arr[top]val;}弹出栈顶元素publicintpop(){if(isEmpty()){thrownewEmptyStackException();}// 获取栈顶元素值并将栈顶指针下移intvalarr[top-1];top--;returnval;}获取栈顶元素publicintpeek(){if(isEmpty()){thrownewEmptyStackException();}returnarr[top-1];}检查栈是否已满publicbooleanisFull(){returntoparr.length;}检查栈是否为空publicbooleanisEmpty(){returntop0;}获取栈中元素的数量publicintsize(){returntop;}检查栈中是否包含某个值publicbooleancontains(intval){// 遍历栈中的元素for(inti0;itop;i){if(arr[i]val){returntrue;}}returnfalse;}栈模拟实现完整代码数组栈packageDataStructure.DS_Stack;importjava.util.Arrays;importjava.util.EmptyStackException;/** * MyStack类实现了栈接口StackInterface使用数组实现栈的基本功能 */publicclassMyStackimplementsStackInterface{// 使用数组存储栈元素privateint[]arr;// 栈顶指针指向下一个插入位置privateinttop;/** * 构造函数初始化一个容量为10的空栈 */publicMyStack(){this.arrnewint[10];top0;}/** * 将元素压入栈 * param val 要压入栈的整数值 */Overridepublicvoidpush(intval){// 如果栈已满则扩容为原来的2倍if(isFull()){arrArrays.copyOf(arr,arr.length*2);}// 将元素放入栈顶并更新栈顶指针arr[top]val;}/** * 检查栈是否已满 * return 如果栈已满返回true否则返回false */publicbooleanisFull(){returntoparr.length;}/** * 检查栈是否为空 * return 如果栈为空返回true否则返回false */OverridepublicbooleanisEmpty(){returntop0;}/** * 获取栈中元素的数量 * return 栈中元素的个数 */Overridepublicintsize(){returntop;}/** * 清空栈 */Overridepublicvoidclear(){top0;}/** * 检查栈中是否包含某个值 * param val 要查找的整数值 * return 如果栈中包含该值返回true否则返回false */Overridepublicbooleancontains(intval){// 遍历栈中的元素for(inti0;itop;i){if(arr[i]val){returntrue;}}returnfalse;}/** * 查看栈顶元素但不移除 * return 栈顶元素的值 * throws EmptyStackException 如果栈为空则抛出此异常 */Overridepublicintpeek(){if(isEmpty()){thrownewEmptyStackException();}returnarr[top-1];}/** * 弹出栈顶元素 * return 栈顶元素的值 * throws EmptyStackException 如果栈为空则抛出此异常 */Overridepublicintpop(){if(isEmpty()){thrownewEmptyStackException();}// 获取栈顶元素值并将栈顶指针下移intvalarr[top-1];top--;returnval;}}链栈packageDataStructure.DS_Stack;importjava.util.EmptyStackException;publicclassMyLinkedListStackimplementsStackInterface{staticclassListNode{publicintval;publicListNodenext;publicListNodepre;publicListNode(intval){this.valval;this.nextnull;this.prenull;}}ListNodeheadnull;ListNodetailnull;Overridepublicvoidpush(intval){ListNodenewNodenewListNode(val);if(isEmpty()){headnewNode;tailnewNode;}else{newNode.pretail;tail.nextnewNode;tailnewNode;}}Overridepublicintpop(){if(isEmpty()){thrownewEmptyStackException();}if(headtail){intdatahead.val;headnull;returndata;}intdatatail.val;tailtail.pre;tail.nextnull;returndata;}Overridepublicintpeek(){if(isEmpty()){thrownewEmptyStackException();}returntail.val;}OverridepublicbooleanisEmpty(){returnheadnull;}Overridepublicintsize(){if(headnull)return0;if(headtail)return1;ListNodecurhead;intlen0;while(cur!null){len;curcur.next;}returnlen;}Overridepublicvoidclear(){headnull;tailnull;}Overridepublicbooleancontains(intval){ListNodecurhead;while(cur!null){if(cur.valval){returntrue;}curcur.next;}returnfalse;}}