专栏首页用代码征服天下数据结构——java实现栈

数据结构——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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • java之static关键字

    说故事的五公子
  • java字符串操作

    说故事的五公子
  • 各种递归算法

    说故事的五公子
  • SpringBoot自定义

    崔笑颜
  • 设计模式之 装饰器模式

    tanoak
  • SpringMVC源码深度解析之拦截器&过滤器&视图层&异步源码分析

    加入这个注解EnableWebMvc重复注入了WebMvcConfigurationSupport,会覆盖我们自定义的配置类

    须臾之余
  • Asp.Net 之 Web.config 配置文件详解

      在asp.net中配置文件名一般默认是web.config。每个web.config文件都是基于XML的文本文件,并且可以保存到Web应用程序中的任何目录中...

    CherishTheYouth
  • C# WinForm PropertyGrid用法

    关于C# PropertyGrid的用法没有找到,找到一个C++的用法。 模仿着使用了一下,感觉挺不错,分享一下。 基本用法: 拖个PropertyGr...

    静谧的小码农
  • 【编程题】Java编程题一(10道)

    【编程题】Java编程题一(10道) 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,...

    Java帮帮
  • java(6)——+号和++号--号

    可以见得,当左边或右边为单字符时,加上的是ASCII字符集里面对应的数字,当单独用时,为正号的意思。

    gzq大数据

扫码关注云+社区

领取腾讯云代金券