Java数据结构和算法(四)——栈

Wesley13
• 阅读 718

前面我们讲解了数组,数组更多的是用来进行数据的存储,纯粹用来存储数据的数据结构,我们期望的是插入、删除和查找性能都比较好。对于无序数组,插入快,但是删除和查找都很慢,为了解决这些问题,后面我们会讲解比如二叉树、哈希表的数据结构。

  而本篇博客讲解的数据结构和算法更多是用作程序员的工具,它们作为构思算法的辅助工具,而不是完全的数据存储工具。这些数据结构的生命周期比数据库类型的结构要短得多,在程序执行期间它们才被创建,通常用它们去执行某项特殊的业务,执行完成之后,它们就被销毁。这里的它们就是——栈和队列。本篇博客我们先介绍栈。

1、栈的基本概念

  (英语:stack)又称为堆****栈堆叠,栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。

  栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。

  由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。栈也称为后进先出表。

  这里以羽毛球筒为例,羽毛球筒就是一个栈,刚开始羽毛球筒是空的,也就是空栈,然后我们一个一个放入羽毛球,也就是一个一个push进栈,当我们需要使用羽毛球的时候,从筒里面拿,也就是pop出栈,但是第一个拿到的羽毛球是我们最后放进去的。

2、Java模拟简单的顺序栈实现

  Java数据结构和算法(四)——栈

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

package com.ys.datastructure;

public class MyStack {

private int``[] array;

private int maxSize;

private int top;

public MyStack(``int size){

this``.maxSize = size;

array = new int``[size];

top = -``1``;

}

//压入数据

public void push(``int value){

if``(top < maxSize-``1``){

array[++top] = value;

}

}

//弹出栈顶数据

public int pop(){

return array[top--];

}

//访问栈顶数据

public int peek(){

return array[top];

}

//判断栈是否为空

public boolean isEmpty(){

return (top == -``1``);

}

//判断栈是否满了

public boolean isFull(){

return (top == maxSize-``1``);

}

}

  测试:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

package com.ys.test;

import com.ys.datastructure.MyStack;

public class MyStackTest {

public static void main(String[] args) {

MyStack stack = new MyStack(``3``);

stack.push(``1``);

stack.push(``2``);

stack.push(``3``);

System.out.println(stack.peek());

while``(!stack.isEmpty()){

System.out.println(stack.pop());

}

}

}

  结果:

  Java数据结构和算法(四)——栈

  这个栈是用数组实现的,内部定义了一个数组,一个表示最大容量的值以及一个指向栈顶元素的top变量。构造方法根据参数规定的容量创建一个新栈,push()方法是向栈中压入元素,指向栈顶的变量top加一,使它指向原顶端数据项上面的一个位置,并在这个位置上存储一个数据。pop()方法返回top变量指向的元素,然后将top变量减一,便移除了数据项。要知道 top 变量指向的始终是栈顶的元素。

  产生的问题:

①、上面栈的实现初始化容量之后,后面是不能进行扩容的(虽然栈不是用来存储大量数据的),如果说后期数据量超过初始容量之后怎么办?(自动扩容

②、我们是用数组实现栈,在定义数组类型的时候,也就规定了存储在栈中的数据类型,那么同一个栈能不能存储不同类型的数据呢?(声明为Object)

③、栈需要初始化容量,而且数组实现的栈元素都是连续存储的,那么能不能不初始化容量呢?(改为由链表实现)

3、增强功能版栈

对于上面出现的问题,第一个能自动扩容,第二个能存储各种不同类型的数据,解决办法如下:(第三个在讲链表的时候在介绍)

这个模拟的栈在JDK源码中,大家可以参考 Stack 类的实现。

Java数据结构和算法(四)——栈

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

package com.ys.datastructure;

import java.util.Arrays;

import java.util.EmptyStackException;

public class ArrayStack {

//存储元素的数组,声明为Object类型能存储任意类型的数据

private Object[] elementData;

//指向栈顶的指针

private int top;

//栈的总容量

private int size;

//默认构造一个容量为10的栈

public ArrayStack(){

this``.elementData = new Object[``10``];

this``.top = -``1``;

this``.size = 10``;

}

public ArrayStack(``int initialCapacity){

if``(initialCapacity < 0``){

throw new IllegalArgumentException(``"栈初始容量不能小于0: "``+initialCapacity);

}

this``.elementData = new Object[initialCapacity];

this``.top = -``1``;

this``.size = initialCapacity;

}

//压入元素

public Object push(Object item){

//是否需要扩容

isGrow(top+``1``);

elementData[++top] = item;

return item;

}

//弹出栈顶元素

public Object pop(){

Object obj = peek();

remove(top);

return obj;

}

//获取栈顶元素

public Object peek(){

if``(top == -``1``){

throw new EmptyStackException();

}

return elementData[top];

}

//判断栈是否为空

public boolean isEmpty(){

return (top == -``1``);

}

//删除栈顶元素

public void remove(``int top){

//栈顶元素置为null

elementData[top] = null``;

this``.top--;

}

/**

* 是否需要扩容,如果需要,则扩大一倍并返回true,不需要则返回false

* [@param](https://my.oschina.net/u/2303379) minCapacity

* [@return](https://my.oschina.net/u/556800)

*/

public boolean isGrow(``int minCapacity){

int oldCapacity = size;

//如果当前元素压入栈之后总容量大于前面定义的容量,则需要扩容

if``(minCapacity >= oldCapacity){

//定义扩大之后栈的总容量

int newCapacity = 0``;

//栈容量扩大两倍(左移一位)看是否超过int类型所表示的最大范围

if``((oldCapacity<<``1``) - Integer.MAX_VALUE >``0``){

newCapacity = Integer.MAX_VALUE;

}``else``{

newCapacity = (oldCapacity<<``1``);``//左移一位,相当于*2

}

this``.size = newCapacity;

int``[] newArray = new int``[size];

elementData = Arrays.copyOf(elementData, size);

return true``;

}``else``{

return false``;

}

}

}

  测试:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

//测试自定义栈类 ArrayStack

//创建容量为3的栈,然后添加4个元素,3个int,1个String.

[@Test](https://my.oschina.net/azibug)

public void testArrayStack(){

ArrayStack stack = new ArrayStack(``3``);

stack.push(``1``);

//System.out.println(stack.peek());

stack.push(``2``);

stack.push(``3``);

stack.push(``"abc"``);

System.out.println(stack.peek());

stack.pop();

stack.pop();

stack.pop();

System.out.println(stack.peek());

}

  结果:

  Java数据结构和算法(四)——栈

4、利用栈实现字符串逆序

  我们知道栈是后进先出,我们可以将一个字符串分隔为单个的字符,然后将字符一个一个push()进栈,在一个一个pop()出栈就是逆序显示了。如下:

  将 字符串“how are you” 反转!!!

  ps:这里我们是用上面自定的栈来实现的,大家可以将ArrayStack替换为JDK自带的栈类Stack试试

1

2

3

4

5

6

7

8

9

10

11

12

13

//进行字符串反转

[@Test](https://my.oschina.net/azibug)

public void testStringReversal(){

ArrayStack stack = new ArrayStack();

String str = "how are you"``;

char``[] cha = str.toCharArray();

for``(``char c : cha){

stack.push(c);

}

while``(!stack.isEmpty()){

System.out.print(stack.pop());

}

}

  结果:

  Java数据结构和算法(四)——栈

5、利用栈判断分隔符是否匹配

  写过xml标签或者html标签的,我们都知道<必须和最近的>进行匹配,[ 也必须和最近的 ] 进行匹配。

  比如:<abc[123]abc>这是符号相匹配的,如果是 <abc[123>abc] 那就是不匹配的。

  对于 12<a[b{c}]>,我们分析在栈中的数据:遇到匹配正确的就消除

  Java数据结构和算法(四)——栈

  最后栈中的内容为空则匹配成功,否则匹配失败!!!

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

//分隔符匹配

//遇到左边分隔符了就push进栈,遇到右边分隔符了就pop出栈,看出栈的分隔符是否和这个有分隔符匹配

[@Test](https://my.oschina.net/azibug)

public void testMatch(){

ArrayStack stack = new ArrayStack(``3``);

String str = "12<a[b{c}]>"``;

char``[] cha = str.toCharArray();

for``(``char c : cha){

switch (c) {

case '{'``:

case '['``:

case '<'``:

stack.push(c);

break``;

case '}'``:

case ']'``:

case '>'``:

if``(!stack.isEmpty()){

char ch = stack.pop().toString().toCharArray()[``0``];

if``(c==``'}' && ch != '{'

|| c==``']' && ch != '['

|| c==``')' && ch != '('``){

System.out.println(``"Error:"``+ch+``"-"``+c);

}

}

break``;

default``:

break``;

}

}

}

6、总结

  根据栈后进先出的特性,我们实现了单词逆序以及分隔符匹配。所以其实栈是一个概念上的工具,具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop(),使得程序不容易出错。

  对于栈的实现,我们稍微分析就知道,数据入栈和出栈的时间复杂度都为O(1),也就是说栈操作所耗的时间不依赖栈中数据项的个数,因此操作时间很短。而且需要注意的是栈不需要比较和移动操作,我们不要画蛇添足。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
Java数据结构和算法(二)——数组
  上篇博客我们简单介绍了数据结构和算法的概念,对此模糊很正常,后面会慢慢通过具体的实例来介绍。本篇博客我们介绍数据结构的鼻祖——数组,可以说数组几乎能表示一切的数据结构,在每一门编程语言中,数组都是重要的数据结构,当然每种语言对数组的实现和处理也不相同,但是本质是都是用来存放数据的的结构,这里我们以Java语言为例,来详细介绍Java语言中数组的用法。
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
8个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这