栈是一种常用的数据结构，在生活中经常遇到这样的例子，如铁路调度站。本节将详细介绍堆栈的实现过程。

算法点拨(顺序栈)

栈是一种重要的数据结构。从数据结构的角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它们是操作受限的线性表，因此可以称为限定性的数据结构。其操作是限定在表尾进行插入和删除操作，允许操作的一端称为栈顶。栈的结构如图11.09所示：

图11.09 栈的结构

实现栈首先需要实现一个栈内元素，关键代码如下：

Java代码

public class Stack {

private int maxSize;

private int stackArray[];

private int top=-1;

public Stack(int s){ //构造方法

maxSize=s;

stackArray=new int[maxSize];

}

说明：

上述代码中，公共成员stackArray用于储存栈中的数据，top用于存储下一个数据元素的指针。对于栈的操作，无非是进行数据元素的入栈与出栈。

1．查找栈中元素

在进行栈中元素查找时，通常根据栈中元素的数据查找节点。要实现栈中元素的查找，首先需要解决的问题就是遍历栈中的所有元素。可以从栈顶开始，利用循环的方式向下查找，只要不到栈底就可循环查找。

2．入栈操作

入栈操作前面说过，只能在栈顶操作。先将top指针向后移动一个单位，然后将想要入栈的数据元素放到原来top指针所指向的元素位置即可。这样就实现了对栈的入栈操作。操作流程如图11.10所示：

图11.10 入栈操作示意图

3．出栈操作

出栈操作和入栈操作的限定差不多，只是将整个过程反过来进行。先将数据元素释放掉，然后在进行指针的操作，将栈顶指针top向前移动一个位置，使其位置在其原来所指向的位置。将栈顶元素的指针域的指针的指向位置变为原来元素的指向位置。出栈的操作流程如图11.11所示

图11.11 删除节点示意图

算法实现

栈是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说，表尾端有其特殊含义。

例11.3 实现栈的算法

首先需要实现自定义的数据元素类，该类的实现方法可以参看本节算法点拨中的代码。

定义数据元素之后，开始栈的操作编程了。在类中，采用了push，pop，isEmpty，isfull，等方法进行入栈，出栈，判断栈是否为空，判断栈是否满和对栈进行输出。

向栈中添加数据的代码如下：

Java代码

public void push(int j){ //入栈方法

stackArray[++top]=j; //栈顶指针后移

}

对栈进行出栈的操作的代码如下：

Java代码

public int pop(){ //出栈方法

return stackArray[top--]; //栈顶指针前移

}

对栈是否为空和是否已满以及输出的判断代码如下：

Java代码

public boolean isEmpty(){ //判断栈是否为空

return (top==-1);

}

public boolean isFull(){ //判断栈是否为满

return (top==maxSize-1);

}

public void s(int d){ //输出栈中内容

System.out.println("栈序列：");

for(int i=0;i

System.out.print(stackArray[i]+" ");

}

为了检查创建栈操作的正确性，特别创建了一个名称为StackTest的类，测试栈的入栈和出栈的操作，其关键代码如下：

Java代码

package stack;

public class StackTest {

public static void main(String[] args) {

int i=0;

Stack s=new Stack(20);

if(!s.isFull()){ //判断栈是否满，没满则调用入栈方法

s.push(100);i++;

s.push(23);i++;

s.push(45);i++;

s.push(78);i++;

s.s(i);

}

System.out.println("\n");

System.out.println("出栈序列：");

while(!s.isEmpty()){ //判断栈是否为空，非空则调用出栈方法

int k=s.pop();

System.out.print(k+" ");

}

运行上面的代码后，在控制台输出的信息如图11.12所示。

图11.12 运行测试类后在控制台输出的栈中的数据

算法点拨(两栈共享空间)

在一个程序中如果需要同时使用具有相同数据类型的两个栈时，我们觉得最直接的办法就是，同时开辟出两块空间，建立两个栈，但是这样有时会出现，一个栈已经栈满溢出了，而另一个栈确实空余出大量的存储空间，这样会造成大量存储空间的浪费。现在我们可以找一种解决的方法，那就是：两栈共享空间。我们使用一个数组来存储两个栈，让一个栈的栈底为数组的始端，另一个栈的栈底为数组的末端，每个栈的栈顶都向中间延伸。两栈共享空间的结构如图11.13所示：

图11.13 栈的结构

实现栈首先需要实现一个栈内元素，关键代码如下：

Java代码

public class Stack {

private int maxSize;

private int stackArray[];

private int top=-1;

public Stack(int s){ //构造方法

maxSize=s;

stackArray=new int[maxSize];

}

说明：

上述代码中，公共成员stackArray用于储存栈中的数据，top用于存储下一个数据元素的指针。对于栈的操作，无非是进行数据元素的入栈与出栈。

1．查找共享空间栈中元素

在进行共享空间的栈中元素查找时，首先我们先要确定我们是要查找哪一个栈中的元素，然后的操作就和顺序栈基本一样了。

2．入栈操作

两栈共享空间的入栈操作也是我们要先确定我们要对哪一个栈进行操作。入栈操作前面我们在顺序栈中已经说过，只能在栈顶操作。例如我们选择对栈一进行操作，先将top1指针向后移动一个单位，然后将想要入栈的数据元素放到原来top1指针所指向的元素位置即可。这样就实现了对栈的入栈操作。操作流程如图11.14所示：

图11.14 入栈操作示意图

3．出栈操作

对于共享空间栈的出栈操作和入栈操作的限定差不多，只是将整个过程反过来进行。先将数据元素释放掉，然后在进行指针的操作，将栈顶指针top1向前移动一个位置，使其位置在其原来所指向的位置。将栈顶元素的指针域的指针的指向位置变为原来元素的指向位置。出栈的操作流程如图11.15所示

图11.15 删除节点示意图

算法实现

栈是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说，表尾端有其特殊含义。

例11.4 实现栈的算法

首先需要实现自定义的数据元素类，该类的实现方法可以参看本节算法点拨中的代码。

定义数据元素之后，开始栈的操作编程了。在类中，采用了push，pop，isEmpty，isfull，s等方法进行入栈，出栈，判断栈是否为空，判断栈是否满和对栈进行输出。

向栈中添加数据的代码如下：

Java代码

public int bos(int i,int x){