请问你知道什么是栈吗？
1.1栈的概念及记本操作
栈(stack)又称堆栈,是限制在表的一端进行插入和删除的线性表。其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端称为栈顶(Top),栈顶保存的元素称为栈顶元素。相对的,表的另一端称为栈底( Bottom)。当栈中没有数据元素时称为空栈;向一个栈插入元素又称为进栈或入栈;从一个栈中删除元素又称为出栈或退栈。
由于栈的插入和删除操作仅在栈顶进行,后进栈的元素必定先出栈,所以又把堆栈称为后进先出表( Last In First Out,LIFO)。图3.1显示了一个堆栈及数据元素插入和删除的过程。
在图3.1中，当ABCD 均已人栈之后，出栈时得到的序列为DCBA，这就是“后进先出”。在解决实际问题时，如果碰到了数据的使用具有“后进先出”的特性，就预示着可以使用堆栈来存储和使用这些数据，堆栈的基本操作除了进栈、出栈操作外，还有判空、取栈顶元素等操作。
1.2顺序栈
由于栈是运算受限的线性表，除了操作不同外，线性表的存储结构对栈也是适用的。利用顺序存储方式实现的栈称为顺序栈。为了便于理解，后面示例中顺序栈操作，均以学号和姓名为数据元素。
1.入职操作思想
根据顺序栈的存储特点，要将某一元素压入栈内，则要进行如下操作:
(1)先判断栈是否已经装满元素，如果未装满才能进行入栈操作，否则不操作。
(2 )栈顶指针先自增，给需要进栈的元素腾出内存空间。
(3 )再将要入栈的元素放入腾出的内存空间里，就是把入栈的元素赋值给对应的数组元素。
【例3.1】 1200101班已有2 名同学王丽、张阳的报到信息存放在栈内，现有(120010131，郑克龙) 同学来报到，请将其信息压人栈中。
首先要定义学生信息类来存放学生记录，具体参数自己定义。
接下来压入对应结点的过程如下:
栈顶指针先自增，给需要进栈的元素腾出内存空间，再往空间里压入元素( 120010131,郑克龙)，如图3.3 所示。
2.入栈操作流程图
顺序栈的学生元素存放在data 数组中，length为栈的总长度，top为栈顶指针，则学生元素入栈程序流程图如图3.4 所示。
3.入栈操作代码实现
public class SeqStack { //顺序栈
//在该例中各元素为学生对象，因此数组定义为student类型
Student data[];//data为存放学生表各数据元素的数组
int length;//栈长度
int top;//栈顶指针
public SeqStack(){
data=new Student[35];
length=35;
top=-1;
}
public boolean push(Student stu){
boolean bRst=false;
if(top>=-1&&top<length-1){ //入栈位置正确与否判断
top++;
data[top]=stu;//插入新节点stu
System.out.println("入栈："+data[top].no+""+data[top].name);
bRst=true;
}
return bRst;
}
public static void main(String[] args) {
Student stu1=new Student();
stu1.no="120010103";
stu1.name="张阳";
Student stu2=new Student();
stu2.no="120010102";
stu2.name="王丽";
Student stu3=new Student();
stu3.no="120010131";
stu3.name="郑克龙";
SeqStack ss= new SeqStack();
ss.push(stu1);
ss.push(stu2);
ss.push(stu3);
}
}4.出栈操作思想
根据顺序栈的存储特点，要取出栈内某一元素，则要进行如下操作:
(1) 先判断栈是否有元素，如果有元素时才能进行出栈操作，否则不操作。
(2 )再将要出栈的元素取出放在内存空间里。
(3 )栈顶指针自减。
【例3.2】1200101班已有3名同学王丽、张阳、郑克龙的报到信息存放在栈内，现需要从栈中取出一位同学的信息进行审查，并显示取出的信息。
首先要定义学生信息类来存放学生记录，具体参见上一章的class Student 定义。
接下来取出对应结点的过程如下:
出栈前如图3.5 所示。
先把需要出栈的元素( 120010131，郑克龙)取出放在内存空间里，再把栈顶指针自减如图3.6 所示。
5.出栈操作流程图
顺序栈的学生元素存放在data数组中，length为栈的总长度，top为栈顶指针，则学生元素出栈流程图如3.7所示。
6.出栈操作代码实现
在入栈的基础上，添加出栈代码，实现如图3.7的流程功能，具体代码实现如下：
public class SeqStack { // 顺序栈
// 在该例中各元素为学生对象，因此数组定义为student类型
Student data[];// data为存放学生表各数据元素的数组
int length;// 栈长度
int top;// 栈顶指针
public SeqStack() {
data = new Student[35];
length = 35;
top = -1;
}
// 进栈
public boolean push(Student stu) {
boolean bRst = false;
if (top >= -1 && top < length - 1) { // 入栈位置正确与否判断
top++;
data[top] = stu;// 插入新节点stu
System.out.println("入栈：" + data[top].no + "" + data[top].name);
bRst = true;
}
return bRst;
}
// 出栈
public Student pop() {
Student stu = null;
if (top >= 0 && top < length) {
stu = data[top];
System.out.println("出栈：" + data[top].no + "" + data[top].name);
top--;
}
return stu;
}
public static void main(String[] args) {
Student stu1 = new Student();
stu1.no = "120010103";
stu1.name = "张阳";
Student stu2 = new Student();
stu2.no = "120010102";
stu2.name = "王丽";
Student stu3 = new Student();
stu3.no = "120010131";
stu3.name = "郑克龙";
SeqStack ss = new SeqStack();
ss.push(stu1);
ss.push(stu2);
ss.push(stu3);
//出栈
while(ss.top>=0){
ss.pop();
}
}
}1.3链栈
用链式存储结构实现的栈称为链栈。其结点结构与单链表的结构相同，链式堆栈也是由一个个结点组成的，每个结点由两个域组成，一个是存放数据元素的数据元素域element,另一个是存放指向下一个结点的对象引用(即指针)next
因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要像单链表那样为了运算方便附加一个头结点，所以链式堆栈通常不带头结点。
通常将链栈表示成图3.8 的形式。
在学生信息类的基础上，链栈的结点定义如下：
public class Node { // 节点类
public Student stu; // 节点数据为学生对象
public Node next;// 后继节点的地址
public Node() {
stu = null;
next = null;
}
}链栈的基本操作也是进栈和出栈操作。
1.进栈操作思想
根据链栈的存储特点，要将某一个新节点s压入栈内，则要进行如下操作：
(1) 处理新结点s的后继，这个后继就是原本的栈顶结点。
(2) 将栈顶指针top 重新指向新结点s即可。
【例3.3】1200101班已有两名同学王丽、张阳的报到信息存放在链栈内，现有(120010131，郑克龙) 同学来报到，请将其信息压人链栈中。
首先要定义学生信息类和结点类。
接下来将对应结点压人链栈内的过程如下:
入栈前如图3.9 所示。
生成新节点（120010131，郑克龙），处理新节点的后继，使其后继指向原本的栈顶节点，如图3.10所示。
将栈顶指针top重新指向新节点（120010131，郑克龙）即可，如果3.11所示。
2.进栈操作流程图
链栈中插入的学生元素存放在node中，top为栈顶指针，curlen为栈的长度，则学生元素入栈程序流程图如图3.12所示。
3.进栈操作代码实现
public class LinkStack {// 链栈
Node top;// 链表头指针
int curlen;// 实际表长
public LinkStack() {
top = null;
curlen = 0;
}
// 在表的第i个位置前插入新数据元素node，返回插入操作结果
public void push(Node node) {
node.next = top;
top = node;
System.out.println("入栈" + top.stu.no + "" + top.stu.name);
curlen++;
}
public static void main(String[] args) {
LinkStack ls = new LinkStack();
Node node1 = new Node();
node1.stu = new Student();
node1.stu.no = "120010103";
node1.stu.name = "张阳";
Node node2 = new Node();
node2.stu = new Student();
node2.stu.no = "120010102";
node2.stu.name = "王丽";
Node node3 = new Node();
node3.stu = new Student();
node3.stu.no = "120010131";
node3.stu.name = "郑克龙";
ls.push(node1);
ls.push(node2);
ls.push(node3);
}
}4.出栈操作思想
根据链栈的存储特点，要弹出某一个结点，则要进行如下操作:
(1) 在栈顶指针top 非空的情况下，保存弹出结点。
(2) 将栈顶指针top 下移一个元素，即top= top.next。
【例3.4】 1200101班已有3 名同学王丽、张阳、郑克龙的报到信息存放在链栈内，现需要从链栈中取出一位同学的信息进行审查，并显示取出的信息。
首先要定义学生信息类和结点类，具体参见上一章class Student 和class Node的定义。
接下来弹出对应结点的过程如图3.13 所示。
5.出栈操作流程图
链栈中弹出学生元素存放在ni中，top为栈顶指针，curlen为栈的长度，则学生元素出栈程序流程图如3.14所示。
6.出栈操作代码实现
在链表入栈程序的基础上，添加出栈代码，如图。3.14所示的流程功能，具体实现代码如下：
public class LinkStack {// 链栈
Node top;// 链表头指针
int curlen;// 实际表长
public LinkStack() {
top = null;
curlen = 0;
}
// 在表的第i个位置前插入新数据元素node，返回插入操作结果
public void push(Node node) {
node.next = top;
top = node;
System.out.println("入栈" + top.stu.no + "" + top.stu.name);
curlen++;
}
// ========出栈===========
public Node pop() {
Node ni = null;
if (top != null) {
ni = top;
top = top.next;
curlen--;
System.out.println("出栈" + ni.stu.no + "" + ni.stu.name);
}
return ni;
}
public static void main(String[] args) {
LinkStack ls = new LinkStack();
Node node1 = new Node();
node1.stu = new Student();
node1.stu.no = "120010103";
node1.stu.name = "张阳";
Node node2 = new Node();
node2.stu = new Student();
node2.stu.no = "120010102";
node2.stu.name = "王丽";
Node node3 = new Node();
node3.stu = new Student();
node3.stu.no = "120010131";
node3.stu.name = "郑克龙";
ls.push(node1);
ls.push(node2);
ls.push(node3);
// =======出栈==========
while (ls.top != null) {
ls.pop();
}
}
}