数据结构——java实现栈

栈

定义：

栈是一种先进后出的数据结构，我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何元素的栈称为空栈

栈的java代码实现：

基于数组：

 import org.junit.jupiter.api.Test;

 /**

  *  用数组实现栈

  * @author wydream

  *

  */

 public class ArrayStack<T> {

     private T data[];

     private int maxSize;

     private int top;

     //初始化栈

     public ArrayStack(int maxSize) {

         this.maxSize=maxSize;

         data=(T[])new Object[maxSize];

         this.top=-1;

     }

     //判断栈是否为空

     public boolean isEmpty() {

         return (top==-1);

     }

     //判断栈是否已经满了

     public  boolean isFull() {

         return (top==maxSize-1);

     }

     //压栈

     public boolean push(T value) {

         if(isFull()) {

             return false;

         }

         top++;

         data[top]=value;

         return true;

     }

     //取出栈顶元素

     public T pop() {

         if(isEmpty()) {

             return null;

         }

         T tmp=data[top];

         data[top]=null;

         top--;

         return tmp;

     }

     //============测试代码============

     public static void main(String[] args) {

         ArrayStack<String> as=new ArrayStack<String>(4);

         as.push("anhui");

         as.push("shanghai");

         as.push("beijing");

         as.push("nanj");

         //测试栈已经满了的情况

         System.out.println(as.push("aa"));

         for(int i=0;i<4;i++) {

             System.out.println(as.pop());

         }

     }

 }

基于链表：

 import org.junit.jupiter.api.Test;

 /**

  *   基于链表实现的栈

  * @author wydream

  *

  */

 public class NodeStack<T> {

     private Node<T> top=null;//栈顶

     public NodeStack() {

         this.top=null;

     }

     //判断栈是否为空

     public boolean isEmpty() {

         if(top!=null) {

             return false;

         }

         return true;

     }

     //压栈

     public boolean push(T value) {

         Node<T> node=new Node<T>(value);

         node.setNext(top);

         top=node;

         return true;

     }

     //出栈

     public T pop() {

         if(top==null) {

             return null;

         }

         T tmp=top.data;

         top=top.getNext();

         return tmp;

     }

     //取出栈顶的值

     public T peek() {

         if(isEmpty()) {

             return null;

         }

         return top.data;

     }

     class Node<T>{

         private T data;//数据

         private Node<T> next;//指向下一个节点的指针

         //初始化链表

         public Node(T data) {

             this.data=data;

         }

         //获取下一个节点

         public Node<T> getNext(){

             return this.next;

         }

         //设置下一个节点

         public void setNext(Node<T> n) {

             this.next=n;

         }

         //获取节点数据

         public T getData() {

             return this.data;

         }

         //设置节点数据

         public void setData(T d) {

             this.data=d;

         }

     }

     public static void main(String[] args) {

         NodeStack<String> ns=new NodeStack<String>();

         //测试是否为空

         System.out.println("=======是否为空======");

         System.out.println(ns.isEmpty());

         System.out.println("=============");

         //压栈测试

         System.out.println("=======压栈======");

         ns.push("北京");

         ns.push("上海");

         ns.push("深证");

         ns.push("广州");

         //是否为空

         System.out.println("=======是否为空======");

         System.out.println(ns.isEmpty());

         System.out.println("=============");

         System.out.println("=======出栈=======");

         //出栈

         System.out.println(ns.pop());

         System.out.println(ns.pop());

         System.out.println(ns.pop());

         System.out.println(ns.pop());

         System.out.println(ns.pop());

         //是否为空

         System.out.println("=======是否为空======");

         System.out.println(ns.isEmpty());

         System.out.println("=============");

     }

 }

两栈共享空间：

栈有个缺陷，必须事先确定数组的大小，这样如果栈满了的话，想在存储元素就必须通过编程手段来扩充数组的容量，这样就很麻烦。于是我们就设计一个数组，里面存放着两个栈，共享这一个数组空间，这样就可以充分利用空间。数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的0下标，另一个栈的栈为数组的长度n-1处

代码实现：

 import javax.crypto.Mac;

 /**

  *   两栈共享空间

  * @author wydream

  *

  */

 public class DoubleStatk {

     private final static int MAXSIZE=20;

     private int[] stackElem;

     private int top1; //将top1设置为指向栈1栈顶元素的存储位置即数组下标0

     private int top2; //将top2设置为指向栈2栈顶元素的存储位置即数组下标n-1

     public DoubleStatk() {

         top1=-1;

         top2=MAXSIZE;

         stackElem=new int[MAXSIZE];

     }

     //是否是空栈

     public boolean isEmptyStack() {

         if(top1==-1&&top2==MAXSIZE) {

             return true;

         }

         return false;

     }

     //清空栈

     public void clearStack() {

         top1=-1;

         top2=MAXSIZE;

     }

     //栈的长度

     public int lengthStak() {

         return (top1+1)+(MAXSIZE-top2);

     }

     //获取top1的元素

     public int getTop1Elem() {

         if(top1==-1) {

             return -1;

         }

         return stackElem[top1];

     }

     //获取top2的元素

     public int getTop2Elem() {

         if(top2==MAXSIZE) {

             return -1;

         }

         return stackElem[top2];

     }

     //压栈

     public void stackPush(int stackNumber,int e) {

         //如果栈已经满了

         if(top1+1==top2) {

             System.out.println("栈已满");

             return;

         }

         if(stackNumber==1) {

             top1+=1;

             stackElem[top1]=e;

             return;

         }

         if(stackNumber==2) {

             top2-=1;

             stackElem[top2]=e;

             return;

         }

     }

     //出栈

     public int stackPop(int stackNumber) {

         int rs;

         if(isEmptyStack()) {

             System.out.println("栈为空");

             return -1;

         }

         if(stackNumber==1) {

             rs= stackElem[top1];

             top1--;

         }else if(stackNumber==2) {

             rs=stackElem[top2];

             top2++;

         }else {

             System.out.println("输入数据有误");

             return -1;

         }

         return rs;

     }

     public void stackTraverse() {

         System.out.println("此时，栈中的元素为：");

         int i=0;

         while(i<=top1) {

             System.out.println(stackElem[i++]+" ");

         }

         i=top2;

         while(i<MAXSIZE) {

             System.out.println(stackElem[i++]+" ");

         }

         System.out.println();

     }

     public static void main(String[] args) {

         DoubleStatk seqStack=new DoubleStatk();

         //1压栈

         for(int j=1;j<=5;j++) {

             seqStack.stackPush(1,j);

         }

         //2压栈

         for(int i=MAXSIZE;i>=MAXSIZE-2;i--) {

             seqStack.stackPush(2, i);

         }

         //输出

         seqStack.stackTraverse();

         System.out.println("栈的长度为："+seqStack.lengthStak());

         seqStack.stackPop(2);

         seqStack.stackTraverse();

         System.out.println("栈1的栈顶元素为: " + seqStack.getTop1Elem());

         System.out.println("栈2的栈顶元素为: " + seqStack.getTop2Elem());

         System.out.println("栈的长度为: " + seqStack.lengthStak());

         for (int i = 6; i <= MAXSIZE-2; i++) {

             seqStack.stackPush(1,i);

         }

         seqStack.stackTraverse();

         System.out.println("栈1的栈顶元素为: " + seqStack.getTop1Elem());

         System.out.println("栈2的栈顶元素为: " + seqStack.getTop2Elem());

         System.out.println("栈顶元素为: " + seqStack.getTop2Elem());

         System.out.println("栈的长度为: " + seqStack.lengthStak());

         System.out.println("栈是否为空: " + seqStack.isEmptyStack());

         seqStack.clearStack();

         System.out.println("栈是否为空: " + seqStack.isEmptyStack());

     }

 }

巴特西

数据结构——java实现栈

栈

定义：

栈的java代码实现：

基于数组：

基于链表：

两栈共享空间：

代码实现：

最新文章

热门文章