单向链表栈的java实现 详细讲解

文章目录

• 前言
• 一、栈是什么？
• 二、实现步骤
• • 1.定义node节点
  • 2.栈结构的定义
  • 3.栈的判断
  • 3.1判断是否已满
  • • 3.2判断栈是否为空
  • 4.栈的操作
  • • 4.1入栈
    • 4.2出栈
  • 5.（逆序）遍历所有栈节点
• 代码整合
• 总结

前言

工作之余，学习一下数据结构与算法，今天学习数据结构：“栈”。笔者有一个坏习惯，一看就会，一写就废。所以笔者准备亲自写使用单向链表实现栈

提示：以下是本篇文章正文内容，下面案例可供参考

一、栈是什么？

小编的理解：
1.一串有顺序的结构
2.只能从同一个位置取出元素或者添加元素
3.不能从中间存元素或者取元素

二、实现步骤

1.定义node节点

既然要实现链表，那就必须要有两个成员变量，来表示链表的节点

1. 下一个节点
2. 当前节点的编号

class Node{    public Node next;    public int no;    public Node(int no){this.no=no;}    @Override    public String toString() { return "Node{" +  ", no=" + no +  '}';    }}

2.栈结构的定义

要保有栈的特性，栈是有一定的容量限制，链表的头结点作为链表的指引

1. maxSize代表栈的空间
2. bottom代表的是栈底元素，固定位置

class StackLinkedList{    public int maxSize;    public Node bottom=new Node(0);    //初始化    public StackLinkedList(int maxSize){ this.maxSize=maxSize;    }}

3.栈的判断

3.1判断是否已满

判断栈内空间是否已满，当栈的节点的数量和maxSize最大容量相等时，栈满

 //链表是否已满    public boolean isFull(){boolean result=false;int size=0;Node temp=bottom.next;while (true){    if (temp==null){ break;    }    temp=temp.next;    size++;}if (size==maxSize){    result=true;}return result;    }

3.2判断栈是否为空

当栈底元素没有下一个节点应用时，栈空

  //链表是否为空    public boolean isEmpty(){ return bottom.next==null;    }

4.栈的操作

4.1入栈

入栈时，需要判断栈内的元素是否已满，链表最后一个节点指向新的节点，lastNode.next=newNode；

  //入栈    public void push(int no){ if (isFull()){     System.out.println("链表已满，请出栈~~~"); }else{     Node node=new Node(no);     Node temp=bottom;     while(true){  if (temp.next==null){      break;  }  temp=temp.next;     }     temp.next=node; }    }

4.2出栈

出栈时，需要判断栈内的元素是佛为空，被出节点前一个节点，指向null，需要被出节点的引用

 //出栈    public int pop(){ if (isEmpty()){     throw new RuntimeException("链表为空，请入栈~~~"); } Node temp=bottom; int num=0; while (temp!=null){     if (temp.next.next==null){  num= temp.next.no;  temp.next=null;  break;     }     temp=temp.next; } return num;    }

5.（逆序）遍历所有栈节点

小编在这里偷了一个懒，正常的使用逻辑是先把链表的所有节点逆序遍历到新的栈中，遍历新的栈元素实现。小编的解决思路：利用java中已有Stack的特性，先进新出的原则，遍历所有节点到stack，然后出栈

  //遍历栈元素    public void show(){ Stack stack=new Stack(); Node temp=bottom.next; while (temp!=null){     stack.push(temp);     temp=temp.next; } while(stack.size()>0){     System.out.println(stack.pop()); }    }

代码整合

package com.qf.linkedlist;import java.util.Scanner;import java.util.Stack;public class StackLinkedListDemo {    public static void main(String[] args) { StackLinkedList stack=new StackLinkedList(5); boolean loop=true; char sc=' '; while (loop){     System.out.println("e 跳出循环");     System.out.println("p 入栈");     System.out.println("o 出栈");     System.out.println("s 循环栈");     Scanner systemPut=new Scanner(System.in);     sc=systemPut.next().charAt(0);     switch (sc){  case 'p':      System.out.println("请输入数据：");      Scanner addNum=new Scanner(System.in);      int num = addNum.nextInt();      stack.push(num);      break;  case 'o':      stack.pop();      break;  case 's':      stack.show();      break;  case 'e':      loop=false;      break;  default :      break;     } }    }}class StackLinkedList{    public int maxSize;    public Node bottom=new Node(0);    //初始化    public StackLinkedList(int maxSize){ this.maxSize=maxSize;    }    //链表是否为空    public boolean isEmpty(){ return bottom.next==null;    }    //链表是否已满    public boolean isFull(){boolean result=false;int size=0;Node temp=bottom.next;while (true){    if (temp==null){ break;    }    temp=temp.next;    size++;}if (size==maxSize){    result=true;}return result;    }    //入栈    public void push(int no){ if (isFull()){     System.out.println("链表已满，请出栈~~~"); }else{     Node node=new Node(no);     Node temp=bottom;     while(true){  if (temp.next==null){      break;  }  temp=temp.next;     }     temp.next=node; }    }    //出栈    public int pop(){ if (isEmpty()){     throw new RuntimeException("链表为空，请入栈~~~"); } Node temp=bottom; int num=0; while (temp!=null){     if (temp.next.next==null){  num= temp.next.no;  temp.next=null;  break;     }     temp=temp.next; } return num;    }    //遍历栈元素    public void show(){ Stack stack=new Stack(); Node temp=bottom.next; while (temp!=null){     stack.push(temp);     temp=temp.next; } while(stack.size()>0){     System.out.println(stack.pop()); }    }}class Node{    public Node next;    public int no;    public Node(int no){this.no=no;}    @Override    public String toString() { return "Node{" +  ", no=" + no +  '}';    }}

总结

1.栈，因为只是对一头进行操作，所以实现了先进后出的体现
2.本文使用的是链表，也可以使用数组；但是使用链表实现栈，可以做到栈容量的不确定性

书法艺术字体