数据结构Java实现05----栈：顺序栈和链式堆栈

ゝ一世哀愁。 2024-02-17 21:23 65阅读 0赞

本文转载至：[http://www.cnblogs.com/smyhvae/p/4789699.html][http_www.cnblogs.com_smyhvae_p_4789699.html]

一、堆栈的基本概念：

堆栈（也简称作栈）是一种特殊的线性表，堆栈的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置进行插入和删除操作，而堆栈只允许在固定一端进行插入和删除操作。

先进后出：堆栈中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。堆栈的插入和删除操作通常称为进栈或入栈，堆栈的删除操作通常称为出栈或退栈。

备注：栈本身就是一个线性表，所以我们之前讨论过线性表的顺序存储和链式存储，对于栈来说，同样适用。

二、堆栈的抽象数据类型：

数据集合：

堆栈的数据集合可以表示为a0,a1,…,an-1，每个数据元素的数据类型可以是任意的类类型。

操作集合：

> （1）入栈push(obj)：把数据元素obj插入堆栈。
> 
> （2）出栈pop()：出栈, 删除的数据元素由函数返回。
> 
> （3）取栈顶数据元素getTop()：取堆栈当前栈顶的数据元素并由函数返回。
> 
> （4）非空否notEmpty()：若堆栈非空则函数返回true，否则函数返回false。

三、顺序栈：

顺序存储结构的堆栈称作顺序堆栈。其存储结构示意图如下图所示：

[![42c4b8c6-f428-468d-b5aa-2cf9f4ae86e2][]][42c4b8c6-f428-468d-b5aa-2cf9f4ae86e2 1]

1、顺序栈的实现：

（1）设计Stack接口

（2）实现SequenceStack类

注：栈是线性表的特例，线性表本身就是用数组来实现的。于是，顺序栈也是用数组实现的。

代码实现：

(1)Stack.java:（Stack接口）

![复制代码][copycode.gif]

1 public interface Stack {
     2 
     3     //入栈
     4     public void push(Object obj) throws Exception;
     5 
     6     //出栈
     7     public Object pop() throws Exception;
     8 
     9     //获取栈顶元素
    10     public Object getTop() throws Exception;
    11 
    12     //判断栈是否为空
    13      public boolean isEmpty();
    14 }

![复制代码][copycode.gif]

(2)SequenceStack.java:

![复制代码][copycode.gif]

1 //顺序栈
     2 public class SequenceStack implements Stack {
     3 
     4     Object[] stack; //对象数组（栈用数组来实现）
     5     final int defaultSize = 10; //默认最大长度
     6     int top; //栈顶位置（的一个下标）:其实可以理解成栈的实际长度
     7     int maxSize; //最大长度
     8 
     9     //如果用无参构造的话，就设置默认长度
    10     public SequenceStack() {
    11         init(defaultSize);
    12     }
    13 
    14     //如果使用带参构造的话，就调用指定的最大长度
    15     public SequenceStack(int size) {
    16         init(size);
    17     }
    18 
    19     public void init(int size) {
    20         this.maxSize = size;
    21         top = 0;
    22         stack = new Object[size];
    23     }
    24 
    25     //获取栈顶元素
    26     @Override
    27     public Object getTop() throws Exception {
    28         // TODO Auto-generated method stub
    29         if (isEmpty()) {
    30             throw new Exception("堆栈为空！");
    31         }
    32 
    33         return stack[top - 1];
    34     }
    35 
    36     //判断栈是否为空
    37     @Override
    38     public boolean isEmpty() {
    39         // TODO Auto-generated method stub
    40         return top == 0;
    41     }
    42 
    43     //出栈操作
    44     @Override
    45     public Object pop() throws Exception {
    46         // TODO Auto-generated method stub
    47         if (isEmpty()) {
    48             throw new Exception("堆栈为空！");
    49         }
    50         top--;
    51 
    52         return stack[top];
    53     }
    54 
    55     //入栈操作
    56     @Override
    57     public void push(Object obj) throws Exception {
    58         // TODO Auto-generated method stub
    59         //首先判断栈是否已满
    60         if (top == maxSize) {
    61             throw new Exception("堆栈已满！");
    62         }
    63         stack[top] = obj;
    64         top++;
    65     }
    66 }

![复制代码][copycode.gif]

2、测试类：

设计一个顺序栈，从键盘输入十个整数压进栈，然后再弹出栈，并打印出栈序列。

代码实现：

(3)Test.java:

![复制代码][copycode.gif]

1 import java.util.Scanner;
     2 
     3 public class Test {
     4     public static void main(String[] args) throws Exception {
     5         SequenceStack stack = new SequenceStack(10);
     6 
     7         Scanner in = new Scanner(System.in);
     8         int temp;
     9         for (int i = 0; i < 10; i++) {
    10             System.out.println("请输入第" + (i + 1) + "个整数：");
    11             temp = in.nextInt();
    12             stack.push(temp);
    13         }
    14 
    15         //遍历输出
    16         while (!stack.isEmpty()) {
    17             System.out.println(stack.pop());
    18         }
    19     }
    20 }

![复制代码][copycode.gif]

运行效果：

[![9fd3385e-ab5b-4fc1-852f-4afe8ec9b304][]][9fd3385e-ab5b-4fc1-852f-4afe8ec9b304 1]

四、Java中栈与堆的区别：

栈(stack):（线程私有）

是一个先进后出的数据结构，通常用于保存方法(函数)中的参数，局部变量。在java中,所有基本类型和引用类型的引用都在栈中存储。栈中数据的生存空间一般在当前scopes内(就是由\{...\}括起来的区域)。

堆(heap):（线程共享）

是一个可动态申请的内存空间(其记录空闲内存空间的链表由操作系统维护)，C中的malloc语句所产生的内存空间就在堆中。在java中，所有使用new xxx()构造出来的对象都在堆中存储，当垃圾回收器检测到某对象未被引用，则自动销毁该对象。所以，理论上说java中对象的生存空间是没有限制的，只要有引用类型指向它，则它就可以在任意地方被使用。

五、hashCode与对象之间的关系：

如果两个对象的hashCode不相同，那么这两个对象肯定也不同。

如果两个对象的hashCode相同，那么这两个对象有可能相同，也有可能不同。

总结一句：不同的对象可能会有相同的hashCode；但是如果hashCode不同，那肯定不是同一个对象。

代码举例：

![复制代码][copycode.gif]

1 public class StringTest {
     2 
     3     public static void main(String[] args) {
     4 
     5         //s1 和 s2 其实是同一个对象。对象的引用存放在栈中，对象存放在方法区的字符串常量池
     6         String s1 = "china";
     7         String s2 = "china";
     8 
     9         //凡是用new关键创建的对象，都是在堆内存中分配空间。
    10         String s3 = new String("china");
    11 
    12         //凡是new出来的对象，绝对是不同的两个对象。
    13         String s4 = new String("china");
    14 
    15         System.out.println(s1 == s2);  //true
    16         System.out.println(s1 == s3);
    17         System.out.println(s3 == s4);
    18         System.out.println(s3.equals(s4));
    19 
    20         System.out.println("\n-----------------\n");
    21       /*String很特殊，重写从父类继承过来的hashCode方法，使得两个
    22        *如果字符串里面的内容相等，那么hashCode也相等。
    23        **/
    24 
    25         //hashCode相同
    26         System.out.println(s3.hashCode());  //hashCode为94631255
    27         System.out.println(s4.hashCode());  //hashCode为94631255
    28 
    29         //identityHashCode方法用于获取原始的hashCode
    30         //如果原始的hashCode不同，表明确实是不同的对象
    31 
    32         //原始hashCode不同
    33         System.out.println(System.identityHashCode(s3)); //2104928456
    34         System.out.println(System.identityHashCode(s4)); //2034442961
    35 
    36         System.out.println("\n-----------------\n");
    37 
    38         //hashCode相同
    39         System.out.println(s1.hashCode());  //94631255
    40         System.out.println(s2.hashCode());  //94631255
    41 
    42         //原始hashCode相同：表明确实是同一个对象
    43         System.out.println(System.identityHashCode(s1));  //648217993
    44         System.out.println(System.identityHashCode(s2));  //648217993
    45     }
    46 }

![复制代码][copycode.gif]

`上面的代码中，注释已经标明了运行的结果。通过运行结果我们可以看到，s3和s4的字符串内容相同，但他们是两个不同的对象，由于String类重写了hashCode方法，他们的hashCode相同，但原始的hashCode是不同的。`

六、链式堆栈：

链式存储结构的堆栈称作链式堆栈。

与单链表相同，链式堆栈也是由一个个结点组成的，每个结点由两个域组成，一个是存放数据元素的数据元素域data，另一个是存放指向下一个结点的对象引用（即指针）域next。

堆栈有两端，插入数据元素和删除数据元素的一端为栈顶，另一端为栈底。链式堆栈都设计成把靠近堆栈头head的一端定义为栈顶。

依次向链式堆栈入栈数据元素a0, a1, a2, ..., an-1后，链式堆栈的示意图如下图所示：

[![44298c1d-2054-4dd5-be7d-1f7e4cd5f43f][]][44298c1d-2054-4dd5-be7d-1f7e4cd5f43f 1]

1、设计链式堆栈：

(1)Node.java:结点类

![复制代码][copycode.gif]

1 //结点类
     2 public class Node {
     3 
     4     Object element; //数据域
     5     Node next;  //指针域
     6 
     7     //头结点的构造方法
     8     public Node(Node nextval) {
     9         this.next = nextval;
    10     }
    11 
    12     //非头结点的构造方法
    13     public Node(Object obj, Node nextval) {
    14         this.element = obj;
    15         this.next = nextval;
    16     }
    17     
    18     //获得当前结点的后继结点
    19     public Node getNext() {
    20         return this.next;
    21     }
    22 
    23     //获得当前的数据域的值
    24     public Object getElement() {
    25         return this.element;
    26     }
    27 
    28     //设置当前结点的指针域
    29     public void setNext(Node nextval) {
    30         this.next = nextval;
    31     }
    32 
    33     //设置当前结点的数据域
    34     public void setElement(Object obj) {
    35         this.element = obj;
    36     }
    37 
    38     public String toString() {
    39         return this.element.toString();
    40     }
    41 }

![复制代码][copycode.gif]

(2)Stack.java:

![复制代码][copycode.gif]

1 //栈接口
     2 public interface Stack {
     3 
     4     //入栈
     5     public void push(Object obj) throws Exception;
     6 
     7     //出栈
     8     public Object pop() throws Exception;
     9 
    10     //获得栈顶元素
    11     public Object getTop() throws Exception;
    12 
    13     //判断栈是否为空
    14     public boolean isEmpty();
    15 }

![复制代码][copycode.gif]

(3)LinkStack.java:

![复制代码][copycode.gif]

1 public class LinkStack implements Stack {
     2 
     3     Node head;  //栈顶指针
     4     int size;  //结点的个数
     5 
     6     public LinkStack() {
     7         head = null;
     8         size = 0;
     9     }
    10 
    11     @Override
    12     public Object getTop() throws Exception {
    13         // TODO Auto-generated method stub
    14         return head.getElement();
    15     }
    16 
    17     @Override
    18     public boolean isEmpty() {
    19         // TODO Auto-generated method stub
    20         return head == null;
    21     }
    22 
    23     @Override
    24     public Object pop() throws Exception {
    25         // TODO Auto-generated method stub
    26         if (isEmpty()) {
    27             throw new Exception("栈为空！");
    28         }
    29         Object obj = head.getElement();
    30         head = head.getNext();
    31         size--;
    32         return obj;
    33     }
    34 
    35     @Override
    36     public void push(Object obj) throws Exception {
    37         // TODO Auto-generated method stub
    38         head = new Node(obj, head);
    39         size++;
    40     }

![复制代码][copycode.gif]

(4)Test.java:测试类

![复制代码][copycode.gif]

1 import java.util.Scanner;
     2 
     3 public class Test {
     4 
     5     public static void main(String[] args) throws Exception {
     6         //SequenceStack stack = new SequenceStack(10);
     7         LinkStack stack = new LinkStack();
     8         Scanner in = new Scanner(System.in);
     9         int temp;
    10         for (int i = 0; i < 10; i++) {
    11             System.out.println("请输入第" + (i + 1) + "个整数：");
    12             temp = in.nextInt();
    13             stack.push(temp);
    14         }
    15         //遍历输出
    16         while (!stack.isEmpty()) {
    17             System.out.println(stack.pop());
    18         }
    19     }
    20 }

![复制代码][copycode.gif]

运行效果：

[![342f95fa-7e65-40cb-8bc5-599022308993][]][342f95fa-7e65-40cb-8bc5-599022308993 1]

七、堆栈的应用:

堆栈是各种软件系统中应用最广泛的数据结构之一。括号匹配和表达式计算是编译软件中的基本问题，其软件设计中都需要使用堆栈。

*  括号匹配问题
 *  表达式计算

1、括号匹配问题：

假设算术表达式中包含圆括号，方括号，和花括号三种类型。使用栈数据结构编写一个算法判断表达式中括号是否正确匹配，并设计一个主函数测试。

比如：

> \{a+\[b+(c\*a)/(d-e)\]\} 正确
> 
> (\[a+b)-(c\*e)\]+\{a+b\} 错误，中括号的次序不对

括号匹配有四种情况：

> 1.左右括号匹配次序不正确
> 
> 2.右括号多于左括号
> 
> 3.左括号多于右括号
> 
> 4.匹配正确

下面我们就通过代码把这四种情况列举出来。

代码实现：

![复制代码][copycode.gif]

1 public class Test {
     2 
     3     //方法：将字符串转化为字符串数组
     4     public static String[] expToStringArray(String exp) {
     5         int n = exp.length();
     6         String[] arr = new String[n];
     7         for (int i = 0; i < arr.length; i++) {
     8             arr[i] = exp.substring(i, i + 1);
     9         }
    10         return arr;
    11     }
    12 
    13     //方法：括号匹配问题的检测
    14     public static void signCheck(String exp) throws Exception {
    15         SequenceStack stack = new SequenceStack();
    16         String[] arr = Test.expToStringArray(exp);
    17         for (int i = 0; i < arr.length; i++) {
    18             if (arr[i].equals("(") || arr[i].equals("[") || arr[i].equals("{")) { //当碰到都是左边的括号的时候，统统压进栈
    19                 stack.push(arr[i]);
    20             } else if (arr[i].equals(")") && !stack.isEmpty() && stack.getTop().equals("(")) { //当碰到了右小括号时，如果匹配正确，就将左小括号出栈
    21                 stack.pop();
    22             } else if (arr[i].equals(")") && !stack.isEmpty() && !stack.getTop().equals("(")) {
    23                 System.out.println("左右括号匹配次序不正确！");
    24                 return;
    25             } else if (arr[i].equals("]") && !stack.isEmpty() && stack.getTop().equals("[")) {
    26                 stack.pop();
    27             } else if (arr[i].equals("]") && !stack.isEmpty() && !stack.getTop().equals("[")) {
    28                 System.out.println("左右括号匹配次序不正确！");
    29                 return;
    30             } else if (arr[i].equals("}") && !stack.isEmpty() && stack.getTop().equals("{")) {
    31                 stack.pop();
    32             } else if (arr[i].equals("}") && !stack.isEmpty() && !stack.getTop().equals("{")) {
    33                 System.out.println("左右括号匹配次序不正确！");
    34                 return;
    35             } else if (arr[i].equals(")") || arr[i].equals("]") || arr[i].equals("}") && stack.isEmpty()) {
    36                 System.out.println("右括号多于左括号！");
    37                 return;
    38             }
    39         }
    40         if (!stack.isEmpty()) {
    41             System.out.println("左括号多于右括号！");
    42         } else {
    43             System.out.println("括号匹配正确！");
    44         }
    45     }
    46 
    47 
    48     public static void main(String[] args) throws Exception {
    49 
    50         String str = "([(a+b)-(c*e)]+{a+b}";
    51         //括号匹配的检测
    52         Test.signCheck(str);
    53     }
    54 }

![复制代码][copycode.gif]

运行效果：

[![1c921aae-8a2e-4b70-bf4a-caf812781afc][]][1c921aae-8a2e-4b70-bf4a-caf812781afc 1]

上方代码中，第50行是一个错误的括号表达式，于是运行结果也很明显了。

2、表达式计算：

比如：

3+(6-4/2)\*5=23

其后缀表达式为：3642/-5\*+\# (\#符号为结束符)

现在要做的是：

使用链式堆栈，设计一个算法计算表达式，当我们输入后缀表达式后，能输出运行结果。

代码实现：

![复制代码][copycode.gif]

1 public class Test {
     2 
     3     //方法：使用链式堆栈，设计一个算法计算表达式
     4     public static void expCaculate(LinkStack stack) throws Exception {
     5         char ch; //扫描每次输入的字符。
     6         int x1, x2, b = 0; //x1,x2:两个操作数 ，b字符的ASCII码
     7         System.out.println("输入后缀表达式并以#符号结束:");
     8         while ((ch = (char) (b = System.in.read())) != '#') {
     9             //如果是数字，说明是操作数则压入堆栈
    10             if (Character.isDigit(ch)) {
    11                 stack.push(new Integer(Character.toString(ch)));
    12             }
    13             //如果不是数字，说明是运算符
    14             else {
    15                 x2 = ((Integer) stack.pop()).intValue();
    16                 x1 = ((Integer) stack.pop()).intValue();
    17                 switch (ch) {
    18                     case '+':
    19                         x1 += x2;
    20                         break;
    21                     case '-':
    22                         x1 -= x2;
    23                         break;
    24                     case '*':
    25                         x1 *= x2;
    26                         break;
    27                     case '/':
    28                         if (x2 == 0) {
    29                             throw new Exception("分母不能为零！");
    30                         } else {
    31                             x1 /= x2;
    32                         }
    33                         break;
    34                 }
    35                 stack.push(new Integer(x1));
    36             }
    37         }
    38         System.out.println("后缀表达式计算结果是：" + stack.getTop());
    39     }
    40 
    41     public static void main(String[] args) throws Exception {
    42         LinkStack stack = new LinkStack();
    43         //(2+3)*(3-1)/2=5的后缀表达式为：23+31-*2/
    44         //方法：键盘输入后缀表达式，输出的得到计算结果
    45         Test.expCaculate(stack);
    46 
    47     }
    48 }

![复制代码][copycode.gif]

运行效果：

[![196bd089-8fad-4256-bcda-a9a4ab4acc20][]][196bd089-8fad-4256-bcda-a9a4ab4acc20 1]

[http_www.cnblogs.com_smyhvae_p_4789699.html]: http://www.cnblogs.com/smyhvae/p/4789699.html
[42c4b8c6-f428-468d-b5aa-2cf9f4ae86e2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/0277d64bdde44e0b918d2a8ff8da8c3a.png
[42c4b8c6-f428-468d-b5aa-2cf9f4ae86e2 1]: http://images2015.cnblogs.com/blog/641601/201509/641601-20150907185827247-2106944626.png
[copycode.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/017964512b2c449d9cf404dcc5b81a75.png
[9fd3385e-ab5b-4fc1-852f-4afe8ec9b304]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/2ba58d18a733405498b00a7e7017c5a9.png
[9fd3385e-ab5b-4fc1-852f-4afe8ec9b304 1]: http://images2015.cnblogs.com/blog/641601/201509/641601-20150907185828215-536681209.png
[44298c1d-2054-4dd5-be7d-1f7e4cd5f43f]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/a2f33fb81d6a446193669a719d489f5c.png
[44298c1d-2054-4dd5-be7d-1f7e4cd5f43f 1]: http://images2015.cnblogs.com/blog/641601/201509/641601-20150907185829325-76904098.png
[342f95fa-7e65-40cb-8bc5-599022308993]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/1f4185260f314059ba277bcb0eb0e49c.png
[342f95fa-7e65-40cb-8bc5-599022308993 1]: http://images2015.cnblogs.com/blog/641601/201509/641601-20150907185830340-951716340.png
[1c921aae-8a2e-4b70-bf4a-caf812781afc]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/9af2c269edaa4ac9afdae81535d2c011.png
[1c921aae-8a2e-4b70-bf4a-caf812781afc 1]: http://images2015.cnblogs.com/blog/641601/201509/641601-20150907185831387-1451386123.png
[196bd089-8fad-4256-bcda-a9a4ab4acc20]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/0f04f9ffa3964158a85b91c9d0d74e42.png
[196bd089-8fad-4256-bcda-a9a4ab4acc20 1]: http://images2015.cnblogs.com/blog/641601/201509/641601-20150907185832294-2138659298.png