-
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; } } }
左神算法学习
更多相关内容 -
Java LinkedList 双向链表实现原理
2021-01-20 02:48:03相信大家都明白 LinkedList 是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下。 什么是链表? 简单的来讲一下什么是链表:首先链表是一种线性的... -
C语言链表实现图书管理系统
2020-08-28 05:32:19主要为大家详细介绍了C语言链表实现图书管理系统,具有一定的参考价值,感兴趣的小伙伴们可以参考一下 -
链表实现的c++图书管理程序
2020-01-10 13:12:22使用链表实现的c++图书管理管理程序 可以对图书和供应商两个类进行管理和统计 大学作业,可供学生参考 -
C语言数组形链表实现
2019-01-27 21:28:21原创C语言数组形链表操作的具体接口,定义简单,逻辑清晰 -
链表实现学生信息管理系统
2019-04-21 16:52:34改源代码用链表实现了学生信息的增删改查,读写入(出)文件,同时实现了学生信息的排序,链表的清空,插入。双向链表的插入排序,能够帮助学习链表。 -
C语言链表实现字符串输入、查找、删除等
2019-02-28 09:00:10C语言链表实现字符串输入、查找、删除等 C语言实验内容 -
栈的实现(C语言)数组实现以及链表实现
2016-05-25 11:43:33栈的实现(C语言)数组实现以及链表实现源码,以及各个功能测试代码函数等 和后缀式转前缀式的用例 -
约瑟夫环问题通过循环链表实现(c语言版)
2018-11-24 14:37:14通过循环链表实现约瑟夫环问题,用c语言实现。属于数据结构部分内容 -
使用C++链表实现二叉树的存储及基本操作
2016-10-06 22:50:28使用C++语言,结合单链表的基本操作,实现二叉树的存储,前序、种序、后序遍历及其他基本操作 -
双向链表实现
2018-06-14 22:45:11数据结构小代码,改自 《数据结构与算法分析C++版》 源代码 ...2. 利用双向链表实现2个一元稀疏多项式的加法运算,运算结果得到的链表要求按照指数升序有序,并遍历输出指数升序、指数降序的多项式。 -
用链表实现多项式加减法运算
2014-10-18 10:48:48用链表实现两个多项式相加的C语言源代码,两个多项式相加时,同类项的系数相加,无同类项的系数保持不变,想家完后再按升幂排序,结果放回链表中。是数据结构的作业,改编了网上的代码,运行结果正确。 -
Java实现双向链表
2020-03-22 23:22:42用Java定义一个双向链表,实现链表的基本操作: 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表。 -
链表实现多级菜单
2012-05-04 13:09:52本例实现单片机的多级菜单,过程是用链表实现的。 -
逆置数组实现和链表实现(C语言实现) 数组和链表.pdf
2022-04-18 09:53:22逆置数组实现和链表实现(C语言实现) 数组和链表.pdf -
JS基于对象的链表实现与使用方法示例
2020-10-17 11:01:51主要介绍了JS基于对象的链表实现与使用方法,结合实例形式分析了链表的原理及javascript定义与使用链表的相关操作技巧,需要的朋友可以参考下 -
学生成绩管理系统C语言实现报告链表实现,内含流程图,代码
2017-05-18 13:51:45学生成绩管理系统C语言实现报告,链表实现,内含流程图,代码,一切以报告形式完成。 -
用循环链表实现队列操作
2013-10-29 09:57:25用循环链表实现队列操作 讲解详细 通过多次编译 可以运行的 -
使用链表实现栈
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++ 双向链表实现学生管理系统
2013-06-09 14:53:28C++ 双向链表实现学生管理系统 -
链表实现集合运算 链表实现集合交并差运算
2019-12-27 17:46:05链表实现集合运算 链表实现集合交并差运算 -
java链表应用--基于链表实现队列详解(尾指针操作)
2020-08-19 12:23:37主要介绍了java链表应用--基于链表实现队列,结合实例形式分析了java基于链表实现队列尾指针相关操作使用技巧,需要的朋友可以参考下 -
C语言数据结构之栈(链表实现)
2020-08-11 22:24:24C语言数据结构之栈(链表实现) 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:瞄准天上的星星,或许你永远也射不到,但却比你瞄准树梢射得高远。
-
链表实现集合的并交差运算
2013-04-28 15:44:31数据结构的实验,用链表实现对集合的相关运算。 -
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++)
2013-03-11 12:43:33约瑟夫环的链表实现(C++) 采用链表方式解决问题,代码简单,书写格式规范,有相应注释以及测试小模块。 -
STM32用链表实现多级菜单
2012-10-02 11:23:15用链表实现多级菜单,STM32彩屏显示多级菜单 -
使用双向链表实现快速排序,C语言
2014-03-31 21:05:38使用双向链表实现快速排序,C语言,有详细注释 -
多项式加法运算(链表实现)
2021-04-24 13:09:04我们用链表存储一个多项式,那么该链表的每一个结点就代表多项式的某一项。所以我们的每一个结点必须包含三个信息:多项式的系数、多项式的指数以及指向下一个结点的指针。 typedef int SLTDataType;//指数、系数...