栈是一种受限的线性表,在数据结构中也很常见。 下面,时光采用漫画的形式来说一说这个栈。
在这里插入图片描述
栈是一种受限线性表,也就是说,栈元素具有线性关系,即前驱后继关系; 只不过它是 一种特殊的线性表而已;
在这里插入图片描述
如图:
线性表是在表尾进行插入和删除操作,而在栈中表尾是指栈顶,而不是栈底; 栈是在栈顶进行数据操作,即先进后出,后进先出;
顺序栈:
栈的顺序存储结构简称顺序栈; 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素; 同时附设指针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}
运行结果: