数据结构——java实现栈
栈
定义：
栈是一种先进后出的数据结构，我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何元素的栈称为空栈
栈的java代码实现：
基于数组：
1 import org.junit.jupiter.api.Test;
2
3 /**
4 * 用数组实现栈
5 * @author wydream
6 *
7 */
8
9 public class ArrayStack<T> {
10
11 private T data[];
12 private int maxSize;
13 private int top;
14
15
16 //初始化栈
17 public ArrayStack(int maxSize) {
18 this.maxSize=maxSize;
19 data=(T[])new Object[maxSize];
20 this.top=-1;
21 }
22
23 //判断栈是否为空
24 public boolean isEmpty() {
25 return (top==-1);
26 }
27
28 //判断栈是否已经满了
29 public boolean isFull() {
30 return (top==maxSize-1);
31 }
32
33
34 //压栈
35 public boolean push(T value) {
36 if(isFull()) {
37 return false;
38 }
39 top++;
40 data[top]=value;
41 return true;
42 }
43
44
45 //取出栈顶元素
46 public T pop() {
47 if(isEmpty()) {
48 return null;
49 }
50 T tmp=data[top];
51 data[top]=null;
52 top--;
53 return tmp;
54 }
55
56 //============测试代码============
57 public static void main(String[] args) {
58 ArrayStack<String> as=new ArrayStack<String>(4);
59 as.push("anhui");
60 as.push("shanghai");
61 as.push("beijing");
62 as.push("nanj");
63 //测试栈已经满了的情况
64 System.out.println(as.push("aa"));
65 for(int i=0;i<4;i++) {
66 System.out.println(as.pop());
67 }
68 }
69
70 }基于链表：
1 import org.junit.jupiter.api.Test;
2
3 /**
4 * 基于链表实现的栈
5 * @author wydream
6 *
7 */
8
9 public class NodeStack<T> {
10
11 private Node<T> top=null;//栈顶
12 public NodeStack() {
13 this.top=null;
14 }
15
16 //判断栈是否为空
17 public boolean isEmpty() {
18 if(top!=null) {
19 return false;
20 }
21 return true;
22 }
23
24 //压栈
25 public boolean push(T value) {
26 Node<T> node=new Node<T>(value);
27 node.setNext(top);
28 top=node;
29 return true;
30 }
31
32 //出栈
33 public T pop() {
34 if(top==null) {
35 return null;
36 }
37 T tmp=top.data;
38 top=top.getNext();
39 return tmp;
40 }
41 //取出栈顶的值
42 public T peek() {
43 if(isEmpty()) {
44 return null;
45 }
46 return top.data;
47 }
48
49
50 class Node<T>{
51 private T data;//数据
52 private Node<T> next;//指向下一个节点的指针
53 //初始化链表
54 public Node(T data) {
55 this.data=data;
56 }
57 //获取下一个节点
58 public Node<T> getNext(){
59 return this.next;
60 }
61 //设置下一个节点
62 public void setNext(Node<T> n) {
63 this.next=n;
64 }
65 //获取节点数据
66 public T getData() {
67 return this.data;
68 }
69 //设置节点数据
70 public void setData(T d) {
71 this.data=d;
72 }
73
74 }
75
76 public static void main(String[] args) {
77
78 NodeStack<String> ns=new NodeStack<String>();
79
80 //测试是否为空
81 System.out.println("=======是否为空======");
82 System.out.println(ns.isEmpty());
83 System.out.println("=============");
84 //压栈测试
85 System.out.println("=======压栈======");
86 ns.push("北京");
87 ns.push("上海");
88 ns.push("深证");
89 ns.push("广州");
90 //是否为空
91 System.out.println("=======是否为空======");
92 System.out.println(ns.isEmpty());
93 System.out.println("=============");
94
95 System.out.println("=======出栈=======");
96 //出栈
97 System.out.println(ns.pop());
98 System.out.println(ns.pop());
99 System.out.println(ns.pop());
100 System.out.println(ns.pop());
101 System.out.println(ns.pop());
102
103 //是否为空
104 System.out.println("=======是否为空======");
105 System.out.println(ns.isEmpty());
106 System.out.println("=============");
107
108
109 }
110 }两栈共享空间：
栈有个缺陷，必须事先确定数组的大小，这样如果栈满了的话，想在存储元素就必须通过编程手段来扩充数组的容量，这样就很麻烦。于是我们就设计一个数组，里面存放着两个栈，共享这一个数组空间，这样就可以充分利用空间。数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的0下标，另一个栈的栈为数组的长度n-1处
代码实现：
1 import javax.crypto.Mac;
2
3 /**
4 * 两栈共享空间
5 * @author wydream
6 *
7 */
8
9 public class DoubleStatk {
10
11 private final static int MAXSIZE=20;
12 private int[] stackElem;
13 private int top1; //将top1设置为指向栈1栈顶元素的存储位置即数组下标0
14 private int top2; //将top2设置为指向栈2栈顶元素的存储位置即数组下标n-1
15
16 public DoubleStatk() {
17 top1=-1;
18 top2=MAXSIZE;
19 stackElem=new int[MAXSIZE];
20 }
21
22 //是否是空栈
23 public boolean isEmptyStack() {
24 if(top1==-1&&top2==MAXSIZE) {
25 return true;
26 }
27 return false;
28 }
29
30 //清空栈
31 public void clearStack() {
32 top1=-1;
33 top2=MAXSIZE;
34 }
35
36 //栈的长度
37 public int lengthStak() {
38 return (top1+1)+(MAXSIZE-top2);
39 }
40
41 //获取top1的元素
42 public int getTop1Elem() {
43 if(top1==-1) {
44 return -1;
45 }
46 return stackElem[top1];
47 }
48
49 //获取top2的元素
50 public int getTop2Elem() {
51 if(top2==MAXSIZE) {
52 return -1;
53 }
54 return stackElem[top2];
55 }
56
57 //压栈
58 public void stackPush(int stackNumber,int e) {
59 //如果栈已经满了
60 if(top1+1==top2) {
61 System.out.println("栈已满");
62 return;
63 }
64 if(stackNumber==1) {
65 top1+=1;
66 stackElem[top1]=e;
67 return;
68 }
69 if(stackNumber==2) {
70 top2-=1;
71 stackElem[top2]=e;
72 return;
73 }
74
75 }
76
77 //出栈
78 public int stackPop(int stackNumber) {
79 int rs;
80 if(isEmptyStack()) {
81 System.out.println("栈为空");
82 return -1;
83 }
84 if(stackNumber==1) {
85 rs= stackElem[top1];
86 top1--;
87 }else if(stackNumber==2) {
88 rs=stackElem[top2];
89 top2++;
90 }else {
91 System.out.println("输入数据有误");
92 return -1;
93 }
94 return rs;
95 }
96
97 public void stackTraverse() {
98 System.out.println("此时，栈中的元素为：");
99 int i=0;
100 while(i<=top1) {
101 System.out.println(stackElem[i++]+" ");
102 }
103 i=top2;
104 while(i<MAXSIZE) {
105 System.out.println(stackElem[i++]+" ");
106 }
107 System.out.println();
108 }
109
110
111 public static void main(String[] args) {
112 DoubleStatk seqStack=new DoubleStatk();
113
114 //1压栈
115 for(int j=1;j<=5;j++) {
116 seqStack.stackPush(1,j);
117 }
118 //2压栈
119 for(int i=MAXSIZE;i>=MAXSIZE-2;i--) {
120 seqStack.stackPush(2, i);
121 }
122 //输出
123 seqStack.stackTraverse();
124 System.out.println("栈的长度为："+seqStack.lengthStak());
125
126 seqStack.stackPop(2);
127 seqStack.stackTraverse();
128 System.out.println("栈1的栈顶元素为: " + seqStack.getTop1Elem());
129 System.out.println("栈2的栈顶元素为: " + seqStack.getTop2Elem());
130 System.out.println("栈的长度为: " + seqStack.lengthStak());
131
132 for (int i = 6; i <= MAXSIZE-2; i++) {
133 seqStack.stackPush(1,i);
134 }
135 seqStack.stackTraverse();
136 System.out.println("栈1的栈顶元素为: " + seqStack.getTop1Elem());
137 System.out.println("栈2的栈顶元素为: " + seqStack.getTop2Elem());
138 System.out.println("栈顶元素为: " + seqStack.getTop2Elem());
139 System.out.println("栈的长度为: " + seqStack.lengthStak());
140
141 System.out.println("栈是否为空: " + seqStack.isEmptyStack());
142 seqStack.clearStack();
143 System.out.println("栈是否为空: " + seqStack.isEmptyStack());
144 }
145
146
147 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-07-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录