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

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

一、堆栈的基本概念:

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

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

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

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

数据集合:

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

操作集合:

(1)入栈push(obj):把数据元素obj插入堆栈。

(2)出栈pop():出栈, 删除的数据元素由函数返回。

(3)取栈顶数据元素getTop():取堆栈当前栈顶的数据元素并由函数返回。

(4)非空否notEmpty():若堆栈非空则函数返回true,否则函数返回false。

三、顺序栈:

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

1、顺序栈的实现:

(1)设计Stack接口

(2)实现SequenceStack类

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

代码实现:

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

 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 }

 

(2)SequenceStack.java:

 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 }

2、测试类:

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

代码实现:

(3)Test.java:

 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 }

运行效果:

四、Java中栈与堆的区别:

栈(stack):(线程私有)

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

堆(heap):(线程共享)

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

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

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

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

总结一句:不同的对象可能会有相同的hashCode;但是如果hashCode不同,那肯定不是同一个对象

代码举例:

 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 }

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

六、链式堆栈:

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

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

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

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

1、设计链式堆栈:

(1)Node.java:结点类

 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 }

(2)Stack.java:

 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 }

(3)LinkStack.java:

 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     }

(4)Test.java:测试类

 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 }

运行效果:

七、堆栈的应用:

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

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

1、括号匹配问题:

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

比如:

{a+[b+(c*a)/(d-e)]}    正确

([a+b)-(c*e)]+{a+b}    错误,中括号的次序不对

括号匹配有四种情况:

1.左右括号匹配次序不正确

2.右括号多于左括号

3.左括号多于右括号

4.匹配正确

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

代码实现:

 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 }

运行效果:

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

2、表达式计算:

比如:

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

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

现在要做的是:

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

代码实现:

 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 }

运行效果:

时间: 09-08

数据结构Java实现05----栈:顺序栈和链式堆栈的相关文章

数据结构_线性表的顺序表示和链式表示

/********************************************************************************************************************/ 声明: (1)*.h文件是代码声明, *.cpp文件是代码实现; (2)一般头文件的内容有: ①类型声明; ②函数声明; ③枚举; ④常量; ⑤宏 (3)以下说明是为了方便代码文件的管理而设定的一些规则, 以后代码都会按照此规则编写: 1)Pubuse.h 是几

顺序队列和链式队列的实现

队列是一种常用的数据结构,它跟栈一样,操作都受到限制,队列只允许从一端进数据,另一端出数据.队列跟栈不同,栈是一种"后进先出"的模式,而队列是一种"先进先出"的操作模式.就好比日常排队一样,先排队的先出,后排队的后出.例如,进入队列的顺序是1,2,3,4,5则出队列的顺序是1,2,3,4,5(只考虑一次性出列的情况). 队列也分顺序队列和链式队列,跟顺序栈和链表栈一样,顺序队列同样是基于数组实现,链式队列则是基于链表实现. 顺序队列: //顺序队列 #include

数据结构(C实现)------- 顺序栈

栈是限定仅在表的一端进行插入或删除的纯属表,通常称允许插入,删除的一端为栈顶(Top),相应在的,则称另一端为栈底(Bottom).不含元素的栈则称为空栈. 所设栈S={a1,a2,a3,...,an},则称a1为栈底元素,an为栈顶元素.根据栈的定义可知,栈顶元素总是最后入栈并且最先出栈的:栈底元素总是最先入栈并且最后出栈的.即栈是按后进先出的原则进行的.因此,栈又称为后进先出(LIFO)的线性表. 而顺序栈,即栈的顺序存储结构.它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同

栈的顺序结构和链式结构实现

1.栈的顺序存储<数组实现> 1.1.栈的接口 1 package com.neusoft.stack; 2 3 public interface IStack { 4 //1.栈置空 5 public void clear(); 6 //2.栈判空 7 public boolean isEmpty(); 8 //3.栈长度 9 public int length(); 10 //4.取栈顶元素 11 public Object peek(); 12 //5.移除栈顶元素-----出栈 13

数据结构之第二章线性表之静态链式存储

1--特点:用一维数组来描述线性表,用游标代替指针指示节点在数组中的相对位置.不设“指针”类型的高级语言中适用链表结构. 2--线性表的静态链式存储结构 ////  静态单链表.h//  单链表的静态存储//// 6 //  Copyright (c) 2014年 dashuai. All rights reserved.// #ifndef SLIST_H#define SLIST_H#include <stdio.h>#include <stdlib.h> #define MA

数据结构之自建算法库——二叉树的链式存储及基本运算

本文是数据结构基础系列(6):树和二叉树中第9课时二叉树的基本运算及其实现的例程. 单链表算法库算法库采用程序的多文件组织形式,包括两个文件: 1.头文件:btree.h,包含定义顺序表数据结构的代码.宏定义.要实现算法的函数的声明: #ifndef BTREE_H_INCLUDED #define BTREE_H_INCLUDED #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; //

C 数据结构1——线性表分析(顺序存储、链式存储)

之前是由于学校工作室招新,跟着大伙工作室招新训练营学习数据结构,那个时候,纯碎是小白(至少比现在白很多)那个时候,学习数据结构,真的是一脸茫然,虽然写出来了,但真的不知道在干嘛.调试过程中,各种bug也不懂怎么修改,那个时候,电脑一直被我弄蓝屏,这个寒假,重新学习一遍数据结构,获益良多,整理一下,发布出来,求拍砖,共同进步. 线性表(List),0个或者多个数据元素的有限序列 线性表的顺序存储,即线性表通过数组的方式实现,指用一段地址连续的存储单元一次存储线性表的数据元素.如图: A1 A2 -

数据结构之栈(1)——顺序栈

栈作为一种特殊的线性表,在计算机中有顺序储存结构和链式存储结构两种存储结构,根据这个我们把栈分为顺序栈和链栈 顺序栈 栈顶:用top来动态地表示栈顶元素在顺序栈中的位置,当top=-1时表示栈为空 这个是栈这个数据类型的定义 typedef char ElemTypeStack; typedef struct{ ElemTypeStack elem[MAXSIZE]; int top; }FirStack; 用一个数组来存储数据,对应的下标表示他在栈中的位置,top表示栈顶元素对应的下标,若栈为

Java实现链式存储的二叉树

二叉树的定义: 二叉树(BinaryTree)是n(n≥0)个结点的有限集,它或者是空集(n=0),或者由一个根结点及两棵互不相交的.分别称作这个根的左子树和右子树的二叉树组成. 二叉树的遍历方式主要有:先序遍历(NLR),中序遍历(LNR),后序遍历(LRN),和层次遍历. 注意: 由二叉树的先序序列和中序序列可以唯一地确定一颗二叉树: 由二叉树的后序序列和中序序列可以唯一地确定一颗二叉树: 由二叉树的层序序列和中序序列可以唯一地确定一棵二叉树: 但,由二叉树的先序序列和后序序列无法唯一地确定