前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >漫画趣解——栈

漫画趣解——栈

作者头像
程序员的时光001
发布2020-07-14 14:53:32
3450
发布2020-07-14 14:53:32
举报
文章被收录于专栏:程序员的时光

写在前面:

栈是一种受限的线性表,在数据结构中也很常见。 下面,时光采用漫画的形式来说一说这个栈。

思维导图:

什么是栈?

在这里插入图片描述

栈是一种受限线性表,也就是说,栈元素具有线性关系,即前驱后继关系; 只不过它是 一种特殊的线性表而已;

栈的特性?

在这里插入图片描述

如图:

线性表是在表尾进行插入和删除操作,而在栈中表尾是指栈顶,而不是栈底; 栈是在栈顶进行数据操作,即先进后出,后进先出

顺序栈和链栈

代码实现

顺序栈:

栈的顺序存储结构简称顺序栈; 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素; 同时附设指针top指示栈顶元素在顺序表中的位置;

1,先写实体类SeqStack;

属性有栈的容量,结点数据以及栈的实际大小(即长度)

代码语言:javascript
复制
 1package com.java.model;
 2
 3public class SeqStack {
 4    //动态数组的最大容量
 5    public final static int Max_Size=1024;
 6
 7    //栈的结点数据
 8    public Object[] data;
 9    //栈的长度,用来标识数组中的元素个数
10    public int size;
11
12    //构造函数
13    public SeqStack(Object[] data, int size) {
14        this.data = data;
15        this.size = size;
16    }
17}

2,写栈的方法类SeqStackDao;

包括入栈、出栈、查看栈顶元素等等;

代码语言:javascript
复制
 1package com.java.dao;
 2
 3import com.java.model.SeqStack;
 4
 5import static com.java.model.SeqStack.Max_Size;
 6
 7public class SeqStackDao {
 8    //初始化栈
 9    public SeqStack Init_SeqStack(){
10        //动态数组初始化,加数组容量
11        Object[] data1=new Object[Max_Size];
12
13        //栈初始化,元素个数size为0
14        SeqStack stack=new SeqStack(data1,0);
15
16        //数组赋值
17        for(int i=0;i<Max_Size;i++){
18            stack.data[i]=0;
19        }
20        return stack;
21    }
22    //入栈
23    public void Push_SeqStack(SeqStack stack,Object data){
24        if(stack==null){
25            return;
26        }
27        if(data==null){
28            return;
29        }
30        //如果栈容量小于或等于数组容量
31        if(stack.size==Max_Size){
32            return;
33        }
34        //元素入栈
35        stack.data[stack.size]=data;
36        stack.size++;
37    }
38    //查找栈顶元素
39    public Object Top_SeqStack(SeqStack stack){
40        if(stack==null){
41            return null;
42        }
43        //若栈元素为0,则返回null
44        if(stack.size==0){
45            return null;
46        }
47        //栈顶元素,注意数组下标从0开始,所以要减1
48        Object o=stack.data[stack.size-1];
49        return o;
50    }
51    //出栈操作
52    public void Pop_SeqStack(SeqStack stack){
53        if(stack==null){
54            return;
55        }
56        if(stack.size==0){
57            return;
58        }
59        //出栈
60        stack.size--;
61    }
62    //判断是否为空
63    public boolean IsEmpty(SeqStack stack){
64        if(stack==null){
65            return false;
66        }
67        if(stack.size==0){
68            return true;
69        }
70        return false;
71    }
72    //返回栈中元素的个数
73    public int Size_SeqStack(SeqStack stack){
74        return stack.size;
75    }
76    //清空栈
77    public void Clear_SeqStack(SeqStack stack){
78        if(stack==null){
79            return;
80        }
81        for(int i=0;i<stack.size;i++){
82            stack.data[i]=null;
83        }
84        stack.size=0;
85    }
86}

3,主函数Main;

包括主函数,来测试栈的各种方法;

代码语言:javascript
复制
 1package com.java.main;
 2
 3import com.java.dao.SeqStackDao;
 4import com.java.model.SeqStack;
 5
 6public class SeqStackMain {
 7    public static void main(String[] args) {
 8        SeqStackDao seqStackDao=new SeqStackDao();
 9        //初始化栈
10        SeqStack stack=seqStackDao.Init_SeqStack();
11
12        //入栈
13        seqStackDao.Push_SeqStack(stack,"A");
14        seqStackDao.Push_SeqStack(stack,"B");
15        seqStackDao.Push_SeqStack(stack,"C");
16        seqStackDao.Push_SeqStack(stack,"D");
17        seqStackDao.Push_SeqStack(stack,"E");
18
19        //输出栈元素
20        while(stack.size>0) {
21            //查找栈顶元素
22            Object o = seqStackDao.Top_SeqStack(stack);
23            System.out.println(o);
24            //出栈
25            seqStackDao.Pop_SeqStack(stack);
26        }
27    }
28}

运行结果:

链栈:

栈的链式存储简称链栈; 存储结构类似于链表;

1,先写实体类LinkStackNode和LinkStack;

LinkStackNode: 包括链栈结点的数据域和指针域; 数据域是Object类型的,指针域是LinkStackNode类型的 LinkStack: 包括链栈的栈顶指针链表元素个数; 栈顶指针是LinkStackNode类型的,链栈元素个数是int型的

代码语言:javascript
复制
 1package com.java.model;
 2
 3public class LinkStackNode {
 4    //栈结点的数据域
 5    public Object data;
 6    //栈结点的指针
 7    public LinkStackNode next;
 8
 9    //构造方法
10    public LinkStackNode(Object data, LinkStackNode next) {
11        this.data = data;
12        this.next = next;
13    }
14}
代码语言:javascript
复制
 1package com.java.model;
 2
 3public class LinkStack {
 4    //栈顶指针,也就是所谓的头结点
 5    public LinkStackNode head;
 6    //栈的容量
 7    public int size;
 8
 9    public LinkStack(LinkStackNode head, int size) {
10        this.head = head;
11        this.size = size;
12    }
13}

2,写链栈的方法类LinkStackDao;

包括入栈,出栈等方法;

代码语言:javascript
复制
 1package com.java.dao;
 2
 3import com.java.model.LinkStack;
 4import com.java.model.LinkStackNode;
 5
 6public class LinkStackDao {
 7    //初始化栈
 8    public LinkStack Init_LinkStack(){
 9        //初始化栈顶指针
10        LinkStackNode head=new LinkStackNode(0,null);
11        //初始化栈
12        LinkStack stack=new LinkStack(head,0);
13
14        return stack;
15    }
16
17    //入栈
18    public void Push_LinkStack(LinkStack stack,Object data){
19        if (stack == null){
20            return;
21        }
22        if (data == null){
23            return;
24        }
25        //创建新插入的结点,也就是栈顶指针后面的第一个元素,因为只能在栈顶进行元素插入或删除
26        LinkStackNode newNode=new LinkStackNode(data,null);
27        //进入插入操作
28        newNode.next=stack.head.next;
29        //栈顶指针的next等于新插入结点
30        stack.head.next=newNode;
31        //栈容量加1
32        stack.size++;
33    }
34
35    //出栈
36    public void Pop_LinkStack(LinkStack stack){
37        if (stack == null){
38            return;
39        }
40        if (stack.size == 0){
41            return;
42        }
43        //删除栈顶指针后面的第一个元素
44        stack.head.next=stack.head.next.next;
45        //栈容量减1
46        stack.size--;
47    }
48
49    //返回栈顶元素
50    public Object Top_LinkStack(LinkStack stack){
51        if (stack == null){
52            return null;
53        }
54        if (stack.size == 0){
55            return null;
56        }
57        //栈顶元素也就是栈顶指针后面的第一个元素
58        return stack.head.next.data;
59    }
60
61    //返回栈容量,也就是栈元素个数
62    public int Size_LinkStack(LinkStack stack){
63        if (stack == null){
64            return -1;
65        }
66        return stack.size;
67    }
68
69    //清空栈
70    public void Clear_LinkStack(LinkStack stack){
71        if (stack == null){
72            return ;
73        }
74        stack.head.next=null;
75        stack.size=0;
76    }
77}

3,主函数;

主函数,包括测试链栈的方法;

代码语言:javascript
复制
 1package com.java.main;
 2
 3import com.java.dao.LinkStackDao;
 4import com.java.model.LinkStack;
 5
 6public class LinkStackMain {
 7    public static void main(String[] args) {
 8        LinkStackDao linkStackDao=new LinkStackDao();
 9        //初始化栈
10        LinkStack stack=linkStackDao.Init_LinkStack();
11
12        //入栈
13        linkStackDao.Push_LinkStack(stack,"A");
14        linkStackDao.Push_LinkStack(stack,"B");
15        linkStackDao.Push_LinkStack(stack,"C");
16        linkStackDao.Push_LinkStack(stack,"D");
17        linkStackDao.Push_LinkStack(stack,"E");
18
19        //输出栈元素
20        while(stack.size>0){
21            //查找栈顶元素
22            Object o=linkStackDao.Top_LinkStack(stack);
23            System.out.println(o);
24            //出栈
25            linkStackDao.Pop_LinkStack(stack);
26        }
27    }
28}

运行结果:

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-03-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员的时光 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 写在前面:
  • 思维导图:
    • 什么是栈?
      • 栈的特性?
        • 顺序栈和链栈
          • 代码实现
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档