IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 栈的数组与链表实现 -> 正文阅读

[数据结构与算法]栈的数组与链表实现

一、特性及常用操作

????????栈是一个动态集合,作为数据结构中的一种基本数据类型,其实现了一种后进先出(last-in,firtst-out,缩写LIFO)的策略。

????????作用与栈上的insert操作常称为入栈(push),无参数的delete操作常称为出栈(pop)。栈结构类似于我们生活中厨房存放的盘子,最后放入(push)的盘子则在一层层盘子的最顶端。当我们需要使用盘子时,第一个取出(pop)也是放在最顶端位置的盘子。

二、两种实现

1,使用数组实现

????????我们定义一个容器大小为15的数组,并定义一个指向下一个入栈位置的索引top,初次索引位置为0。当我们入栈操作时,将入栈对象放置在top指向位置,完成后top索引进行+1。当我我们依次入栈5201后top为第五个位置角标4;

当我们进行出栈时,索引top先进行-1后指向当前栈顶元素,然后返回当前栈顶元素。

入栈操作

出栈操作

代码实现(不考虑容器溢出问题)

自定义栈实现类 MyStackUseArray

package com.xiaohui.basics.stack.array;


/**
 * 自定义栈,array实现(不考虑角标越界问题)
 * @author huizi
 */
public class MyStackUseArray{

    /**
     * 当前栈顶下一个位置角标
     */
    private int index = 0;

    /**
     * 默认的栈容器大小
     */
    private Integer[] array = new Integer[15];

    /**
     * 进栈操作
     *
     * @param val 进栈对象
     * @return 进栈对象
     */
    public Integer push(Integer val){
        array[index++] = val;
        return val;
    }

    /**
     * 出栈操作
     *
     * @return Integer 栈顶元素
     */
    public Integer pop(){
        Integer popVal = array[--index];
        array[index] = null;
        return popVal;
    }
}

测试类

package com.xiaohui.basics.stack;

import com.xiaohui.basics.stack.array.MyStackUseArray;
import com.xiaohui.basics.stack.linked.Node;

/**
 * 自定义栈演示
 *
 * @author huizi
 */
public class Application {

    public static void main(String[] args) {
        stackArrayTest();
    }

    private static void stackArrayTest() {
        MyStackUseArray stackUseArray = new MyStackUseArray();
        stackUseArray.push(5);
        stackUseArray.push(2);
        stackUseArray.push(0);
        stackUseArray.push(1);

        Integer pop = stackUseArray.pop();
        System.out.println(pop);
        Integer pop2 = stackUseArray.pop();
        System.out.println(pop2);
        Integer pop3 = stackUseArray.pop();
        System.out.println(pop3);
    }
}

控制台输出:

D:\Java\jdk1.8.0_131\bin\java.exe ...
1
0
2

Process finished with exit code 0

2,使用链表实现

? ? ? ? 使用链表结构实现则不需要指定容器大小,链表由一个个节点(包含存储值对象以及该节点的下一个节点的指针引用两部分组成)依次链接组成。根据栈的特性我们知道需要有一个记录当前栈顶元素的引用(即指针)指向当前栈顶元素top。每当入栈时我们需要将当前入栈对象的下一节点的指针修改为当前记录栈顶元素top所指向的对象。并将top指向新入栈对象。当出栈时,我们先返回top所指向对象,并将top修改为所返回对象的下一个节点指向对象。

入栈操作:

出栈操作:

代码实现

定义节点信息 Node:

package com.xiaohui.basics.stack.linked;

/**
 * 节点元素对象
 *
 * @author huizi
 */
public class Node {

    /**
     * 下一个节点
     */
    private Node next;

    /**
     * 当前节点值
     */
    private Integer value;

    public Node(Node next, Integer value) {
        this.next = next;
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }
}

?自定义栈实现:

package com.xiaohui.basics.stack.linked;

/**
 * 栈使用链表实现
 *
 * @author huizi
 */
public class MyStackUserLinked {
    /**
     * 指向栈顶元素的引用
     */
    private Node top = new Node(null,null);

    public Node push(Node val){
        // 获取当前栈顶对象,并这设置为进栈对象的下一个节点
        Node next = top.getNext();
        val.setNext(next);

        // 将栈顶引用指向进栈对象
        top.setNext(val);
        return val;
    }

    public Node pop(){
        // 获取当前栈顶元素
        Node topNode = top.getNext();
        // 设置新的栈顶元素
        Node newTopNode = topNode.getNext();
        top.setNext(newTopNode);
        return topNode;
    }
}

测试代码

package com.xiaohui.basics.stack;

import com.xiaohui.basics.stack.linked.MyStackUserLinked;
import com.xiaohui.basics.stack.linked.Node;

/**
 * 自定义栈演示
 *
 * @author huizi
 */
public class Application {

    public static void main(String[] args) {
        stackLinkedTest();
    }

    private static void stackLinkedTest() {
        MyStackUserLinked linkedStack = new MyStackUserLinked();
        linkedStack.push(new Node(null,5));
        linkedStack.push(new Node(null,2));
        linkedStack.push(new Node(null,0));
        linkedStack.push(new Node(null,1));

        Node pop = linkedStack.pop();
        System.out.println(pop.getValue());
        Node pop2 = linkedStack.pop();
        System.out.println(pop2.getValue());
        Node pop3 = linkedStack.pop();
        System.out.println(pop3.getValue());
    }
}

?打印输出:

D:\Java\jdk1.8.0_131\bin\java.exe ...
1
0
2

Process finished with exit code 0

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-04-29 12:21:18  更:2022-04-29 12:23:31 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 6:27:35-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码