企业官网建设流程全解析

栈

生活中的栈----客栈

• 存储货物或供旅客住宿的地方,可引申为仓库、中转站 。例如我们现在生活中的酒店，在古时候叫客栈，是供旅客休息的地方，旅客可以进客栈休息，休息完毕后就离开客栈。

计算机中的栈:

• 我们把生活中的栈的概念引入到计算机中，就是供数据休息的地方，它是一种数据结构，数据既可以进入到栈中，又可以从栈中出去。
• 栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

栈是一种基于先进后出(FILO)的数据结构

first in last out

我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。

栈代码实现

• 数组实现
• 链表实现

数组实现:

对于数组来说，我们模拟栈的过程很简单，因为栈是后进先出，我们很容易在数组的末尾进行插入和删除。

• 所以我们选定末尾为栈顶。所以对于一个栈所需要的基础元素是 一个data数组和一个top(int)做指针表示栈顶位置。

push入栈

• 如果top<数组长度-1。入栈。top++;a[top]=value;
• 如果top==数组长度-1；栈满。

pop出栈并返回首位

• 如果top>=0,栈不为空，可以弹出。return data[top–];
• 如下图，本来栈为1，2，3，4（栈顶），执行pop操作。top变为3的位置并且返回4；
  

代码实现:

选定数组末尾为栈顶,设计top指针 指向栈顶元素

publicclassStack01<T>implementsIterable<T>{//数组privateTdata[];//top指针 指向栈顶元素privateinttop;publicStack01(){data=(T[])newObject[10];top=-1;}publicStack01(intmaxsize){data=(T[])newObject[maxsize];top=-1;}booleanisEmpty(){returntop==-1;}intsize(){returntop+1;}//入栈booleanpush(Tvalue)throwsException{if(top+1>data.length-1){thrownewException("栈已满");}else{data[++top]=value;returntrue;}}//返回栈顶元素不移除Tpeek()throwsException{if(!isEmpty()){returndata[top];}else{thrownewException("栈为空");}}//出栈Tpop()throwsException{if(isEmpty()){thrownewException("栈为空");}else{returndata[top--];}}@OverridepublicIterator<T>iterator(){returnnewStack01.SIterator();}privateclassSIteratorimplementsIterator{privateintcusor;publicSIterator(){this.cusor=top;}@OverridepublicbooleanhasNext(){returncusor>=0;}@OverridepublicObjectnext(){if(top==-1){returnnull;}returndata[cusor--];}}}

测试

publicclassStackTest01{publicstaticvoidmain(String[]args)throwsException{//创建栈对象Stack01<String>stack=newStack01<>(12);//测试压栈stack.push("a");stack.push("b");stack.push("c");stack.push("d");for(Stringitem:stack){System.out.println(item);}System.out.println("------------------------------");//测试弹栈Stringresult=stack.pop();System.out.println("弹出的元素是："+result);System.out.println("剩余的元素个数："+stack.size());}}

链表实现:

栈API设计

push入栈

单向链表头插法

pop出栈

代码实现:

importjava.util.Iterator;publicclassStack<T>implementsIterable<T>{//记录首结点privateNodehead;//栈中元素的个数privateintN;//单向链表 节点NodeprivateclassNode{publicTitem;publicNodenext;publicNode(Titem,Nodenext){this.item=item;this.next=next;}}publicStack(){this.head=newNode(null,null);this.N=0;}//判断当前栈中元素个数是否为0publicbooleanisEmpty(){returnN==0;}//获取栈中元素的个数publicintsize(){returnN;}//把t元素压入栈publicvoidpush(Tt){//找到首结点指向的第一个结点NodeoldFirst=head.next;//创建新结点NodenewNode=newNode(t,null);//让首结点指向新结点head.next=newNode;//让新结点指向原来的第一个结点newNode.next=oldFirst;//元素个数+1；N++;}//弹出栈顶元素publicTpop(){//找到首结点指向的第一个结点NodeoldFirst=head.next;if(oldFirst==null){returnnull;}//让首结点指向原来第一个结点的下一个结点head.next=oldFirst.next;//元素个数-1；N--;returnoldFirst.item;}@OverridepublicIterator<T>iterator(){returnnewSIterator();}privateclassSIteratorimplementsIterator{privateNoden;publicSIterator(){this.n=head;}@OverridepublicbooleanhasNext(){returnn.next!=null;}@OverridepublicObjectnext(){n=n.next;returnn.item;}}}

测试:

publicclassStackTest{publicstaticvoidmain(String[]args){//创建栈对象Stack<String>stack=newStack<>();//测试压栈stack.push("a");stack.push("b");stack.push("c");stack.push("d");for(Stringitem:stack){System.out.println(item);}System.out.println("------------------------------");//测试弹栈Stringresult=stack.pop();System.out.println("弹出的元素是："+result);System.out.println("剩余的元素个数："+stack.size());}}

java自带的 Stack

Stack

package java.util;

Vector

java.util.Stack 是由数组实现