栈 之 如何实现一个栈

/*** @Description* @Author Flag* @Date: 2021/7/20 8:53* @Version: 1.0**/
public class LinkedStackDome {public static void main(String[] args) {//测试一下LinkedStack是否正常//先创建一个ArrayStack对象->表示栈LinkedStack stack = new LinkedStack(4);String key = "";boolean loop = true;//用于控制是否退出Scanner scanner = new Scanner(System.in);while (loop){System.out.println("show:表示显示栈");System.out.println("exit:退出程序");System.out.println("push:表示添加元素到栈(入栈)");System.out.println("pop:表示从栈取出数据(出战)");System.out.println("请输入你的选择:");key = scanner.next();switch (key){case "show":stack.show();break;case "exit":scanner.close();loop = false;break;case "push":System.out.println("请输入一个数字");int i = scanner.nextInt();stack.push(i);break;case "pop":try{int pop = stack.pop();System.out.println("出栈的数据:"+pop);} catch (Exception e){System.out.println(e.getMessage());}break;default:break;}}}}class LinkedStack{//定义栈的大小private int maxSize;//链表模拟栈，private LinkedStackNode first;//top表示栈顶，初始化是-1private int top;/*** 构造方法* @param maxSize 栈的大小*/public LinkedStack(int maxSize) {this.maxSize = maxSize;top = -1;}/*** 判断栈是否满了* @return*/public boolean isFull(){return top+1 == maxSize;}/*** 入栈* @param value 入栈的元素*/public void push(int value){//1、判断栈是否满了if(this.isFull()){System.out.println("栈已经满了,不能再添加元素");return;}//2、新创建一个节点，用于添加到链表上LinkedStackNode node = new LinkedStackNode(value);//3、将top++,表示链表中的元素新增了一个top++;//4、判断头元素是否为null,如果是null,代表是第一个元素,则直接让新元素当第一个元素if(first == null){first = node;return;}//5.如果头元素不是null,则证明，此时链表中已经有元素，则将新元素添加上即可//5.1获取到链表的尾部LinkedStackNode middleNode = first;while (middleNode.getNext() != null){middleNode = middleNode.getNext();}//5.2将链表添加上去middleNode.setNext(node);}/*** 出栈* @return 出栈的元素*/public int pop(){//1.判断栈是否为nullif(this.isEmpty()){throw new RuntimeException("栈中没有元素");}//2.将链表的数量减一top -- ;//3.如果链表中是否只有一个元素if(first.getNext() == null){LinkedStackNode popNode = this.first;this.first = null;return popNode.getNumber();}//4.如果链表中有不只一个元素//4.1.定义一个中间变量，让他指向链表的最后一个元素，即最后要出栈的元素LinkedStackNode lastNode = first;//4.2.定义一个中间变量，用来用来获取到比lastNode前一个元素,‘//因为是单向链表，我们出栈后，要置空指向最后一个元素的指针，所以需要找到最有一个元素的前一个元素进行操作LinkedStackNode beforeLastNode = null;//4.2.遍历链表,直到lastNode是最后一个元素,此时，如果链表中只有一个元素，则while (lastNode.getNext() != null){//将lastNode给到beforeLastNode//然后lastNode向后移动//此时就构造出 beforeLastNode在lastNode前一个位置的情况beforeLastNode = lastNode;lastNode = lastNode.getNext();}//4.3.此时将最后一个元素的前一个元素的next指针变成null,则相当于舍弃掉了最后一个元素beforeLastNode.setNext(null);//4.3.返回lastNode的编号return lastNode.getNumber();}/*** 显示栈的元素*/public void show(){//判断栈是否为nullif(this.isEmpty()){System.out.println("栈中无元素");return;}//定义一个新的链表节点LinkedStackNode newLinedStackHead = null;//正向遍历原始链表，将链表的每一个元素，都放到新的链表的第一个元素//因为前面做了判断，所以first不可以为nullLinkedStackNode oldLinkedStackNode = first;//直到原始链表元素为null时，结束while (oldLinkedStackNode != null){LinkedStackNode middleNode = new LinkedStackNode(oldLinkedStackNode.getNumber());if(newLinedStackHead == null){newLinedStackHead = middleNode;} else {middleNode.setNext(newLinedStackHead);newLinedStackHead = middleNode;}//移动原始链表的位置oldLinkedStackNode = oldLinkedStackNode.getNext();}while (newLinedStackHead != null){System.out.println(newLinedStackHead.getNumber());newLinedStackHead = newLinedStackHead.getNext();}}/*** 判断栈是否为null* @return 结果*/public boolean isEmpty(){return top == -1;}
}/*** 链表栈的节点*/
class LinkedStackNode{private int number;private LinkedStackNode next;public LinkedStackNode(int number) {this.number = number;}public int getNumber() {return number;}public LinkedStackNode getNext() {return next;}public void setNext(LinkedStackNode next) {this.next = next;}
}