一、栈（Stack）

 

　　1.栈的基本概念

 

　　栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

 

　　压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

 

　　出栈：栈的删除操作叫做出栈。出数据在栈顶。

 

　　栈顶指针：顾名思义，栈顶指针是指向栈顶的一个指针。但Java当中没有指针这一说法，因此也可以当作下标来进行处理。

 

　　需要注意的是：栈顶指针指向的是可以存放元素的栈的位置，一旦有元素放入后它再加1。

 

　　Stack中的方法有：

 

　　push为压栈，pop为出栈（返回值为出栈的值），peek为栈顶元素，empty为判断栈是否为空，search为找出某个元素在栈中的第几个位置，返回下标。

 

　　2.用顺序表实现栈

 

　　用顺序表实现的栈称为顺序栈，只是该顺序表的实际操作也是一样要遵循栈的基本操作——先进后出。

 

　　public class MyStack {

 

　　private int[] elem ;

 

　　private int top = 0 ;

 

　　public MyStack（） {

 

　　this.elem = new int[3];

 

　　}

 

　　public void push（int item） {

 

　　if（top==elem.length） {

 

　　Arrays.copyOf（elem,5）;

 

　　return;

 

　　}

 

　　elem[top]=item;

 

　　top++;

 

　　}

 

　　public int pop（） {

 

　　if（top==0） {

 

　　throw new UnsupportedOperationException（"栈为空"）;

 

　　}

 

　　top--;

 

　　int ret = this.elem[top];

 

　　return ret;

 

　　}

 

　　public int peek（） {

 

　　if（top==0） {

 

　　throw new UnsupportedOperationException（"栈为空"）;

 

　　}

 

　　return this.elem[top-1];

 

　　}

 

　　public int search（int item） {

 

　　return 0;

 

　　}

 

　　}

 

　　3.用链表实现栈

 

　　**用链表实现栈要注意一个点：因为栈遵循的是先进后出，因此我们在入栈时的操作为单链表的头插法，出栈时的操作为删除单链表的头结点，并使得头结点指向下一结点。**只有这样用单链表实现栈才能做到时间复杂度为O（1）。