devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++ 链表、栈、队列_c++ 单链表 双链表 队列

作者：我家小花儿 | 2024-04-18 07:37:08

赞

踩

c++ 单链表 双链表 队列

在这里插入图片描述

一、C++ 链表

链表实际上是线性表的链式存储结构，与数组不同的是，它是用一组任意的存储单元来存储线性表中的数据，存储单元不一定是连续的，

且链表的长度不是固定的，链表数据的这一特点使其可以非常的方便地实现节点的插入和删除操作

1.1 几种链表的介绍

1.1.1 单向链表

在这里插入图片描述
单向链表很容易理解，就说把指针当成一条链一样连接每一个节点，每个节点包含了一个或者多个数据。链表的存储单元不一定是连续的，长度不固定，主要用于方便实现节点的插入和删除操作。官方的话这里就不说了，作为数据结构里最基本的，感兴趣的童鞋自行看书

//单向链表节点结构
typedef struct dlink_node
{
    struct dlink_node *next;
    void *val;  //能存储任意类型数据
}node;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

1.1.2 双向链表

在这里插入图片描述
在单向链表的基础上，增加了一个指向前一个节点的指针

//双向链表节点结构
typedef struct dlink_node
{
    struct dlink_node *prev;
    struct dlink_node *next;
    void *val;  //能存储任意类型数据
}node;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

1.1.3 循环链表

链表的两头连接，形成了一个环状链表，称为循环链表。
在这里插入图片描述
循环链表与单链表的主要差异在于循环的判断上，原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束。

判断循环链表为空： front=rear
队满时： (rear+1)%maxsize=front   （rear的下一个是front）
front指向队首元素，rear指向队尾元素的下一个元素。

  • 1
  • 2
  • 3

循环链表还可以引申出环形链表（常用于判断链表是否有环）
在这里插入图片描述

1. 2链表的C++用法

1. 2.1 链表的C++写法

链表的构造:

struct ListNode
{
    double value;
    ListNode *next;
    // ListNode *pre;  双向链表
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

创建一个新链表节点：

ListNode *head = new ListNode(0);创建一个新节点并赋值为0

  • 1

访问下一个节点和值

head = head->next;
cout<<head->val;

  • 1
  • 2

1. 2.2 常考算法题

  1. 链表的倒数第K个结点（基本法）
  2. 从尾到头打印链表
  3. 如何判断一个链表有环
  4. 链表中环的大小
  5. 链表中环的入口结点
  6. 两个链表的第一个公共结点
  7. 合并两个排序的链表
  8. 反转链表
  9. 单链表在时间复杂度为O(1)删除链表结点
  10. 实现无序链表 时间复杂度为O(1)的排序
  11. 约瑟夫环问题

单独写在另一篇文章：

二、C++ 队列

2.1 队列介绍

先进先出（FIFO)——先进队列的元素先出队列。来源于我们生活中的队列（先排队的先办完事）。
在这里插入图片描述
在这里插入图片描述

typedef struct queue
{
        int queuesize;   //数组的大小
        int head, tail;  //队列的头和尾下标
        int *q;          //数组头指针
}Queue;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

2.2 队列的两种存储方式

线性表有顺序存储和链式存储，队列作为一种特殊的线性表，也同样存在这两种存储方式。

2.2.1 顺序队列

用数组存储队列，即利用一组地址连续的存储单元依次存放队列中的元素。为了避免当只有一个元素时，队头和队尾重合使得处理变得麻烦，所以引入两个指针(头尾指针)：front指针指向队头元素，rear指针指向队尾元素的下一个位置。初始化时的头尾指针，初始值均为0。入队时尾指针rear加1，出队时头指针front加1，头尾指针相等时队列为空。
在这里插入图片描述

初始化为空队列，头尾指针相等

在这里插入图片描述

每一次有元素入队，尾指针加1，头指针不变，尾指针始终指向队尾元素的下一位

在这里插入图片描述
每一次有元素出队，则尾指针不变，头指针加1

在这里插入图片描述

最后所有元素出队，则头指针再次和尾指针相等，说明队列空了

在这里插入图片描述
当尾指针已经指向了队列的最后一个位置的下一位置时，若再有元素入队，就会发生“溢出”。

这里可以看到，队尾一般指向已队列元素的前一个位置

如何解决“溢出”问题呢：循环队列。

循环队列

顺序队列的 “假溢出” 问题：队列的存储空间未满，却发生了溢出。比如尾指针现在虽然已经指向了最后一个位置的下一位置，但是之前队头也删除了一些元素，那么头指针经历若干次的加1之后，留出了很多空位置，但是顺序队列还在傻乎乎的以为再有元素入队就溢出呢！肯定不合理。故循环队列诞生！

所以解决"假溢出"的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。将新元素插入到第一个位置上，入队和出队仍按先进先出的原则进行，操作效率高，空间利用率高。

虽然使用循环队列，解决了假溢出问题，但是又有新问题发生——判空的问题，因为仅凭 front = rear 不能判定循环队列是空还是满。比如如图：
在这里插入图片描述

空循环队列front = rear

在这里插入图片描述

满循环队列front = rear

解决办法：

  1. 设置一个标志变量flag， 当front == rear，且flag = 0时为队列空，当front== rear，且flag= 1 时为队列满。
  2. 办法二是当队列空时，条件就是front = rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。于是front == rear就是队列空

我们重点来讨论第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。 所以若队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1) % QueueSize == front。通用的计算队列长度公式为：(rear - front + QueueSize) % QueueSize。

注意：front指针和rear指针后移不能直接使用++，而要使用%：
Q->front = (Q->front + 1) % MAXSIZE，因为到达数组尾后需要移动到数组开头。

2.2.2 链式队列

队列的链式存储结构，其实就是一个操作受限的单向链表，只不过它只能尾进头出而已，我们把它简称为链队列。链式队列和单向链表比就多了两个指针，头指针和尾指针。

优点：

  • 相比普通的队列，元素出队时无需移动大量元素，只需移动头指针。
  • 可动态分配空间，不需要预先分配大量存储空间。
  • 适合处理用户排队等待的情况。

缺点：

  • 需要为表中的逻辑关系增加额外的存储空间。
    在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
参考：https://zhuanlan.zhihu.com/p/75950769

2.3 C++ stl库queue的使用

C++队列queue模板类的定义在头文件中,queue 模板类需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。C++队列Queue是一种容器适配器，它给予程序员一种先进先出(FIFO)的数据结构。

头文件：#include

那么我们如何判断队列是空队列还是已满呢？

非循环队列：

  1. 栈空： 队首标志=队尾标志时，表示栈空。
  2. 栈满 : 队尾+1 = 队首时，表示栈满。

循环队列：

  1. 求元素的个数：(rear - front + MAXSIZE) % MAXSIZE
  2. front/rear指向逻辑的下一个空间 front =（front+1)%MAXSIZE，rear = (rear+1)%MAXSIZE
  3. 判空：front == rear
  4. 判满：(rear+1) %MAXSZIE== front

创建一个队列

queue< int > q;

  • 1

基本操作：

q.empty()               如果队列为空返回true，否则返回false
q.size()                返回队列中元素的个数
q.pop()                 删除队列首元素但不返回其值
q.front()               返回队首元素的值，但不删除该元素
q.push()                在队尾压入新元素
q.back()                返回队列尾元素的值，但不删除该元素
q.swap(p);              将当前 queue 中的元素和参数 queue 中的元素交换。

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
#include <queue>
#include <iostream>
using namespace std;
 
int main(){
	queue<int> q;
	for (int i = 0; i < 10; i++){
		q.push(i);
	}
	if (!q.empty()){
		cout << "队列q非空！" << endl;
		cout << "q中有" << q.size() << "个元素" << endl;
	}
	cout << "队头元素为：" << q.front() << endl;
	cout << "队尾元素为：" << q.back() << endl;
	for (int j = 0; j < 10; j++){
		int tmp = q.front();
		cout << tmp << " ";
		q.pop();
	}
	cout << endl;
	if (!q.empty()){
		cout << "队列非空！" << endl;
	}
	system("pause");
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

队列q非空！
q中有10个元素
队头元素为：0
队尾元素为：9
0 1 2 3 4 5 6 7 8 9

#include <iostream>
using namespace std;
#define MAX 5
//循环队列
struct Queue{
	int data[MAX];
	int front;//队首指针 
	int rear;//队尾指针 
}; 

//初始化队列
void init(Queue &q){
	q.front = q.rear = 0;
} 
//判断是否空
int isEmpty(Queue q){
	return q.front==q.rear;//0不是空 
}
//判断是否满
int isFull(Queue q){
	return (q.rear+1)%MAX == q.front;//0不是满 
} 
//入队
bool enQueue(Queue &q, int val){
	if(isFull(q)){//牺牲掉一个空间 
		cout<<"队满---\n";
		return false;
	}
	q.data[q.rear] = val;
	q.rear = (q.rear+1)%MAX;
	return true;
} 
//出队
bool deQueue(Queue &q){
	if(isEmpty(q)){//判断是否为空 W
		cout<<"队列为空---";
		return false;
	}
	q.front = (q.front+1)%MAX;
	return true;
}
//队头
int frontQueue(Queue q){
	if(isEmpty(q)){
		cout<<"队列为空"<<endl;
		return -1;
	}
	else
		return q.data[q.front];
} 
//队尾
void backQueue(Queue q){
	if(isEmpty(q)){
		cout<<"队列为空"<<endl;
	}
	else{
		cout<<"队尾一般指向已队列元素的后一个位置，所以一般不会去读取循环队列的队尾元素"<<endl;
	}
} 
//队列长度
int queueSize(Queue q){
	if(q.front==q.rear)
		return 0;
	else
		return (q.rear - q.front + MAX) % MAX;
} 

int main(){
	Queue q;
	init(q);
	/*
		牺牲掉一个空间判断是否队满
		所以元素最多是 MAX-1个 
	*/
	for(int i=0; i<5; i++){
		enQueue(q,i);
	}
	cout<<"队列是否为空: "<<isEmpty(q)<<endl;
	cout<<"队列是否满了: "<<isFull(q)<<endl;
	cout<<"队列的元素长度是："<<queueSize(q)<<endl;
	cout<<"队头的值："<<frontQueue(q)<<endl;
	backQueue(q);
	if(!deQueue(q))
		cout<<"出队失败"<<endl;
	cout<<"出队后队头的值："<<frontQueue(q)<<endl;
	cout<<"入队3元素"<<endl;
	if(!enQueue(q,3))
		cout<<"入队失败"<<endl;
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
队满---
队列是否为空: 0
队列是否满了: 1
队列的元素长度是：4
队头的值：0
队尾一般指向已队列元素的后一个位置，所以一般不会去读取循环队列的队尾元素
出队后队头的值：1
入队3元素

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

2.4 队列常考算法题

leetcode查看
待补充

三、C++ 栈

3.1 栈的介绍

参考：https://www.cnblogs.com/QG-whz/p/5170418.html#_label0

特点：

  • 先进后出
  • 限定只能在栈顶进行插入和删除操作。

压栈：栈的插入操作，叫做进栈，也称压栈、入栈。
弹栈：栈的删除操作，也叫做出栈。

3.2 栈的使用

常用操作：

s.empty();         //如果栈为空则返回true, 否则返回false;
s.size();          //返回栈中元素的个数
s.top();           //返回栈顶元素, 但不删除该元素
s.pop();           //弹出栈顶元素, 但不返回其值
s.push();          //将元素压入栈顶

  • 1
  • 2
  • 3
  • 4
  • 5

基于数组的栈

#include <stack>
#include <iostream>
using namespace std;
 
int main()
{
	stack<int> mystack;
	int sum = 0;
	for (int i = 0; i <= 10; i++){
		mystack.push(i);
	}
	cout << "size is " << mystack.size() << endl;
	while (!mystack.empty()){
		cout << " " << mystack.top();
		mystack.pop();
	}
	cout << endl;
	cout << "size is " << mystack.size() << endl;
	system("pause");
	return 0;
}
//size is 11
// 10 9 8 7 6 5 4 3 2 1 0
//size is 0

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

基于单链表的栈
参考：https://blog.csdn.net/zichen_ziqi/article/details/80807989

3.3 栈常考算法题

leetcode查看

1. 有效的括号（LeetCode 20）2.

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号