漫画趣解——栈

程序员的时光001

发布于 2020-07-14 14:53:32

3450

发布于 2020-07-14 14:53:32

文章被收录于专栏：程序员的时光

写在前面：

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

思维导图：

什么是栈？

在这里插入图片描述

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

栈的特性？

在这里插入图片描述

如图：

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

顺序栈和链栈

代码实现

顺序栈：

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

1，先写实体类SeqStack；

属性有栈的容量，结点数据以及栈的实际大小（即长度）

 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；

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

 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；

包括主函数，来测试栈的各种方法；

 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型的

 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}

 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；

包括入栈，出栈等方法；

 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，主函数；

主函数，包括测试链栈的方法；

 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}

运行结果：