链式栈

特点

  • 能够克服用数组实现的顺序栈空间利用率不高的特点
  • 但是需要为每个栈元素分配额外的指针空间用来存放指针域

    代码实现

    ```java import org.w3c.dom.Node;

import java.util.LinkedList; import java.util.Scanner;

/**

  • @author laoduan
  • @create 2020-04-10-17:53 */ public class LinkedListStackDemo { public static void main(String[] args) {
    1.  LinkedListStack linkedListStack = new LinkedListStack();
  1.     String key = "";
  2.     boolean loop = true;
  3.     Scanner scanner = new Scanner(System.in);
  5.     while (loop){
  6.         System.out.println("------------------------");
  7.         System.out.println("show:显示栈");
  8.         System.out.println("exit:退出程序");
  9.         System.out.println("pop:出栈");
  10.         System.out.println("push:入栈\n");
  11.         System.out.println("输入你的选择\n");
  13.         key = scanner.next();
  14.         switch (key){
  15.             case "show":
  16.                 linkedListStack.list();
  17.                 break;
  18.             case "push":
  19.                 System.out.println("请输入一个数");
  20.                 int value = scanner.nextInt();
  21.                 System.out.println("请输入数据");
  22.                 String data = scanner.next();
  23.                 MyNode myNode = new MyNode(value, data);
  24.                 linkedListStack.push(myNode);
  25.                 break;
  26.             case "pop":
  27.                 try {
  28.                     linkedListStack.pop();
  29.                 }catch (Exception e){
  30.                     System.out.println(e.getMessage());
  31.                 }
  32.                 break;
  33.             case "exit":
  34.                 scanner.close();
  35.                 loop=false;
  36.                 break;
  37.             default:
  38.                 break;
  40.         }
  42.     }
  43.     System.out.println("程序退出");
  47. }

}

class LinkedListStack{ private int top=-1;

  1. MyNode head = new MyNode(0,"");
  2. public MyNode getHead(){
  3.     return head;
  4. }
  7. //入栈
  8. public void push(MyNode myNode){
  9.     MyNode temp = head.next;
  10.     if(head.next==null){
  11.         head.next=myNode;
  12.     }else {
  13.         myNode.next=temp;
  14.         head.next=myNode;
  15.     }
  16.     top++;
  17. }
  19. //出栈
  20. public MyNode pop (){
  21.     MyNode node = head.next;
  22.     head.next=node.next;
  23.     System.out.println("取出的栈顶数据是:"+node);
  24.     if(node==null){
  25.         System.out.println("链表为空");
  26.     }
  27.     return node;
  28. }
  31. public void list(){
  32.     if (head.next==null){
  33.         System.out.println("链表为空");
  34.         return;
  35.     }
  37.     MyNode temp = head.next;
  38.     while (true){
  39.         if(temp==null){
  40.             break;
  41.         }
  42.         System.out.println(temp);
  43.         //将temp后移
  44.         temp=temp.next;
  45.     }
  46. }

}

class MyLinkedList{ MyNode head = new MyNode(0,””); public MyNode getHead(){ return head; }

  1. public void add(MyNode myNode){
  2.     MyNode temp = head.next;
  3.     if(head.next==null){
  4.         head.next=myNode;
  5.     }else {
  6.         myNode.next=temp;
  7.         head.next=myNode;
  8.     }
  9. }
  11. public void show(){
  12.     if (head.next==null){
  13.         System.out.println("链表为空");
  14.         return;
  15.     }
  17.     MyNode temp = head.next;
  18.     while (true){
  19.         if(temp==null){
  20.             break;
  21.         }
  22.         System.out.println(temp);
  23.         //将temp后移
  24.         temp=temp.next;
  25.     }
  26. }

} class MyNode{ int no; String data; MyNode next;

  1. public MyNode(int no,String data){
  2.     this.no=no;
  3.     this.data=data;
  4. }
  6. @Override
  7. public String toString() {
  8.     return "{" +
  9.             "no=" + no +
  10.             ", data='" + data + '\'' +
  11.             '}';
  12. }

} ```