我们在学习的阶段时,对一些数据结构的概念、用法,比如:栈。总是不那么熟悉,相信大部分初学者都感同身受,所以在此,我向大家分享一下自己如何将栈的概念、用法融汇贯通的。
对于数据结构中栈的学习,我认为可以分三个阶段:
1.字面理解阶段:
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶(Top),另一端为固定的一端,称为栈底(Bottom)。
(1)通常称插入、删除的这一端为栈顶(Top),另一端[先放入的数据一端]称为栈底(Bottom)。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出(Last In First Out)的线性表,简称为LIFO表。
栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前栈中"最新"的元素,即最后插入(进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除。
图例:
根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。
也就是说,栈是一种后进先出(Last In First Out)的线性表,简称为LIFO表。由此可见,栈对于插入、修改等操作不擅长。所以在此我就不对该操作进行基础实现。
2、画图理解阶段与3、具体基础实现
栈的基础操作具体包括了增加、删除、插入、修改等。
在这里我只对增加、删除、判断是否为空、栈的长度进行基础实现[包括了数组与链表实现]。
注意:该实现过程使用了泛型[温馨提示:泛型的概念与使用,我已经在之前的可变数组的基础实现中说过]
操作的步骤不是一成不变的,但又有一定的顺序,我只是写出了自己喜欢的顺序,但是你们可以自己拓展一下,看哪些步骤可交换,哪些不能交换。
1)实现栈的第一步是确定储存的数据的容器
a、基于数组
//定义一个储存数据的数组,初始化长度为0 Object[] src= new Object[0];
b、基于链表
不同于数组,栈的链表实现是基于链表的基础上的,所以必须定义一个结点类保存数据
/** * 链式结构内部结点类,单链表 * * @author Administrator * */ class Node<E> { // 内容,值 E data; // 对下一个结点的引用 Node<E> netx = null; //空的构造函数,用于构造空值的结点 public Node() { } //构造有值的结点 public Node(E e) { data = e; } } //栈的属性: // 定义一个储存数据的链表 private Node<E> head = null; //定义一个变量保存栈的长度 private int num=0;
2)增加操作
a、基于数组
图例:
如上图解析:将src数组的数据复制到dest临时数组中相应位置,再将新的数据放到dest数组中去,最后将dest数组赋予src数组,就还原了数组。
/** * 将数据压入栈中 * @param e 压入的数据 */ public void put(E e){ //定义一个新的空数组dest,数组长度比原数组大1 Object[] dest= new Object[src.length+1]; //将src数组的数据复制到dest数组里,位置不变,长度不变 System.arraycopy(src, 0, dest, 0, src.length); //将增加数据放入dest数组尾部 dest[dest.length-1]=e; //将dest数组赋予src数组,数组还原 src=dest; }
b、基于链表
图例:
如上图解析:先将新结点node的next指向head
再将head指向node结点,然后将栈的长度+1
/** * 将数据压入栈中 * * @param e * 压入的数据 */ public void put(E e) { //建立一个新结点node,值为e,默认无指向 Node<E> node = new Node<E>(e); //如果头结点为空,就将node结点置为头结点head if (head == null) { //将node结点置为头结点head head = node; } else {//否则头结点head就后移 //将node结点与头结点连接 node.netx = head; //头结点head后移 head = node; } //栈长度+1 num++; }
3)删除操作
a、基于数组
图例:
如上图解析:将src数组的数据复制到dest临时数组中相应位置【不包括src数组的最后一位】,再将新的数据放到变量e中去,再将dest数组赋予src数组,就还原了数组,最后返回输出e。
/** * 弹出栈顶数据 * @return 弹出的数据 */ public E poll(){ //定义一个新的空数组dest,数组长度比原数组小1 Object[] dest= new Object[src.length-1]; //将src数组的数据复制到dest数组里,位置不变,长度是dest的长度 System.arraycopy(src, 0, dest, 0, dest.length); //将栈弹出的栈尾数据放入变量e中 E e = (E)src[src.length-1]; //将dest数组赋予src数组,数组还原 src=dest; //返回弹出数据 return e; }
b、基于链表
图例:
如上图解析:先将新结点node的next指向head
再将head指向node结点的next指向的结点
将node结点的next指向null,然后将栈的长度-1 ,最后返回输出node.data
/** * 弹出栈顶数据 * * @return 弹出的数据 */ public E poll() { //如果栈内有数据,就弹出,否则返回null if(head!=null){ //建立一个新结点node,默认无指向 Node<E> node = new Node<E>(); //将node指向头结点 node=head; //头结点head的指向移到下一个结点 head=node.netx; //头结点的指向关系为null node.netx=null; //栈长度-2 num--; //返回弹出的值 return node.data; } //返回null return null; }
4)判断栈是否为空操作
/** * 判断栈是否为空,基于链表实现[基于数组实现:将num改成src.length] * * @return true/false */ public boolean isEmpty() { //如果栈长度是0就返回false if (num != 0) { return false; } else { //否则就返回true return true; } }
5)栈的长度
/** * 获得栈的长度,基于链表实现[基于数组实现:将num改成src.length] * * @return 栈的长度 */ public int size() { //返回栈长度 return num; }
相关推荐
Struts2值栈的理解Struts2值栈的理解Struts2值栈的理解
理解有栈无栈协程可能会有错误, 只是自己简单的理解之前一直没想明白了一个问题, 就是关于协程如何进行上下文切换.众所周知, 协程是分为有栈协程和无栈协程俩种.
(重点理解)详细介绍下Java虚拟机栈?(重点理解)一个方法调用另一个方法,会创建很多栈帧吗?栈指向堆是什么意思?递归的调用自己会创建很多栈帧吗?你能给我详细的介绍Java堆吗?(重点理解)能不能解释一下本地...
04 | 深入理解栈:从CPU和函数的视角看栈的管理所以,今天这节课,我们继续深入探讨一下栈这个话题,我会带你基于“符合人的直观思维”,也就是函数的层面和 CP
入栈和出栈是栈这种数据结构的基本操作,对于理解栈的工作机制和应用场景具有重要意义。以下是对这两个基本操作的详细解析,以及一些扩展性的内容,共计约1500字。入栈和出栈是栈这种数据结构的基本操作,对于理解栈...
1、理解栈的逻辑结构定义及特点、掌握栈的存储结构的描述、 实现栈的基本运算。 2、理解队列的逻辑结构定义及特点、掌握循环队列存储结构及其描述方法、掌握循环队列的基本运算。 二、实验内容: 1、建立顺序栈,并...
理解栈在程序设计中的应用。 2.实验环境 Visual C++ 6.0 3.实验报告内容 (1)给出栈的顺序存储结构定义。 (2)给出在顺序存储结构上实现栈的入栈操作的基本设计思想,并用C语言实现。 (3)给出在顺序存储结构上...
这是求迷宫的问题,是c语言程序的老师布置的作业,只是一个小程序
c语言栈操作源代码直接运行,帮助大家对栈的理解
堆和栈的区别 软件常识,面试必备,要想真正理解里面的含义,还得实际做一段时间的程序才能理解
一、实验目的 1、掌握栈的含义和存储结构;...1、认真阅读和理解与本实验有关的课本内容,预先写出源代码; 2、上机输入源程序、调试运行源程序,详细记录调试过程和运行结果; 3、为实验报告做准备。
Zigbee 协议栈简介 什么是 ZigBee 协议栈呢?...协议栈是协议的具体实现形式,通俗点来理解就是协议栈是协议和用户 之间的一个接口,开发人员通过使用协议栈来使用这个协议的,进而实现无线数 据收发
堆和栈的区别可以更深刻的解读堆栈,让我们更好的运用堆栈,学号计算机
文章通过简单的比喻和代码示例,使初学者能够轻松理解栈的原理和应用。 ### 适用人群 这篇文章主要面向编程初学者,特别是对栈数据结构感兴趣的读者。无论你是小学生还是刚开始接触编程的新手,这篇文章都会帮助你...
C语言一道练习如何建立栈和运用栈来进行一些操作的好题。里面涉及加减乘除括号的优先级考虑和入栈出栈的规则来实现...作为数据结构中比较重要的一个结构——栈,我们可以通过这道题更加好的理解栈的用途并熟悉栈的运用
笔记如何理解"栈"理解为叠在一起的盘子. 后进者先出, 先进者后出 FILO.栈是一种"操作受限"的线性表, 只允许在一端插入数据和删除数据.栈 和 数组, 队
栈的删除 插入以及很多的功能实现 能 让初学者更好的理解 毕竟是自己写的东西
该文档介绍了堆和栈的区别,对大家理解堆和栈有很好的帮助。
Java虚拟机栈也是线程私有的,它的生命周期与线程相同(随线程而生,随线程而灭) 2. 如果线程请求的栈深度大于虚拟机所允许的深度,将抛出StackOverflowError异常; 如果虚拟机栈可以动态扩展,如果扩展时无法申请...
栈和队列,主要是栈和队列的想法,能够更好地理解栈和队列