type
status
date
slug
summary
tags
category
icon
password
前言
工作之余,学习一下数据结构与算法,今天学习数据结构:“栈”。笔者有一个坏习惯,一看就会,一写就废。所以笔者准备亲自写使用单向链表实现栈
提示:以下是本篇文章正文内容,下面案例可供参考
一、栈是什么?
小编的理解:
1.一串有顺序的结构
2.只能从同一个位置取出元素或者添加元素
3.不能从中间存元素或者取元素
二、实现步骤
1.定义node节点
既然要实现链表,那就必须要有两个成员变量,来表示链表的节点
- 下一个节点
- 当前节点的编号
class Node{ public Node next; public int no; public Node(int no){this.no=no;} @Override public String toString() { return "Node{" + ", no=" + no + '}'; } }
2.栈结构的定义
要保有栈的特性,栈是有一定的容量限制,链表的头结点作为链表的指引
- maxSize代表栈的空间
- 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.本文使用的是链表,也可以使用数组;但是使用链表实现栈,可以做到栈容量的不确定性
- 作者:程序员小舟
- 链接:https://codezhou.top/article/%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8%E6%A0%88%E7%9A%84java%E5%AE%9E%E7%8E%B0%20%E8%AF%A6%E7%BB%86%E8%AE%B2%E8%A7%A3
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。