栈的顺序结构和链式结构实现

1.栈的顺序存储<数组实现>

1.1.栈的接口

 1 package com.neusoft.stack;
 2 
 3 public interface IStack {
 4     //1.栈置空
 5     public void clear();
 6     //2.栈判空
 7     public boolean isEmpty();
 8     //3.栈长度
 9     public int length();
10     //4.取栈顶元素
11     public Object peek();
12     //5.移除栈顶元素-----出栈
13     public Object pop();
14     //6.入栈
15     public void push(Object x);
16     //7.打印栈元素
17     public void display();
18 }

点击复制代码

 1 package com.neusoft.stack;
 2 
 3 public interface IStack {
 4     //1.栈置空
 5     public void clear();
 6     //2.栈判空
 7     public boolean isEmpty();
 8     //3.栈长度
 9     public int length();
10     //4.取栈顶元素
11     public Object peek();
12     //5.移除栈顶元素-----出栈
13     public Object pop();
14     //6.入栈
15     public void push(Object x);
16     //7.打印栈元素
17     public void display();
18 }
点击+展开代码

1.2 栈的顺序存储类

 1 package com.neusoft.stack;
 2 
 3 public class SqStack implements IStack {
 4     private Object[] stackElem;
 5     //非空栈中始终表示栈顶元素的下一个位置，当栈为空的时候其值为0
 6     public int top;
 7     public SqStack(int maxSize) {
 8         // TODO 初始化栈
 9         top=0;
10         stackElem=new Object[maxSize];
11     }
12     @Override
13     public void clear() {
14         // TODO 栈置空
15         top=0;
16     }
17     @Override
18     public boolean isEmpty() {
19         // TODO 栈判空
20         return top==0;
21     }
22     @Override
23     public int length() {
24         // TODO 栈长度
25         return top;
26     }
27     @Override
28     public Object peek() {
29         // TODO 查看栈顶元素对象而不移除，返回栈顶元素
30         if (!isEmpty()) {
31             //返回镇定元素
32             return stackElem[top-1];
33         }
34         else {
35             //栈为空
36             return null;
37         }
38     }
39 
40     @Override
41     public Object pop() {
42         // TODO 出栈操作
43         if (top==0) {
44             return null;
45         }else {//栈非空
46             return stackElem[--top];
47         }
48     }
49     @Override
50     public void push(Object elem) {
51         // TODO 入栈
52         if (top==stackElem.length) {
53             System.out.println("栈满~");
54         }else {//栈未满
55             stackElem[top++]=elem;
56         }
57     }
58 
59     @Override
60     public void display() {
61         // TODO 显示
62         for (int i=top-1;i>=0;i-- ) {
63             System.out.print(stackElem[i].toString()+" ");
64         }
65         System.out.println();
66     }
67 
68 }

点击复制代码

 1 package com.neusoft.stack;
 2 
 3 public class SqStack implements IStack {
 4     private Object[] stackElem;
 5     //非空栈中始终表示栈顶元素的下一个位置，当栈为空的时候其值为0
 6     public int top;
 7     public SqStack(int maxSize) {
 8         // TODO 初始化栈
 9         top=0;
10         stackElem=new Object[maxSize];
11     }
12     @Override
13     public void clear() {
14         // TODO 栈置空
15         top=0;
16     }
17     @Override
18     public boolean isEmpty() {
19         // TODO 栈判空
20         return top==0;
21     }
22     @Override
23     public int length() {
24         // TODO 栈长度
25         return top;
26     }
27     @Override
28     public Object peek() {
29         // TODO 查看栈顶元素对象而不移除，返回栈顶元素
30         if (!isEmpty()) {
31             //返回镇定元素
32             return stackElem[top-1];
33         }
34         else {
35             //栈为空
36             return null;
37         }
38     }
39 
40     @Override
41     public Object pop() {
42         // TODO 出栈操作
43         if (top==0) {
44             return null;
45         }else {//栈非空
46             return stackElem[--top];
47         }
48     }
49     @Override
50     public void push(Object elem) {
51         // TODO 入栈
52         if (top==stackElem.length) {
53             System.out.println("栈满~");
54         }else {//栈未满
55             stackElem[top++]=elem;
56         }
57     }
58 
59     @Override
60     public void display() {
61         // TODO 显示
62         for (int i=top-1;i>=0;i-- ) {
63             System.out.print(stackElem[i].toString()+" ");
64         }
65         System.out.println();
66     }
67 
68 }
点击+展开

1.3.栈的顺序存储测试类

 1 package com.neusoft.stack;
 2 //测试顺序结构的栈
 3 public class DebugSqStack {
 4     public static void main(String[] args) {
 5         //------初始化栈------------
 6         SqStack S = new SqStack(100);
 7         //-----入栈(添加元素)--------
 8         for (int i = 0; i < 10; i++) {
 9             S.push(i);
10         }
11         //----输出栈中的元素---------
12         System.out.println("栈中个元素为：");
13         S.display();
14         //----判断栈空--------------
15         if (!S.isEmpty()) {
16             System.out.println("栈不是空的~");
17         }
18         //---栈长度------------------
19         System.out.println("栈的长度为："+S.length());
20         //---输出栈顶元素-------------
21         System.out.println("栈顶元素为："+S.peek().toString());
22         //-----测试取出栈顶元素后的输出---------------
23         S.pop();
24         S.display();
25         //-----去除栈中的所有元素------------------
26         System.out.println("去除所有栈中的元素");
27         S.clear();
28         if (S.isEmpty()) {
29             System.out.println("栈已经清空~");
30         }
31     }
32 }

点击复制代码

 1 package com.neusoft.stack;
 2 //测试顺序结构的栈
 3 public class DebugSqStack {
 4     public static void main(String[] args) {
 5         //------初始化栈------------
 6         SqStack S = new SqStack(100);
 7         //-----入栈(添加元素)--------
 8         for (int i = 0; i < 10; i++) {
 9             S.push(i);
10         }
11         //----输出栈中的元素---------
12         System.out.println("栈中个元素为：");
13         S.display();
14         //----判断栈空--------------
15         if (!S.isEmpty()) {
16             System.out.println("栈不是空的~");
17         }
18         //---栈长度------------------
19         System.out.println("栈的长度为："+S.length());
20         //---输出栈顶元素-------------
21         System.out.println("栈顶元素为："+S.peek().toString());
22         //-----测试取出栈顶元素后的输出---------------
23         S.pop();
24         S.display();
25         //-----去除栈中的所有元素------------------
26         System.out.println("去除所有栈中的元素");
27         S.clear();
28         if (S.isEmpty()) {
29             System.out.println("栈已经清空~");
30         }
31     }
32 }
点击+展开代码

1.4 测试类

      

2.栈的链式存储结构(链栈)

2.1 IStack接口声明

 1 package com.neusoft.stack;
 2 
 3 public interface IStack {
 4     //1.栈置空
 5     public void clear();
 6     //2.栈判空
 7     public boolean isEmpty();
 8     //3.栈长度
 9     public int length();
10     //4.取栈顶元素
11     public Object peek();
12     //5.移除栈顶元素-----出栈
13     public Object pop();
14     //6.入栈
15     public void push(Object x);
16     //7.打印栈元素
17     public void display();
18 }

点击复制代码

 1 package com.neusoft.stack;
 2 
 3 public interface IStack {
 4     //1.栈置空
 5     public void clear();
 6     //2.栈判空
 7     public boolean isEmpty();
 8     //3.栈长度
 9     public int length();
10     //4.取栈顶元素
11     public Object peek();
12     //5.移除栈顶元素-----出栈
13     public Object pop();
14     //6.入栈
15     public void push(Object x);
16     //7.打印栈元素
17     public void display();
18 }
点击+复制代码

2.2 Node节点声明

 1 package com.neusoft.stack;
 2 
 3 public class Node {
 4     public Object data;// 数据域
 5     public Node next;// 指针域
 6     public Node() { //构造空节点
 7         this(null,null);
 8     }
 9     public Node(Object data){//构造有一个参数的数据域
10         this(data,null);
11     }
12     public Node(Object data,Node node){//构造数据域和指针域
13         this.data=data;
14         this.next=node;
15     }
16 }

点击复制代码

 1 package com.neusoft.stack;
 2 
 3 public class Node {
 4     public Object data;// 数据域
 5     public Node next;// 指针域
 6     public Node() { //构造空节点
 7         this(null,null);
 8     }
 9     public Node(Object data){//构造有一个参数的数据域
10         this(data,null);
11     }
12     public Node(Object data,Node node){//构造数据域和指针域
13         this.data=data;
14         this.next=node;
15     }
16 }
点击+展开代码

2.3 链栈的实现类

 1 package com.neusoft.stack;
 2 public class LinkStack implements IStack {
 3     private Node top;//栈顶元素的引用
 4     @Override
 5     public void clear() {
 6         // TODO 链栈置空
 7         top=null;
 8     }
 9 
10     @Override
11     public boolean isEmpty() {
12         // TODO 判空
13         return top== null;
14     }
15 
16     @Override
17     public int length() {
18         // TODO 长度
19         Node p =top;//p指针指向栈顶元素
20         int length=0;
21         while (p!=null) {
22             p=p.next;//指向后继节点
23             length++;
24         }
25         return length;
26     }
27 
28     @Override
29     public Object peek() {
30         // TODO 查找栈顶元素而不移除
31         if (!isEmpty()) {
32             return top.data;//栈顶元素
33         }else {
34             return null;
35         }
36     }
37     @Override
38     public Object pop() {
39         // TODO 出栈,返回出栈的元素
40         if (!isEmpty()) {
41             Node p=top;//将要删除的元素用p指针暂存
42             top=top.next;
43             return p.data;
44         }else{
45             return null;
46         }
47     }
48     @Override
49     public void push(Object x) {
50         // TODO 入栈
51         Node p=new Node(x);//构造一个新节点
52         p.next=top;
53         top=p;
54     }
55 
56     @Override
57     public void display() {
58         // TODO 显示数据
59         Node p=top;
60         while(p!=null){
61             System.out.print(p.data.toString()+" ");
62             p=p.next;
63         }
64         System.out.println();
65     }
66 
67 }

点击复制代码

 1 package com.neusoft.stack;
 2 public class LinkStack implements IStack {
 3     private Node top;//栈顶元素的引用
 4     @Override
 5     public void clear() {
 6         // TODO 链栈置空
 7         top=null;
 8     }
 9 
10     @Override
11     public boolean isEmpty() {
12         // TODO 判空
13         return top== null;
14     }
15 
16     @Override
17     public int length() {
18         // TODO 长度
19         Node p =top;//p指针指向栈顶元素
20         int length=0;
21         while (p!=null) {
22             p=p.next;//指向后继节点
23             length++;
24         }
25         return length;
26     }
27 
28     @Override
29     public Object peek() {
30         // TODO 查找栈顶元素而不移除
31         if (!isEmpty()) {
32             return top.data;//栈顶元素
33         }else {
34             return null;
35         }
36     }
37     @Override
38     public Object pop() {
39         // TODO 出栈,返回出栈的元素
40         if (!isEmpty()) {
41             Node p=top;//将要删除的元素用p指针暂存
42             top=top.next;
43             return p.data;
44         }else{
45             return null;
46         }
47     }
48     @Override
49     public void push(Object x) {
50         // TODO 入栈
51         Node p=new Node(x);//构造一个新节点
52         p.next=top;
53         top=p;
54     }
55 
56     @Override
57     public void display() {
58         // TODO 显示数据
59         Node p=top;
60         while(p!=null){
61             System.out.print(p.data.toString()+" ");
62             p=p.next;
63         }
64         System.out.println();
65     }
66 
67 }
点击+复制代码

2.4 链栈的测试类

 1 package com.neusoft.stack;
 2 
 3 public class DebugLinkStack {
 4     public static void main(String[] args) {
 5         //-----------初始化--------------
 6         LinkStack S = new LinkStack();
 7         //----------插入元素-------------
 8         for (int i = 1; i <=10; i++) {
 9             S.push(i);
10         }
11         //---------显示栈中各元素-----------
12         System.out.println("链栈中的元素为：");
13         S.display();
14         //---------判断栈空--------------
15         if (!S.isEmpty()) {
16             System.out.println("栈非空~");
17             //--------栈长度-----------
18             System.out.println("栈的长度为："+S.length());
19             //--------输出栈顶元素-----------
20             System.out.println("栈顶元素为："+S.peek().toString());
21             //--------去除栈顶元素后，剩余各个元素为-------
22             System.out.println("栈顶元素出栈之后的各元素输出为：");
23             S.pop();
24             S.display();
25             //-----栈置空---------
26             S.clear();
27             if (S.isEmpty()) {
28                 System.out.println("栈为空！~");
29             }
30         }
31     }
32 }

点击复制代码

 1 package com.neusoft.stack;
 2 
 3 public class DebugLinkStack {
 4     public static void main(String[] args) {
 5         //-----------初始化--------------
 6         LinkStack S = new LinkStack();
 7         //----------插入元素-------------
 8         for (int i = 1; i <=10; i++) {
 9             S.push(i);
10         }
11         //---------显示栈中各元素-----------
12         System.out.println("链栈中的元素为：");
13         S.display();
14         //---------判断栈空--------------
15         if (!S.isEmpty()) {
16             System.out.println("栈非空~");
17             //--------栈长度-----------
18             System.out.println("栈的长度为："+S.length());
19             //--------输出栈顶元素-----------
20             System.out.println("栈顶元素为："+S.peek().toString());
21             //--------去除栈顶元素后，剩余各个元素为-------
22             System.out.println("栈顶元素出栈之后的各元素输出为：");
23             S.pop();
24             S.display();
25             //-----栈置空---------
26             S.clear();
27             if (S.isEmpty()) {
28                 System.out.println("栈为空！~");
29             }
30         }
31     }
32 }
点击+复制代码

2.5 结果分析

    

3.编写一个函数，要求借助栈把一个数组中的元素逆置 

 1 package com.neusoft.stack;
 2 /**
 3  * @author zhao-chj
 4  * 编写一个函数，要求借助栈把一个数组中的元素逆置
 5  */
 6 public class Exercise001 {
 7   public static void main(String[] args) {
 8       Integer[] a={2,3,5,8,12,34};
 9       System.out.println("逆置前数组中的各个元素为：");
10       for (int i = 0; i < a.length; i++) {
11         System.out.print(a[i]+" ");
12     }
13       System.out.println();
14       reserve(a);
15       System.out.println("逆置后的数据中的元素为：");
16       for (int i = 0; i < a.length; i++) {
17         System.out.print(a[i]+" ");
18     }
19   }
20 
21   private static void reserve(Object[] a) {
22     // TODO 栈中数组元素逆置
23     SqStack S = new SqStack(a.length);
24     for (int i = 0; i < a.length; i++) {
25         S.push(a[i]);
26     }
27     for (int i = 0; i < a.length; i++) {
28         a[i]=S.pop();
29     }
30 }
31 }

点击复制代码

 1 package com.neusoft.stack;
 2 /**
 3  * @author zhao-chj
 4  * 编写一个函数，要求借助栈把一个数组中的元素逆置
 5  */
 6 public class Exercise001 {
 7   public static void main(String[] args) {
 8       Integer[] a={2,3,5,8,12,34};
 9       System.out.println("逆置前数组中的各个元素为：");
10       for (int i = 0; i < a.length; i++) {
11         System.out.print(a[i]+" ");
12     }
13       System.out.println();
14       reserve(a);
15       System.out.println("逆置后的数据中的元素为：");
16       for (int i = 0; i < a.length; i++) {
17         System.out.print(a[i]+" ");
18     }
19   }
20 
21   private static void reserve(Object[] a) {
22     // TODO 栈中数组元素逆置
23     SqStack S = new SqStack(a.length);
24     for (int i = 0; i < a.length; i++) {
25         S.push(a[i]);
26     }
27     for (int i = 0; i < a.length; i++) {
28         a[i]=S.pop();
29     }
30 }
31 }
点击+复制代码

测试结果

    

4.编写一个序列判断十个字符是否是回文序列

====回文序列:正读和反读都相同,如abba和abdba

 1 package com.neusoft.stack;
 2 /**
 3  * @author zhao-chj
 4  * 编写一个序列判断十个字符是否是回文序列
 5  * 回文序列:正读和反读都相同,如abba和abdba
 6  * 要求：使用栈实现
 7  */
 8 public class Exercise002 {
 9     private static boolean isPailndSeq(String str) {
10         // TODO 判断是否为回文序列
11         LinkStack S= new LinkStack();
12         for (int j = 0; j < str.length(); j++) {
13             S.push(str.charAt(j));//Returns the char value at the specified index.
14         }
15         for (int i = 0; i < str.length(); i++) {
16             char c=((Character)S.pop()).charValue();
17             if (c!=str.charAt(i)) {
18                 return false;
19             }
20         }
21         return true;
22     }
23     public static void main(String[] args) {
24         String str1="abba";
25         String str2="abdba";
26         boolean as=isPailndSeq(str1);
27         if (as) {
28             System.out.println(str1+"是回文序列");
29         }else {
30             System.out.println(str1+"不是回文序列");
31         }
32     }
33 
34 
35 }

点击复制代码

 1 package com.neusoft.stack;
 2 /**
 3  * @author zhao-chj
 4  * 编写一个序列判断十个字符是否是回文序列
 5  * 回文序列:正读和反读都相同,如abba和abdba
 6  * 要求：使用栈实现
 7  */
 8 public class Exercise002 {
 9     private static boolean isPailndSeq(String str) {
10         // TODO 判断是否为回文序列
11         LinkStack S= new LinkStack();
12         for (int j = 0; j < str.length(); j++) {
13             S.push(str.charAt(j));//Returns the char value at the specified index.
14         }
15         for (int i = 0; i < str.length(); i++) {
16             char c=((Character)S.pop()).charValue();
17             if (c!=str.charAt(i)) {
18                 return false;
19             }
20         }
21         return true;
22     }
23     public static void main(String[] args) {
24         String str1="abba";
25         String str2="abdba";
26         boolean as=isPailndSeq(str1);
27         if (as) {
28             System.out.println(str1+"是回文序列");
29         }else {
30             System.out.println(str1+"不是回文序列");
31         }
32     }
33 
34 
35 }
点击+复制代码

测试结果

    

END~

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/jackchen-Net/p/6675586.html