精华内容
下载资源
问答
  • 基于双向链表实现: 栈 队列
    千次阅读
    2022-03-13 06:21:18

     基于双向链表实现栈与队列:

            内部类DoubleLinkedList<T> 可以构建双向链表, 提供4中操作: 头插 ,头取 ,尾插 ,尾取 .所以可以称为"双端双向链表"(自己起的 便于理解),这两端分别由head 和 tail 分别引用. 通常链表无论是单向还是双向链表都只有一个 head, 但为了实现基于"双端双向链表"的 "栈" 和 "队列",这四种操作头插 和 头取 就是 "栈" ,头插 尾取就是"队列".

             栈和队列都是逻辑上的结构,在数据结构中是ADT,实现的方式可以基于数组或链表或其它.      

    
    /**
     * 栈和队列的操作
     * <p>
     * 栈和队列实现:
     *      1.双向链表实现
     *      2.数组实现
     *
     * 基于双向链表实现
     */
    public class StackOrQueueBaseOnLink {
    
        private static class MyStack<T>{
            private final DoubleLinkedList<T> linkedList = new DoubleLinkedList<>();
            public void push(T t){
                linkedList.addToHead(t);
            }
            public T pop(){
                return linkedList.popFromHead();
            }
        }
    
        private static class MyQueue<T>{
            private final DoubleLinkedList<T> linkedList = new DoubleLinkedList<>();
            public void push(T t){
                linkedList.addToHead(t);
            }
            public T pop(){
                return linkedList.popFromTail();
            }
        }
    
        /**
         * 双端双向链表: 头尾可进可出
         *
         * @param <T> 存储类型
         */
        private static class DoubleLinkedList<T> {
            public Node<T> head;
            public Node<T> tail;
    
            /*头部弹出*/
            public T popFromHead(){
                if(this.head == null){
                    return null;
                }
                Node<T> curr = head;
                if(head == tail){
                    head = null;
                    tail = null;
                }else{
                    head = head.next;
                    head.prev = null;
                    curr.next = null;
                }
                return curr.val;
            }
            /*尾部弹出*/
            public T popFromTail(){
                if(this.tail == null){
                    return null;
                }
                Node<T> curr = tail;
                if(tail == head){
                    tail = null;
                    head = null;
                }else{
                    tail = tail.prev;
                    tail.next = null;
                    curr.prev = null;
                }
                return curr.val;
            }
    
            public void addToHead(T val) {
                Node<T> curr = new Node<>(val);
                if (head == null) {
                    head = curr;
                    tail = curr;
                } else {
                    //头插curr
                    curr.next = head;
                    head.prev = curr;
                    //重置head
                    head = curr;
                }
            }
    
            public void addToTail(T val){
                Node<T> curr = new Node<>(val);
                if(tail == null){
                    head = curr;
                    tail = curr;
                }else{
                    //尾插
                    tail.next = curr;
                    curr.prev = tail;
                    tail = curr;
                }
            }
        }
    
        private static class Node<T> {
            public T val;
            public Node<T> prev;
            public Node<T> next;
    
            public Node(T val) {
                this.val = val;
            }
        }
    }
    

      左神算法学习

    更多相关内容
  • 相信大家都明白 LinkedList 是基于双向链表实现的,本篇文章主要讲解一下双向链表实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下。 什么是链表? 简单的来讲一下什么是链表:首先链表是一种线性的...
  • 主要为大家详细介绍了C语言链表实现图书管理系统,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 使用链表实现的c++图书管理管理程序 可以对图书和供应商两个类进行管理和统计 大学作业,可供学生参考
  • C语言数组形链表实现

    2019-01-27 21:28:21
    原创C语言数组形链表操作的具体接口,定义简单,逻辑清晰
  • 改源代码用链表实现了学生信息的增删改查,读写入(出)文件,同时实现了学生信息的排序,链表的清空,插入。双向链表的插入排序,能够帮助学习链表。
  • C语言链表实现字符串输入、查找、删除等 C语言实验内容
  • 栈的实现(C语言)数组实现以及链表实现源码,以及各个功能测试代码函数等 和后缀式转前缀式的用例
  • 通过循环链表实现约瑟夫环问题,用c语言实现。属于数据结构部分内容
  • 使用C++语言,结合单链表的基本操作,实现二叉树的存储,前序、种序、后序遍历及其他基本操作
  • 双向链表实现

    2018-06-14 22:45:11
    数据结构小代码,改自 《数据结构与算法分析C++版》 源代码 ...2. 利用双向链表实现2个一元稀疏多项式的加法运算,运算结果得到的链表要求按照指数升序有序,并遍历输出指数升序、指数降序的多项式。
  • 链表实现两个多项式相加的C语言源代码,两个多项式相加时,同类项的系数相加,无同类项的系数保持不变,想家完后再按升幂排序,结果放回链表中。是数据结构的作业,改编了网上的代码,运行结果正确。
  • Java实现双向链表

    2020-03-22 23:22:42
    用Java定义一个双向链表实现链表的基本操作: 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表
  • 链表实现多级菜单

    2012-05-04 13:09:52
    本例实现单片机的多级菜单,过程是用链表实现的。
  • 逆置数组实现和链表实现(C语言实现) 数组和链表.pdf
  • 主要介绍了JS基于对象的链表实现与使用方法,结合实例形式分析了链表的原理及javascript定义与使用链表的相关操作技巧,需要的朋友可以参考下
  • 学生成绩管理系统C语言实现报告,链表实现,内含流程图,代码,一切以报告形式完成。
  • 用循环链表实现队列操作 讲解详细 通过多次编译 可以运行的
  • 使用链表实现

    千次阅读 2021-07-10 14:18:44
    使用自定义链表实现栈,自定义链表的实现:自定义链表 具体实现 栈接口 public interface Stack<T> { /** * 添加元素 * @param t */ void push (T t); /** * 元素出栈 * @return */ T pop(); ...

    前言

    使用自定义链表实现栈,自定义链表的实现:自定义链表


    具体实现

    • 栈接口
    public interface Stack<T> {
    
        /**
         * 添加元素
         * @param t
         */
        void push (T t);
    
        /**
         * 元素出栈
         * @return
         */
        T pop();
    
        /**
         * 查看栈顶元素
         * @return
         */
        T peek();
    
        /**
         * 获取大小
         * @return
         */
        int getSize();
    
        /**
         * 是否为空
         * @return
         */
        boolean isEmpty();
    
    }
    
    • 实现类
    public class LinkedListStack<T> implements Stack<T> {
    
        /**
         * 链表
         */
        private LinkedList<T> list;
    
        /**
         * 构造方法
         */
        public LinkedListStack() {
            list = new LinkedList<>();
        }
    
        /**
         * 添加元素
         * @param t
         */
        @Override
        public void push(T t) {
            list.addFirst(t);
        }
    
        /**
         * 元素出栈
         * @return
         */
        @Override
        public T pop() {
            return list.removeFirst();
        }
    
        /**
         * 获取栈顶元素
         * @return
         */
        @Override
        public T peek() {
            return list.getFirst();
        }
    
        /**
         * 获取大小
         * @return
         */
        @Override
        public int getSize() {
            return list.getSize();
        }
    
        /**
         * 是否为空
         * @return
         */
        @Override
        public boolean isEmpty() {
            return list.isEmpty();
        }
    
        /**
         * 重写toString方法
         * @return
         */
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("Stack: top ");
            res.append(list);
            return res.toString();
        }
    
        public static void main(String[] args) {
            LinkedListStack<Integer> stack = new LinkedListStack<>();
    
            for (int i = 0; i < 5; i++) {
                stack.push(i);
                System.out.println(stack);
            }
    
            stack.pop();
            System.out.println(stack);
        }
    
    }
    
    - End -
    一个努力中的公众号
    关注一下吧
    展开全文
  • C++ 双向链表实现学生管理系统
  • 链表实现集合运算 链表实现集合交并差运算
  • 主要介绍了java链表应用--基于链表实现队列,结合实例形式分析了java基于链表实现队列尾指针相关操作使用技巧,需要的朋友可以参考下
  • C语言数据结构之栈(链表实现)

    千次阅读 2020-08-11 22:24:24
    C语言数据结构之栈(链表实现) tips:前些天学习了单链表的增删改查,对于双向链表和循环链表而言,无非就是对单链表的指针进行稍微的变换。今天来看看c语言数据结构之栈的实现以及栈的各种操作。 栈的特点是先进后出...

    C语言数据结构之栈(链表实现)

    tips:前些天学习了单链表的增删改查,对于双向链表和循环链表而言,无非就是对单链表的指针进行稍微的变换。今天来看看c语言数据结构之栈的实现以及栈的各种操作。


    栈的特点是先进后出,后进先出,因此我们很容易联想到去使用单链表的头插法,和头部删除法去实现入栈和出栈的操作。


    首先我们来看一下栈的各种操作的实现思路以及具体实现过程
    准备工作:
    • 创建栈中元素的结构体
    typedef struct tag 
    {
    	int val;//栈(链表)的值,即数据域部分
    	struct  tag *pNext;//后继指针
    }Node,*pNode;
    
    • 创建栈的结构体
    typedef struct tagStack
    {
    	pNode phead;//链表(tag)的头指针
    	int size;//栈的大小(栈中元素个数)
    }Stack,*pStack;
    
    • 准备打印输出函数
    //打印栈元素
    void print_stack(pStack p)
    {
    	pNode pcur = p->phead;//工具人保存当前结点信息
    	while (pcur!=NULL)
    	{
    		printf("%d\n",pcur->val);
    		pcur = pcur->pNext;
    	}
    
    	printf("---------------------------------\n");
    }
    

    1、入栈(push)
    思路:

    • 为链表创建新结点,并将其初始化;
    • 采用头插法为链表添加新结点入栈;
    • 入栈操作完成后,将栈的size+1;

    具体实现:

    //入栈
    void push(pStack p, int val)
    {
    	pNode pnew = (pNode)malloc(sizeof(Node));//申请新结点空间(申请的是tag)
    
    	//新结点初始化
    	pnew->val = val;
    	pnew->pNext = NULL;
    
    	//入栈,头插法
    	if (p->phead == NULL)//判断链表是否为空,为空,头指针指向新结点
    	{
    		p->phead = pnew;
    	}
    	else //不为空,则头插法
    	{
    		//新结点变成新的头结点
    		pnew->pNext = p->phead;
    		p->phead = pnew;
    	}
    	p->size++;
    }
    

    2、出栈(pop)
    思路:

    • 采用头部删除法,删除链表第一个结点(即栈顶元素),完成出栈;
    • 出栈操作完成后,将栈的size-1;

    具体实现:

    //出栈,头部删除法
    void pop(pStack p)
    {
    	pNode pcur = p->phead;//工具人保存当前结点信息
    	//判断链表是否为空
    	if (p->phead == NULL)
    	{
    		printf("该链表为空!\n");
    	}
    	else
    	{
    		//头部删除法
    		p->phead = pcur->pNext;
    		free(pcur);
    		p->size--;
    	}
    }
    

    3、返回栈顶元素(top)
    思路:

    • 当栈为空时直接返回EOF;
    • 当栈不为空时,直接返回链表头结点的val(即栈顶元素的值);

    具体实现:

    //返回栈顶元素
    int top(pStack p)
    {
    	//判断链表是否为空
    	if (p->phead == NULL)
    	{
    		return EOF;
    	}
    	else
    	{
    		//返回栈顶元素
    		return p->phead->val;
    	}
    
    }
    

    4、判断栈是否为空(empty)
    思路:

    • 当链表头指针为空时,栈即为空;
    • (或者)当栈的size==0时,栈为空;

    总之判断方法很多,大家可以尽情发挥。

    具体实现:

    //判断栈是否为空
    int empty(pStack p)
    {
    	//判断链表是否为空
    	if (p->phead == NULL)
    	{
    		return 0;
    	}
    	else
    	{
    		return 1;
    	}
    }
    

    5、返回栈中元素个数(size)
    思路:

    • 当链表为空时,返回0;
    • 当链表不为空时,返回栈的size;

    这个实现方法很多,大家可以尽情发挥。

    具体实现:

    //返回栈中元素个数
    int size(pStack p)
    {
    	//判断链表是否为空
    	if (p->phead == NULL)
    	{
    		return 0;
    	}
    	else
    	{
    		return p->size;
    	}
    }
    

    至此栈的基本操作我们已经全部实现了,接下来我们在main()函数中测试一下:

    int main()
    {
    	//栈的操作,链表实现栈stack
    	
    	Stack s;//定义一个栈
    	int i;//入栈的值
    	char panduan;//用来判断是否弹栈
    
    	//使用memset初始化结点(栈)
    	memset(&s, 0, sizeof(Stack));//栈的初始化,初始化为0
    
    	while (scanf("%d", &i) != EOF)
    	{
    		//入栈
    		push(&s, i);		
    	}
    	//打印栈元素
    	printf("栈里面元素为:\n");
    	print_stack(&s);
    
    	//打印栈顶元素
    	printf("栈顶元素为:%d\n", top(&s));
    
    	//判断栈是否为空
    	if (empty(&s))
    	{
    		printf("栈不为空!\n");
    	}
    	else
    	{
    		printf("栈为空!\n");
    	}
    	//栈中元素个数
    	printf("栈中元素个数为:%d\n", size(&s));
    
    	printf("---------------------------------\n");
    
    	while (printf("是否弹栈?y/n:"),scanf("%c", &panduan) != NULL)
    	{
    		if (panduan == 'y')
    		{
    			//出栈
    			pop(&s);
    
    			//打印栈元素
    			print_stack(&s);
    
    
    			//打印栈顶元素
    			printf("栈顶元素为:%d\n", top(&s));
    
    			//判断栈是否为空
    			if (empty(&s))
    			{
    				printf("栈不为空!\n");
    			}
    			else
    			{
    				printf("栈为空!\n");
    			}
    			//栈中元素个数
    			printf("栈中元素个数为:%d\n", size(&s));
    
    			printf("---------------------------------\n");
    		}
    		else if(panduan == 'n')
    		{
    			break;
    		}
    	
    	}
    
    	return 0;
    }
    

    实现结果:

    在这里插入图片描述
    栈的操作到目前来说已经实现,希望对大家学习有所帮助,加油!


    tips:瞄准天上的星星,或许你永远也射不到,但却比你瞄准树梢射得高远。

    展开全文
  • 数据结构的实验,用链表实现对集合的相关运算。
  • c语言链表实现通讯录管理系统(完整版)

    千次阅读 多人点赞 2020-09-23 23:30:56
    通讯录管理系统是链表的常用应用,也是我们必须要掌握的一个用链表实现的小项目制作。 下面来看代码 #include <stdio.h> #include <stdlib.h> typedef struct //定义每个人员信息结构体 { char num[5]...

    通讯录管理系统是链表的常用应用,也是我们必须要掌握的一个用链表实现的小项目制作。
    下面来看代码

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct  //定义每个人员信息结构体 
    {
    	char num[5]; //编号 
    	char name[9];//姓名 
    	char sex[3]; //性别 
    	char phone[13]; //电话 
    	char addr[31]; //地址 
     }DataType;
     typedef struct node  //定义链表类型 
     {
     	DataType data; //数据域 
     	struct node *next; //指针域 
      }ListNode;
    typedef ListNode *LinkList;
    void CreateList(LinkList &L,int m)//通讯录链表的建立 
    { int i;
      LinkList s,r;
      L=(LinkList)malloc(sizeof(ListNode));
      L->next=NULL;
      r=L; //尾节点 
    
      for(i=0;i<m;i++)
      {  s=(LinkList)malloc(sizeof(ListNode)); //新建的节点 
         printf("输入第%d位编号:",i+1);
         scanf("%s",&s->data.num);
         printf("\n输入姓名:");
         scanf("%s",&s->data.name);
         printf("\n输入性别:");
         scanf("%s",&s->data.sex);
         printf("\n输入电话:");
         scanf("%s",&s->data.phone);
         printf("\n输入地址:");
         scanf("%s",&s->data.addr);
         s->next=NULL;  
    	 r->next=s; //插入尾节点之后 
    	 r=s;
    	 
      }	
    
    }
    int ListLength(LinkList L) //求通讯录链表的长度 
    { LinkList p;
      int length=0;
      p=L->next;
      while(p)
      { length++;
        p=p->next;
      }
      return length;	
     } 
    int ListInsert(LinkList &L,int i,DataType d)  //通讯录链表的插入 
    { LinkList p,s;
      int length;
      length=ListLength(L); 
      p=L->next;
      int j=1;
      if(!p||i>length+1) //如果是空表或者查询位置不符合要求 
      return 0;
      while(p&&j<i-1)  //使p指向要添加位置的前一个元素 
      {
      	p=p->next;
      	j++;
      }
      s=(LinkList)malloc(sizeof(LinkList));
      s->data=d;
      s->next=p->next;
      p->next=s;
      return 1; 
    }
    int ListDelete(LinkList &L,int i)
    { LinkList p,q;//p为要删除的前一个节点,q为要删除的节点 
      p=L;
      int j=0;
      int length;
      length=ListLength(L); 
      if(!p||i>length) //如果是空表或者查询位置不符合要求 
      return 0;
      while(p&&j<i-1) //使p指向要删除位置的前一个元素 
      { p=p->next;
      	j++;
      }
      q=p->next; //q指向后一个元素  
      printf("\n被删除的人员信息为:\n");
      printf("\n编号:%s  姓名:%s  性别:%s  电话:%s 地址:%s",q->data.num,q->data.name,q->data.sex,q->data.phone,q->data.addr);
      p->next=q->next; 
      return 1; 	
     } 
    int GetElem(LinkList L,int i,DataType &d) //查询第i个成员信息 
    { LinkList p;
      p=L->next;
      int j=1;
      int length;
      length=ListLength(L); 
      if(!p||i>length) //如果是空表或者查询位置不符合要求 
      return 0;
      while(j<i)
      {p=p->next;
       j++;
      }
      d=p->data;
      return 1;
    	
    }
    
    void print(LinkList L) //打印通讯录人员信息 
    { LinkList p;
      p=L->next;
      while(p)
      {
      	printf("\n编号:%s  姓名:%s  性别:%s  电话:%s 地址:%s",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr);
      	p=p->next;
      }
    	
     } 
     void menu()
     { printf("--------------------------------------------1.通讯录链表的建立----------------------------------------------------------");
       printf("\n--------------------------------------------2.通讯者节点的插入----------------------------------------------------------");
       printf("\n--------------------------------------------3.通讯者节点的查询----------------------------------------------------------");
       printf("\n--------------------------------------------4.通讯者节点的删除----------------------------------------------------------");
       printf("\n--------------------------------------------5.通讯录链表的输出----------------------------------------------------------");
       printf("\n--------------------------------------------0.退出管理系统--------------------------------------------------------------");
     }
     int main()
     {
     	LinkList L;
     	DataType d,d1;
     	int m,location,length,choose;
     	menu();
     	p:
     	printf("\n请输入你的选项:");
     	scanf("%d",&choose);
     	switch(choose)
     	{ case 1:printf("请输入通讯录人数:");scanf("%d",&m);CreateList(L,m);goto p;
     	  case 2:printf("\n输入要插入的位置:");scanf("%d",&location);printf("输入插入人员的编号:"); scanf("%s",&d.num);printf("\n输入姓名:"); scanf("%s",&d.name); printf("\n输入性别:");scanf("%s",&d.sex);printf("\n输入电话:");scanf("%s",&d.phone);printf("\n输入地址:");scanf("%s",&d.addr);ListInsert(L,location,d);goto p;
    	  case 3:printf("\n请输入查询位置");scanf("%d",&location);GetElem(L,location,d); printf("查询到的人员信息为:\n");printf("\n编号:%s  姓名:%s  性别:%s  电话:%s 地址:%s",d.num,d.name,d.sex,d.phone,d.addr);goto p;
    	  case 4:printf("\n输入要删除的位置:");scanf("%d",&location);ListDelete(L,location);goto p; 
    	  case 5:print(L);goto p;
    	  case 0:printf("系统已退出。");exit(0);
    	  default:printf("输入错误,请重新输入");goto p;
    	 }
     	return 0;
     }
    

    下面是运行结果图
    在这里插入图片描述

    展开全文
  • 使用线程安全型双向链表实现简单 LRU Cache 模拟

    千次阅读 多人点赞 2021-11-16 09:11:22
    使用线程安全型双向链表实现简单 LRU Cache 模拟目录????博主介绍前言1、动机1.1、要解决的问题2、系统设计2.1、系统总体框架2.2、系统功能模块2.3 系统整体流程3、数据结构设计4、关键技术与系统实现4.1、生成访问...
  • 约瑟夫环的链表实现(C++) 采用链表方式解决问题,代码简单,书写格式规范,有相应注释以及测试小模块。
  • STM32用链表实现多级菜单

    热门讨论 2012-10-02 11:23:15
    链表实现多级菜单,STM32彩屏显示多级菜单
  • 使用双向链表实现快速排序,C语言,有详细注释
  • 多项式加法运算(链表实现

    千次阅读 多人点赞 2021-04-24 13:09:04
    我们用链表存储一个多项式,那么该链表的每一个结点就代表多项式的某一项。所以我们的每一个结点必须包含三个信息:多项式的系数、多项式的指数以及指向下一个结点的指针。 typedef int SLTDataType;//指数、系数...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 624,996
精华内容 249,998
关键字:

链表实现

友情链接: MyUnit.rar