type
status
date
slug
summary
tags
category
icon
password
AI summary

前言

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

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

一、栈是什么?

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

二、实现步骤

1.定义node节点

既然要实现链表,那就必须要有两个成员变量,来表示链表的节点
  1. 下一个节点
  1. 当前节点的编号

2.栈结构的定义

要保有栈的特性,栈是有一定的容量限制,链表的头结点作为链表的指引
  1. maxSize代表栈的空间
  1. bottom代表的是栈底元素,固定位置

3.栈的判断

3.1判断是否已满

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

3.2判断栈是否为空

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

4.栈的操作

4.1入栈

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

4.2出栈

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

5.(逆序)遍历所有栈节点

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

代码整合

总结

1.栈,因为只是对一头进行操作,所以实现了先进后出的体现 2.本文使用的是链表,也可以使用数组;但是使用链表实现栈,可以做到栈容量的不确定性
 
递归-八皇后问题(回溯算法)插值查找算法