精华内容
下载资源
问答
  • 链表栈
    2022-03-13 14:23:53
    
    
    1. 单项链表: 只有头节点,对其进行操作时需要时刻考虑下次操作时节点是否还在.通常需要先
    记录下一个节点,然后再操作.对于一些不会改变链表指向的操作通常返回的是头节点,而对于
    像反转链表这样的操作就需要返回新的头,这个头通常为操作时使用的prev节点.
    
    2. 双向链表: 只有一个头,只不过每个节点有指向前一个和后一个节点的指针,用于定位节点的
    前一个或或一个节点,在对其进行操作时需要考虑前后指针的指向该如何处理
    
    3. 单双链表的逆序问题: 对于单链表逆序时将指针往回指就可实现逆序.对于双向链表只不过是
    多个一个前指针而已
    
    4. 双端双向链表: 也就是具有两个头的双向链表,一个头交head,一个头叫tail,如果它能够提供
    头插 头取 尾插 尾取,就可以作为轻易实现栈或队列的基础.头插 头取 就是栈结构,头插 尾取就
    是队列结构
    
    5.栈: FILO(先进后出) 是抽象的数据结构ADT类型,可通过链表和数组实现
    
    6.队列: FIFO(先进先出) 是抽象的数据结构ADT类型,可通过链表和数组实现
    
    7.栈实现队列: 构造两个栈,一个push栈,一个pop栈,将push栈中的数据pop出到pop栈,然后由pop
    栈pop就可以实现FIFO,但是需要注意:如果pop不为null那么就不能往里面push,会导致乱序,所以
    要构造好逻辑
    
    8.队列实现栈: 构造两个队列,一个data队列,一个help队列.data队列总是入队数据,help队列用于
    协助data拿出最后入队的数据,即栈的pop效果.为了达到使用队列实现的"弹栈"效果,需要将data队列
    中的数据出队,然后入队到help队列,data队列中保留一个元素,然后出队即可实现"弹栈".下一次"弹栈"
    操作时原先的data队列已经空了,就应该承担help的角色,而原先的help就承担了data的角色,所以需
    要交换两个队列的角色,其实交换逻辑很简单,就像数组排序时那样交换即可,虽然这里是引用,但是java
    永远都是值传递的,直接换就行,以此往复即可使用队列模拟栈的效果
    
    
    
    

    更多相关内容
  • 节点的数据设计具有一般性(使用void *data),使用链表栈实现本功能,且栈的Top指针作为每个函数的形式参数。最后以int型序号管理为实例,演示实验功能。ac_impl.c负责输出选择菜单项;test_impl.c中实现对菜单的...
  • 顺序栈和链表栈(链栈)的初始化栈、判断栈是否为空、得到栈顶元素、清空栈、销毁栈、检测栈长度、入栈、出栈。程序可测试。
  • 链表栈递归。 给定两个链表,分别表示两个非负整数。它 们的数字逆序存储在链表中,且每个结点只 存储一个数字,计算两个数的和,并且返回 和的链表头指针
  • 主要介绍了Java数据结构之链表、队列、树的实现方法,结合实例形式分析了Java数据结构中链表、队列、树的功能、定义及使用方法,需要的朋友可以参考下
  • 基于c++链表栈

    2018-05-17 20:25:31
    c++实现链表栈堆,链式链式堆链式队列,调试好长时间,刚学c++不就,老师不值得作业
  • 链表栈实现

    2014-07-23 10:05:52
    学习数据结构过程中,亲自在VC++上编译通过的链表栈的实现源代码,与大家共享。
  • 在之前的博客中,分别实现了基于数组的和基于链表。下面来使用代码对比我们自己实现的的性能差异: private static double testStack(Stack<Integer> s, int opCnt) { long startTime = ...

    在之前的博客中,分别实现了基于数组的栈和基于链表的栈。

    下面来使用代码对比我们自己实现的栈的性能差异:

     private static double testStack(Stack<Integer> s, int opCnt) {
            long startTime = System.nanoTime();
    
            for (int i = 0; i < opCnt; i++) {
                s.push(i);
            }
    
            for (int i = 0; i < opCnt; i++) {
                s.pop();
            }
    
            long endTime = System.nanoTime();
    
            return (endTime - startTime) / 1000000000.0;
        }

    上面的代码实现:对栈进行opCnt次入栈和出栈操作,记录所消耗的时间。(注:nonoTime的单位是ns,将结果转换为s,除以10的9次方)

    首先将opCnt设置为10 0000 来看看性能差异:

     public static void main(String[] args) {
            ArrayStack<Integer> arrayStack = new ArrayStack<Integer>();
            LinkedStack<Integer> linkedStack = new LinkedStack<Integer>();
            int opCnt = 100000;
            double time1 = testStack(arrayStack, opCnt);
            double time2 = testStack(linkedStack, opCnt);
            System.out.println("arrayStack:" + time1 + "s");
            System.out.println("linkedStack:" + time2 + "s");
    
        }

    结果:

    arrayStack:0.020232116s
    linkedStack:0.016551687s

    将opCnt设置为100 0000:

    结果:

    arrayStack:0.094751187s
    linkedStack:0.657009347s

    将opCnt设置为1000 0000:

    arrayStack:3.780388172s
    linkedStack:9.333468302s

    总结:

    基于数组的栈是在数组尾部进行入栈和出栈操作,因此实现复杂度为O(1);

    基于链表的栈是在链表头部进行入栈和出栈操作,因此实现复杂度也为O(1);

    因此两者的性能不会差很多,在opCnt=1000 0000时,arrayStack的性能比linkedStack性能要好。原因是linkedStack要进行大量的new操作,在opCnt较小的情况下,体现不出性能差异;而在操作次数大时,arrayStack性能优势就体现出来了。

    当前这种性能的比较还是比较粗糙的,但是也能粗略的反映问题。







    展开全文
  •   链式:就是一种操作受限的单向链表,每次入栈一个元素,向链表中添加一个节点,出栈一个元素,释放一个节点。因为具有“后进先出”的特点,如果每次在链表的尾部进行插入和删除,就要遍历整个链表来找到尾...

      链式栈:就是一种操作受限的单向链表,每次入栈一个元素,向链表中添加一个节点,出栈一个元素,释放一个节点。因为栈具有“后进先出”的特点,如果每次在链表的尾部进行插入和删除,就要遍历整个链表来找到尾节点。而在头部进行插入和删除时,只需根据头指针即可找到链表的首元素结点。而无需遍历链表。所以链式栈的出,入栈通过对链表进行头删和头插来实现。

    有关链表的知识先阅读这篇文章:LinkedList

    代码清单

    LinkedListStack.h

    #ifndef C___LINKEDLISTSTACK_H
    #define C___LINKEDLISTSTACK_H
    #include "LinkedList.h"
    template<typename T>
    class Stack {
    public:
        virtual int getSize()const = 0;
        virtual bool isEmpty()const = 0;
        virtual void push(T& e) = 0;
        virtual T pop() = 0;
        virtual T peek()const = 0;
    };
    
    template<typename T>
    class LinkedListStack : public Stack<T> {
    public:
        LinkedListStack();
        int getSize()const;
        bool isEmpty()const;
        void push(T&e);
        T pop();
        T peek()const;
        void print()const;
    private:
        LinkedList<T>*list;
    };
    
    template<typename T>
    int LinkedListStack<T>::getSize() const {
        return list->getSize();
    }
    
    template<typename T>
    bool LinkedListStack<T>::isEmpty() const {
        return list->isEmpty();
    }
    
    template<typename T>
    void LinkedListStack<T>::push(T& e) {
        list->addFirst(e);
    }
    
    template<typename T>
    T LinkedListStack<T>::pop() {
        return list->removeFirst();
    }
    
    template<typename T>
    T LinkedListStack<T>::peek()const {
        return list->getFirst();
    }
    
    template<typename T>
    void LinkedListStack<T>::print() const {
        std::cout << "Stack: size = " << list->getSize() << std::endl;
        std::cout << "bottom ";
        list->print();
        std::cout << " top" << std::endl;
    }
    
    template<typename T>
    LinkedListStack<T>::LinkedListStack() {
        list = new LinkedList<T>();
    }
    
    #endif //C___LINKEDLISTSTACK_H
    

    main.cpp

    int LinkedListStack()
    {
       LinkedListStack<int>*ls = new LinkedListStack<int>();
       for(int i = 0;i<10;++i)
       {
           ls->push(i);
           ls->print();
       }
       cout<<"isEmpty()"<<ls->isEmpty()<<endl;
       cout<<"getSize()"<<ls->getSize()<<endl;
       cout<<"peek"<<ls->peek()<<endl;
       cout<<"pop"<<ls->pop()<<endl;
       ls->print();
       return 0;
    }
    
    展开全文
  • Java实现--链表栈

    2018-09-27 18:18:34
    链表实现: 其实就只是换了个名字,包装起来而已,没什么新的东西。 注:这里插入结点的方法应为在头部插入结点(与输入的值逆置),这样构成的才是 关于定义链表可以查看我的另一篇博文...

     用链表实现栈:

    其实就只是换了个名字,包装起来而已,没什么新的东西。

    注:这里插入结点的方法应为在头部插入结点(与输入的值逆置),这样构成的才是栈

    关于定义链表可以查看我的另一篇博文https://blog.csdn.net/szlg510027010/article/details/82862965

    /**
     * 用链表实现栈
     * @author Administrator
     *
     */
    public class LinkStack {
    	private LinkList theList;
    	
    	public LinkStack(){
    		theList = new LinkList(); 
    	}
    	
    	//入栈
    	public void push(int data) {
    		theList.Insert(data);
    	}
    	
    	//出栈
    	public int pop(){
    		return theList.delete().data;
    	}
    	
    	//检查栈是否为空
    	public boolean isEmpty() {
    		return theList.isEmpty();
    	}
    	
    	public void displayStack() {
    		System.out.print("Stack (top--->bottom): ");
    		theList.displayList();
    	}
    }
    
    /**
     * 测试(链表)栈
     * @author Administrator
     *
     */
    public class TestLinkStack {
    	public static void main(String[] args) {
    		LinkStack theStack = new LinkStack();
    		theStack.push(20);
    		theStack.push(40);
    		
    		theStack.displayStack();
    		
    		theStack.push(60);
    		theStack.push(80);
    		
    		theStack.displayStack();
    		
    		theStack.pop();
    		theStack.pop();
    		
    		theStack.displayStack();
    	}
    }
    

    测试结果:

    Stack (top--->bottom): {40} {20} 
    Stack (top--->bottom): {80} {60} {40} {20} 
    Stack (top--->bottom): {40} {20} 
     

    展开全文
  • 双向链表实现

    2022-07-16 23:30:37
    用双向链表实现结构
  • c++写的链表栈

    2014-10-30 22:50:28
    可以作为c++课程初学者使用的作业,或者作为初学者的研究。用链表写好的,亲测可用,同时具有保存和读取功能
  • C_链表和队列

    千次阅读 2022-03-19 20:24:36
    链表和队列
  • 数据结构 链表 C语言 单向链表
  • 链表实现
  • 链表模拟
  • 的实现(C语言)数组实现以及链表实现源码,以及各个功能测试代码函数等 和后缀式转前缀式的用例
  • 链表----

    2022-03-04 13:47:35
    //链式的结构体声明: 直接用单链表 //链式的结构体声明: 直接用单链表的即可; typedef struct LStack { ELEM_TYPE data; //数据域 struct LStack* next; //指针域 }LStack, * PLStack; //链栈可执行函数声明...
  • 数据结构:链表

    2021-12-30 17:09:14
    1. 链表 1.1 什么是链表 链表是数据结构之一,其中的数据呈线性排列。 在链表中,数据的添加和删除都较为方便,访问比较耗费时间。 链表的数据元素是一个一个串联在一起的,这一串数据形成的结构就是“链表”。它就...
  • 基于双向链表实现: 队列

    千次阅读 2022-03-13 06:21:18
    基于双向链表实现与队列: 内部类DoubleLinkedList<T> 可以构建双向链表, 提供4中操作: 头插 ,头取 ,尾插 ,尾取 .所以可以称为"双端双向链表"(自己起的 便于理解),这两端分别由head 和 tail 分别引用.通常...
  • 链表实现

    2020-10-23 09:55:13
    单链表作为底层,实现的数据结构 的实现: package SingleLinkedListStack; import ArrayStack.Stack; import SingleLinkedList.Node; import SingleLinkedList.SingleLinkedList;...// 用链表作为的底
  • C++使用链表实现

    2021-07-16 15:00:54
    的特点: 1.压入栈时压在最上面 2.弹出时弹出最上面 源码: #include<iostream> using namespace std; struct Node { int data; Node* next; }; class stack { public: Node* head; int len; //...
  • 自己编写的 初学 忘指教 只有简单的3中操作 初始化 插入数据 删除数据 而对于基本的查找 置空 求长度在此基础上仿照编写即可
  • java用链表实现结构

    2022-01-16 16:51:03
    首先看我的链表类 public class ListNode { public int val; public ListNode next; public ListNode(){} public ListNode(int val){ this.val = val; } public ListNode(int val,ListNode next){this.val = ...
  • Java基于链表的实现

    千次阅读 2022-03-26 14:32:01
    1、什么是 (Stack)是一种线性存储结构,它具有如下特点: (1)中的数据元素遵守”先进后出”(First In Last Out)的原则,简称FILO结构。...3、具体代码(我们使用链表来完成基本操作,并且使
  • 链表实现

    2022-05-06 12:02:17
    本文用链式存储结构实现了,采用泛型编程,可移植性较好
  • 用双向链表实现(C)

    千次阅读 2022-05-15 23:22:26
    一个所含元素个数size #pragma once #include #include #include #include typedef int STDataType; //定义各个节点 typedef struct StackNode { struct Stack* next; struct Stack* prev; STDataType data; }...
  • C语言 实现 链表栈

    万次阅读 2012-04-18 20:12:18
    typedef struct LinkStack //链表栈定义 { PNode top; //栈顶指针 }LinkStack; typedef struct LinkStack * PLinkStack; //链表栈的指针类型 //创建一个空栈 PLinkStack createEmptyStack( void ); //判断栈是否...
  • 关于c语言的程序与习题 有关于顺序链表 单链表 双链表 等程序,运用相关软件打开并运行,就可以看到效果
  • 链表栈的入栈和出栈操作

    千次阅读 2017-11-24 16:23:58
    链表栈的入栈和出栈操作 #include #include typedef int ElemType; typedef struct linknode {  ElemType data; //数据域  struct linknode *next; //指针域 }ListStack; //入栈 /*  已知变量:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 217,919
精华内容 87,167
关键字:

链表栈

友情链接: xa143.zip