1. Toy模板网首页
  2. > Toy博客

【数据结构】线性表之栈、队列

7月前 作者：是阿建吖! 分类：Toy博客 阅读(40) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】线性表之栈、队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【数据结构】线性表之栈、队列

前言

前面两篇文章讲述了关于线性表中的顺序表与链表，这篇文章继续讲述线性表中的栈和队列。
这里讲述的两种线性表与前面的线性表不同，只允许在一端入数据，一段出数据，详细内容请看下面的文章。
顺序表与链表两篇文章的链接：
线性表之顺序表
线性表之链表

注意： 本文提到的效率全部为空间复杂度！！！！

一、栈

1. 栈的概念

栈:一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO (Last ln FirstOut)的原则.
入栈:栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。

2. 栈的结构

栈的结构决定了栈只能在栈顶入数据，栈顶出数据，并且遵循着后进先出的原则。

2.1 选择数据结构完成栈（数组 or 链表)

2.1.1 数组

前面学习过顺序表就能知道，数组只有尾插和尾删的效率高为 O(1) , 而靠近头的位置的插入删除的效率比较低为O(N)。
而对于栈这种只能在栈顶插入、删除的数据结构可谓是完美契合数组的优点。
【数据结构】线性表之栈、队列

2.1.2 链表

前面学习过链表就可以知道，对于单链表的头插、头删的效率非常高为 O(1) , 而它的尾插、尾删需要找尾，效率比较低为 O(N)。

若以单链表的头为栈底，尾为栈顶，则入栈、出栈相当于单链表的尾插、尾删效率并不高。
显然这不是我们的最佳选项，但是若用一个变量记录尾的情况下，尾插、尾删的效率也可以达到O(1)。

【数据结构】线性表之栈、队列

若以单链表的头为栈顶，尾为栈底，则入栈、出栈相当于单链表的头插、头删效率非常高为O(1)。
这里与前面的数组差不多，也是栈的操作完全契合单链表的优点。

【数据结构】线性表之栈、队列
栈能够使用单链表实现，当然也可以用带头双向循环链表实现，但是我认为这里使用带头双向循环链表有点大炮打蚊子，大材小用的感觉。

2.1.3 我选择用数组完成栈

为什么这里选择数组完成栈呢？
明明数组容量不足时扩容需要消耗，而链表没有这个消耗，为什么不用链表？
原因有以下几点：

  1. 由于数组物理结构上是连续的，缓存命中率高，访问效率高。
  2. 相比链表，数组只需要存储数据，而链表每一个节点还需要存下一个节点的地址。
  3. 虽然数组扩容有消耗，但是链表每次申请节点的时候也会有消耗。

2.2 栈的操作

【数据结构】线性表之栈、队列

3. 栈的实现

Stack.h头文件的实现

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

Stack.c文件的实现

3.1 初始化栈

栈的初始化将传入函数的结构体进行初始化：
a. 栈顶初始化的时候注意有两种情况:
1. top指向栈顶元素
2. top指向栈顶元素的后面一个位置
当然都可以，我选择 1 仅仅方便我自己理解

b. 是否在初始化的时候给栈申请部分空间
当然都可以，我这里选择不申请空间，在后面用realloc函数申请和扩容空间。

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->capacity = 0;
	//ps->top = -1;    //top指向栈顶
	ps->top = 0;     //top指向栈顶的后面一个元素
	ps->a = NULL;
}

3.2 入栈

当数据入栈时需要判断栈是否为满，若为满则需要扩容，这里的StackFull函数其实并没有必要，由于栈只有尾插这一个插入操作不需要复用扩容操作，所以可以直接写在入栈操作中。
注意：
当realloc()函数的参数为NULL时，其作用与malloc()函数的作用一样。

void StackFull(Stack* ps)
{
	assert(ps);
	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
	STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
	if (tmp == NULL)
	{
		perror("realloc");
		return;
	}
	ps->a = tmp;
	ps->capacity = newcapacity;
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);

	if (ps->capacity == ps->top)
		StackFull(ps);
	ps->a[ps->top] = data;
	ps->top++;
}

3.3 判空

前面假设了top是指向栈顶元素后面一个位置，所以当 top 指向 0 的时候栈是空的。

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
}

3.4 出栈

执行出栈操作时，栈不能为空，且只需要 top-- ， 不需要将其数据抹除。

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//栈为空，则不能继续出栈
	ps->top--;
}

3.5 取栈顶元素

与出栈操作一样，取栈顶元素时，栈不能为空。
且top是指向栈顶元素后面一个位置，所以取栈顶元素时取的是 top - 1 指向的元素。

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//栈为空，则无栈顶元素
	return ps->a[ps->top - 1];
}

3.6 获取栈中有效元素个数

由于top是指向栈顶元素的下一个位置，而元素个数正好是下标 + 1 ，也就是top。

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;   //由于top是指向栈顶元素的下一个位置		
					  //而元素个数正好是下标 + 1 ，也就是top
}

3.7 销毁栈

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;

	ps->capacity = 0;
	ps->top = 0;
}

4. 整体代码的实现

#include "Stack.h"
// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->capacity = 0;
	ps->top = 0;     //top指向栈顶的后面一个元素
	ps->a = NULL;
}

void StackFull(Stack* ps)
{
	assert(ps);
	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
	STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
	if (tmp == NULL)
	{
		perror("realloc");
		return;
	}
	ps->a = tmp;
	ps->capacity = newcapacity;
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);

	if (ps->capacity == ps->top)
		StackFull(ps);
	ps->a[ps->top] = data;
	ps->top++;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
}

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//栈为空，则不能继续出栈
	ps->top--;
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//栈为空，则无栈顶元素
	return ps->a[ps->top - 1];
}

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;   //由于top是指向栈顶元素的下一个位置		
					  //而元素个数正好是下标 + 1 ，也就是top
}

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;

	ps->capacity = 0;
	ps->top = 0;
}

二、队列

1. 队列的概念

队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有 先进先出 FIFO(First In First Out) 的原则。
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头

2. 队列的结构

【数据结构】线性表之栈、队列

2.1 选择数据结构完成队列（数组 or 链表)

2.1.1 数组

前面学习过顺序表就能知道，数组只有尾插和尾删的效率高为 O(1) , 而靠近头的位置的插入删除的效率比较低为O(N)。
而对于队列这种只能在队尾插入、对头删除的数据结构，无论队头和队尾定义在哪，使用数组完成必定会有头删或头插，会使得队列的效率降低，所以不建议使用数组完成。

【数据结构】线性表之栈、队列

2.1.2 链表

前面学习过链表就可以知道，对于单链表的头插、头删的效率非常高为 O(1) , 而它的尾插、尾删需要找尾，效率比较低为 O(N)。

(1)若以单链表的头为队头，尾为队尾，则入队列、出队列相当于单链表的尾插、头删效率并不高。
(2)若以单链表的头为队尾，尾为队头，则入队列、出队列相当于单链表的头插、尾删效率并不高。
虽然两种情况都有一种操作效率为O(N) , 但是这两种情况都是与尾有关的操作，
所以只要在结构体中定一个记录尾的成员，那么尾插、尾删的效率就能达到O(1).

【数据结构】线性表之栈、队列

2.1.3 我选择用链表完成队列

为什么这里选择链表完成队列？
通过上面的讲述原因已经显而易见了。
原因如下：
由于无论怎么改造数组都会有一个操作效率为 O(N),而链表只需要改变结构体，使其多一个指向尾的成员，就能使队列的插入、删除的操作效率为O(1).

3. 队列的实现

Queue.h头文件的实现

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int QDataType;

// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;  //指向队列最后一个元素的后面
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

Queue.c文件的实现
3.1 初始化队列

这里队列的front指向队头，rear指向队尾。
当队列为空的时候，那么front和rear 都是指向 NULL。

// 初始化队列 
void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

【数据结构】线性表之栈、队列

3.2 队尾入队列

由于使用链表实现队列，插入时需要申请一个节点。
入队列分为两种情况：

  1. 队列为空时，需要改变队头、队尾的指针。
  2. 队列不为空时，只需要将新节点接到队尾，并将尾指针向后移动即可。
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->next = NULL;
	newnode->data = data;

	if (q->front == NULL)      //分队列是否有元素两种情况
	{						   //队列为空
		assert(q->rear == NULL);
		q->front = newnode;
		q->rear = newnode;
	}
	else
	{						   //队列不为空
		q->rear->next = newnode;
		q->rear = newnode;
	}

	q->size++;//入队列，队列长度加一
}
3.3 判空

当队列中的头、尾指针都指向NULL的时候为队列为空。

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == NULL && q->rear == NULL;
}

【数据结构】线性表之栈、队列

3.4 队头出队列

出队列分为两种情况：

  1. 队列中只有一个元素时：删除最后一个节点，并将 front 和 rear 指向 NULL。
  2. 队列中有多个元素时：删除 front 指向的节点，并将 front 向后移动。
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	//出队列时，队列不能为空
	assert(!QueueEmpty(q));

	//当队列中只有一个元素的时候，不仅仅头指针需要改变，尾指针也需要改变
	//因为当删除最后一个元素时，首指针释放当前节点，并向后移动，而尾指针并没有移动
	//当释放后若在插入元素时，尾指针会造成野指针的情况
	if (q->front->next == NULL)
	{
		QNode* del = q->front;
		q->front = NULL;
		q->rear = NULL;
		free(del);
	}
	else
	{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
	}
	q->size--;
}
3.5 获取队列头部元素

front 指向的节点存储着头部元素。

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	//获取队列头部元素时，队列不能为空
	assert(!QueueEmpty(q));

	return q->front->data;
}
3.6 获取队列队尾元素

rear 指向的节点存储着尾元素。

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	//获取队列头部元素时，队列不能为空
	assert(!QueueEmpty(q));

	return q->rear->data;
}
3.7 获取队列中有效元素个数

结构体中的 size 存储着队列中的有效元素个数

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	//结构体中定义了一个size
	//而这里遍历链表得到个数，效率低O(N)
	/*int size = 0;  不要用
	QNode* cur = q->front;
	while (cur != q->rear)
	{
		size++;
		q->front = q->front->next;
	}*/
	return q->size;
}
3.8 销毁队列

销毁队列与前面销毁单链表相同，需要将每一个节点都释放。

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

4. 整体代码的实现

// 初始化队列 
void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->next = NULL;
	newnode->data = data;

	if (q->front == NULL)      //分队列是否有元素两种情况
	{
		assert(q->rear == NULL);
		q->front = newnode;
		q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}

	q->size++;//入队列，队列长度加一
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == NULL && q->rear == NULL;
}

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	//出队列时，队列不能为空
	assert(!QueueEmpty(q));

	//当队列中只有一个元素的时候，不仅仅头指针需要改变，尾指针也需要改变
	//因为当删除最后一个元素时，首指针释放当前节点，并向后移动，而尾指针并没有移动
	//当释放后若在插入元素时，尾指针会造成野指针的情况
	if (q->front->next == NULL)
	{
		QNode* del = q->front;
		q->front = NULL;
		q->rear = NULL;
		free(del);
	}
	else
	{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
	}
	q->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	//获取队列头部元素时，队列不能为空
	assert(!QueueEmpty(q));

	return q->front->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	//获取队列头部元素时，队列不能为空
	assert(!QueueEmpty(q));

	return q->rear->data;
}


// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);

	//结构体中定义了一个size
	//而这里遍历链表得到个数，效率低
	/*int size = 0;    不要用
	QNode* cur = q->front;
	while (cur != q->rear)
	{
		size++;
		q->front = q->front->next;
	}*/
	return q->size;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

结尾

注意： 本文提到的效率全部为空间复杂度！！！！
如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连！！🌹🌹

【数据结构】线性表之栈、队列文章来源地址https://www.toymoban.com/news/detail-457761.html

到了这里，关于【数据结构】线性表之栈、队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】线性表之顺序表

    【数据结构】线性表之顺序表

    线性表是 n (n = 0) 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表:顺序表、链表、栈、队列… 线性表在 逻辑上是线性结构 ，也就说是连续的一条直线。但是在 物理结构 上并 不一定 是连续的线性表在物理上存储时，通常以

    2024年02月04日
    浏览(40)
  • 数据结构——线性表之顺序表

    数据结构——线性表之顺序表

    目录 一.线性表 二.顺序表实现  2.1 概念及结构  2.2 动态顺序表 2.2.1 初始化与销毁函数 2.2.2 打印函数 2.2.3 尾插函数 2.2.4 尾删函数 2.2.5 扩容函数 2.2.6 头插函数 2.2.7 头删函数 2.2.8 任意位置插入函数 2.2.9 查找函数 2.2.10 任意位置删除函数  2.2.11 修改函数 三.完整代码 四.力扣

    2024年02月07日
    浏览(29)
  • 数据结构之栈、队列——算法与数据结构入门笔记（四）

    数据结构之栈、队列——算法与数据结构入门笔记（四）

    本文是算法与数据结构的学习笔记第四篇，将持续更新，欢迎小伙伴们阅读学习 。有不懂的或错误的地方，欢迎交流 栈是一种线性数据结构，其 只允许在固定的一端进行插入和删除 元素操作。进行数据插入和删除操作的一端称为栈顶 (Top）, 另一端称为栈底 (Bottom)。栈中的

    2024年02月08日
    浏览(29)
  • 数据结构之栈与队列详解

    数据结构之栈与队列详解

    栈和队列是一种特殊的线性结构，他与之前学的线性结构不同，栈和队列是拥有一种特殊规则的线性结构，虽然它是用数组或者链表实现，但是只有符合这种规则才能被称作栈或者队列 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和

    2024年01月16日
    浏览(34)
  • 数据结构：线性表之-单向链表(无头)

    数据结构：线性表之-单向链表(无头)

    目录 什么是单向链表 顺序表和链表的区别和联系 顺序表： 链表： 链表表示(单项)和实现 1.1 链表的概念及结构 1.2单链表(无头)的实现 所用文件 将有以下功能： 链表定义 创建新链表元素 尾插 头插 尾删 头删 查找-给一个节点的指针 改 pos位置之前插入 删除pos位置的值 成品

    2024年02月09日
    浏览(48)
  • 数据结构奇妙旅程之栈和队列

    数据结构奇妙旅程之栈和队列

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好，我是xiaoxie.希望你看完之后,有不足之处请多多谅解，让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页：xiaoxieʕ̯

    2024年02月04日
    浏览(33)
  • 数据结构之栈和队列---c++

    数据结构之栈和队列---c++

    栈 栈是一个“先进后出”结构 队列 入队演示 队列是一种“先进先出”的结构 出队演示 接下来我们开始本次的内容 分析 1.我们可以 老老实实的写一个栈 然后将所有的接口函数实现出来，最后再进行实现队列，但是显然是 效率低下 的方法 2.我们使用 数组模拟栈 ，然后再进

    2024年02月14日
    浏览(49)
  • C数据结构-线性表之顺序表

    C数据结构-线性表之顺序表

    首先我们创建3个文件，分别如下： liner_data --sqlist.c --sqlist.h --test.c 下面编写sqlist.c文件：函数实现的功能 test.c文件：main函数的执行入口 c语言程序编译的过程如下： 预编译-编译-汇编-连接 汇编：gcc -c sqlist.c -o sqlist.o gcc -c test.c -o test.o 连接：可执行文件：gcc sqlist.o test.o -o

    2024年02月09日
    浏览(28)
  • 数据结构学习分享之栈和队列详解

    数据结构学习分享之栈和队列详解

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:数据结构学习分享⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你了解更多数据结构的知识   🔝🔝 这一节要分享的是一个全新的结构–栈和队列,栈和队列总是会一起出现,因为它们的存储方式刚好相反,一个先进先出一

    2024年02月03日
    浏览(38)
  • Java------数据结构之栈与队列（简单讲解）

    Java------数据结构之栈与队列（简单讲解）

    本篇碎碎念 ：时隔n个月，继续写博客，假期落下的进度，在开学后努力追赶， 假期不努力，开学徒伤悲啊，此时此刻真想对自己说一句，活该啊~~~~ 欠下的链表练习题讲解会在下次更新~~~~ 今日份励志文案:  万物皆有裂痕，那是光照进来的地方 栈:一种特殊的线性表，其只允

    2024年04月14日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包