C语言 浅谈栈与队列的定义与操作

目录
  • 栈的定义
  • 栈的实现
    • 前置
    • 初始化栈
    • 栈的销毁
    • 栈的插入
    • 出栈的操作
    • 取栈顶元素
    • 栈的大小
  • 队列的定义
  • 队列的基本操作
    • 队列的初始化
    • 队列的销毁
    • 队列的插入
    • 队列的删除
    • 队列的判空
    • 取出队头元素
    • 取出队尾元素
    • 队列的大小

栈的定义

栈同样是一种线性表，它的特性是插入元素必须从后面插入，删除元素也是从后面删除，进行数据删除和插入的一端称为栈顶，另一端是栈底。
压栈—就是插入元素
出栈—就是删除元素
它可以用数组实现也可以用链表实现

但是用数组实现更好，因为链表的插入和删除要进行遍历，而数组可以进行随机访问，从而时间复杂度更低。

栈的实现

前置

栈的元素需要表明容量，还有栈顶

typedef int SDType;
typedef struct Srack
{
	SDType* a;
	int top;
	int capacity;

}ST;

初始化栈

把元素置为空，栈顶在下标为0的位置

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

栈的销毁

不再赘述

void StackDestrory(ST* ps)
{
	assert(ps);
	free(ps);
	ps=NULL;
	ps->capacity = ps->top = 0;
}

栈的插入

先判空，如果容量满了，进行增容，把栈顶元素进行赋值，再把栈顶指针加一

void StackPush(ST* ps, SDType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SDType* tmp = (SDType)realloc(ps->capacity, sizeof(SDType) * newCapacity);
		if (tmp == NULL)
		{
			printf("Realloc fail!\n");
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newCapacity;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

出栈的操作

栈顶指针减一即可

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;

}

取栈顶元素

先进行判空，不空的话直接取出栈顶指针指向的元素

SDType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps -> a[ps->top - 1];
}

栈的大小

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

判断栈是否为空

bool StackEmpty(ST* ps)
{
	return ps->top == 0;
}

队列的定义

队列只允许在一段进行插入操作，一段进行删除操作，在队尾进行插入，在队头进行删除

队列的基本操作

队列的初始化

我们在进行基本操作的时候要用到头指针和尾指针

void QueueInit(Queue* pq)
{
	assert(pq != NULL);
	pq->head = NULL;
	pq->tail = NULL;

}

队列的销毁

将临时指针cur被赋值为head，保存下一个，遍历进行删除，最后把头指针和尾指针进行free

void QueueDestroy(Queue* pq)
{
	assert(pq != NULL);
	QueueNode* cur = pq->head;
	QueueNode* next = cur->next;
	while (cur)
	{
		free(cur);
		cur = next;
		next = next->next;
	}
	pq->head = pq->tail = NULL;
}

队列的插入

队列只能从队尾查，如果开始的时候队头和队尾重合，那就直接进行插入，
如果不，那就找到尾，在尾后边进行插入

void QueuePush(Queue* pq,QDataType x)
{
	assert(pq);
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	newNode->data = x;
	newNode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}

队列的删除

很简单，删除队尾头元素，先保存下一个，再把队头复制给新的

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* NewHead = pq->head->next;
	free(pq->head);
	pq->head = NewHead;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

队列的判空

是否队头指向空

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

取出队头元素

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

取出队尾元素

先判空

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;

}

队列的大小

直接遍历就行

int QueueSize(Queue* pq)
{
	assert(pq);
	int n = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		cur = cur->next;
		n++;
	}
	return n;
}

点个赞把

到此这篇关于C语言 浅谈栈与队列的定义与操作的文章就介绍到这了,更多相关C语言 栈与队列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言中栈和队列实现表达式求值的实例

    C语言中栈和队列实现表达式求值的实例 实现代码: #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define STACK_SIZE 20 #define STACK_INCREMENT 10 #define QUEUE_SIZE 20 typedef int Status; typedef char StackElemtype; typedef struct Stack{ StackElemty

  • C语言 表、栈和队列详解及实例代码

    C语言 表.栈和队列详解 表ADT 形如A1,A2,A3-An的表,这个表的大小为n,而大小为0的表称为空表,非空表中,Ai+1后继Ai,Ai-1前驱Ai,表ADT的相关操有PrintList打印表中的元素:CreateEmpty创建一个空表:Find返回关键字首次出现的位置:Insert和Delete从表的某个位置插入和删除某个关键字. 对表的所有操作都可以通过使用数组来实现,但在这里使用链表的方式来实现.链表(linked list)由一系列不必在内存中相连的结构组成,每个结构均含有元素和指

  • C语言编程数据结构的栈和队列

    C语言编程数据结构的栈和队列

    目录 栈 数组实现 标题全部代码 Stack_array.c Stack_array.h 初始化数组栈 满栈后扩容 是否为空栈 压栈和退栈 链表实现 stack_chain.h stack_chain.c 整个压栈流程 整个弹栈流程 出栈情况 队列 队列的实现 queue_chain.h queue_chain.c 一个结构体类型用于维护这个队列 概念流程图 入队列的实现 出队列的实现 是否空队 栈 栈是一种以后进先出为顺序对对象进行添加或删除的数据结构 对栈进行形象记忆就像是桌子上的一堆书或一

  • C语言编程数据结构栈与队列的全面讲解示例教程

    C语言编程数据结构栈与队列的全面讲解示例教程

    目录 一.栈的表示和实现 1栈的概念和结构 2栈的初始化 3压栈(栈顶插入一个数据) 4出栈(栈顶删除一个数据) 5取栈顶元素 6取栈顶元素 7判断栈是否为空 二.队列的表示和实现 1队列的概念及结构 2队列的实现 3队列初始化 4入队(队尾插入一个数据) 5出队(队头删除一个数据) 6取队头数据 7取队尾数据 8计算队列中数据个数 9判断队列是否为空 10销毁队列 总结 一.栈的表示和实现 1栈的概念和结构 栈:一种特殊的线性表(逻辑上数据是连着放的),其只允许在固定的一端进行插入和删除操作.

  • C语言数据结构进阶之栈和队列的实现

    C语言数据结构进阶之栈和队列的实现

    目录 栈的实现: 一.栈的概念和性质 二.栈的实现思路 三.栈的相关变量内存布局图 四.栈的初始化和销毁 五.栈的接口实现: 1.入栈 2.出栈 3.获取栈顶的数据 4.获取栈的元素个数 5.判断栈是否为空 队列的实现: 一.队列的概念和性质 二.队列的实现思路 三.队列相关变量的内存布局图 四.队列的初始化和销毁 五.队列的接口实现: 1. 入数据 2.出数据 3.取队头数据 4.取队尾数据 5.获取队列元素个数 6.判断队列是否为空 总结 栈的实现: 一.栈的概念和性质 栈(stack)又名

  • C语言基于考研的栈和队列

    C语言基于考研的栈和队列

    目录 栈 栈的基本操作 三角矩阵 总结 栈 栈的基本操作 InitStack(&S):初始化 StackEmpty(S):判空,空则true,非空则false Push(&S,x):入栈 Pop(&S,&x):出栈,并用x返回元素内容 GetTop(S,&x):读栈顶元素 DestroyStack(&S):销毁并释放空间 栈是一种受限的线性表,只允许在一端操作 栈若只能在栈顶操作,则只可能上溢 采用非递归方式重写递归时,不一定要用栈,比如菲波那切数列只要用循

  • 深入浅析C语言中堆栈和队列

    深入浅析C语言中堆栈和队列

    1.堆和栈 (1)数据结构的堆和栈 堆栈是两种数据结构. 栈(栈像装数据的桶或箱子):是一种具有后进先出性质的数据结构,也就是说后存放的先取,先存放的后取.这就如同要取出放在箱子里面底下的东西(放入的比较早的物体),首先要移开压在它上面的物体(放入的比较晚的物体). 堆(堆像一棵倒过来的树):是一种经过排序的树形数据结构,每个结点都有一个值.通常所说的堆的数据结构,是指二叉堆.堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆.由于堆的这个特性,常用来实现优先队列,堆的存取是随意,

  • C语言 浅谈栈与队列的定义与操作

    C语言 浅谈栈与队列的定义与操作

    目录 栈的定义 栈的实现 前置 初始化栈 栈的销毁 栈的插入 出栈的操作 取栈顶元素 栈的大小 队列的定义 队列的基本操作 队列的初始化 队列的销毁 队列的插入 队列的删除 队列的判空 取出队头元素 取出队尾元素 队列的大小 栈的定义 栈同样是一种线性表,它的特性是插入元素必须从后面插入,删除元素也是从后面删除,进行数据删除和插入的一端称为栈顶,另一端是栈底. 压栈-就是插入元素 出栈-就是删除元素 它可以用数组实现也可以用链表实现 但是用数组实现更好,因为链表的插入和删除要进行遍历,而数组可以

  • C语言分别实现栈和队列详解流程

    C语言分别实现栈和队列详解流程

    目录 什么是栈 栈的结构图示 栈的实现 创建栈的结构体 初始化栈 入栈 出栈 获取栈顶元素 获取栈中有效元素个数 检测栈是否为空 栈的销毁 什么是队列? 队列的实现 创建队列结构体 初始化队列 队尾入队列 队头出队列 获取队列头部元素 获取队列尾部元素 获取队列中元素个数 检测队列是否为空 销毁队列 什么是栈 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素的操作.进行数据插入和删除的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守先进后出LIFO(Last In First Out

  • C语言数据结构之栈与队列的相互实现

    C语言数据结构之栈与队列的相互实现

    目录 一.用对列实现栈 代码实现 二.用栈实现队列 代码实现 一.用对列实现栈 题干要求: 细节分析:队列是先进先出: 要实现的栈是先进后出. 解题思路:假设:先用一个队列储存数据 N 个,然后将前 N-1 个数据导入到另一个队列, 此时,原始队列中仅剩一个,是最后剩的数据,便可将其导出,这便是一次后进先出. 细节点:每次导出数据时,都需要一个队列向另一个队列传入数据,因此输入队列和输出队列                    需要轮换,要对其进行判定. 具体过程gif动态图如下: 代码实现

  • C语言数据结构之栈和队列的实现及应用

    C语言数据结构之栈和队列的实现及应用

    目录 一.栈的概念 二.Stack.h 三.Stack.c 1.栈的初始化和销毁 2.栈的进栈.出栈 3.栈的判空.访问栈顶元素.栈内元素个数 四.队列的概念 五.Queue.h 六.Queue.c 1.队列的初始化和销毁 2.队列的入队.出队 3.队列的判空 4.访问队头.队尾数据.统计队列长度 七.力扣中栈和队列OJ题 1.有效的括号 2.用队列实现栈 3.用栈实现队列 4.设计循环队列 栈和队列是一种数据结构,只规定了性质,并没有规定实现方式. 本文以顺序结构实现栈,链表方式实现队列. 一

  • c语言数据结构之栈和队列详解(Stack&Queue)

    c语言数据结构之栈和队列详解(Stack&Queue)

    目录 简介 栈 一.栈的基本概念 1.栈的定义 2.栈的常见基本操作 二.栈的顺序存储结构 1.栈的顺序存储 2.顺序栈的基本算法 3.共享栈(两栈共享空间) 三.栈的链式存储结构 1.链栈 2.链栈的基本算法 3.性能分析 四.栈的应用——递归 1.递归的定义 2.斐波那契数列 五.栈的应用——四则运算表达式求值 1.后缀表达式计算结果 2.中缀表达式转后缀表达式 队列 一.队列的基本概念 1.队列的定义 2.队列的常见基本操作 二.队列的顺序存储结构 1.顺序队列 2.循环队列 3.循环队列

  • 浅谈js函数的多种定义方法与区别

    定义一个函数一般有如下三种方式: 1.函数关键字(function)语句: function fnMethodName(x){ alert(x); } 2.函数字面量(Function Literals): var fnMethodName = function(x){alert(x);} 3.Function()构造函数: var fnMethodName = new Function('x', 'alert(x);') 上面三种方法定义了同一个方法函数fnMethodName,第1种就是最常

  • JavaScript数据操作_浅谈原始值和引用值的操作本质

    JavaScript数据操作_浅谈原始值和引用值的操作本质

    我的一句话总结:原始值不管是变量赋值还是函数传递都不会改变原值,引用值不管是变量赋值还是函数传递,如果新变量重新赋值,则不会影响原引用值,如新变量是直接操作,就会影响原引用值. 首先明确,值和类型是两个不同的概念.例如,null是null类型的唯一值.undefined是undefined类型的唯一值.而true和false是boolean类型仅有的两个值等.在任何语言中,值的操作都可以归纳为以下3个方面. 复制值:即把值赋值给新变量,或者通过变量把值赋值给另一个变量.属性或数组元素. 传递值:

  • 浅谈Python数据类型判断及列表脚本操作

    浅谈Python数据类型判断及列表脚本操作

    数据类型判断 在python(版本3.0以上)使用变量,并进行值比较时.有时候会出现以下错误: TypeError: unorderable types: NoneType() < int() 或者类似的类型错误. 这是因为一方变量的数据类型不明(python无法判断),所以出错. 在一般情况下,可以提前对要使用的变量进行定义并赋值,例如: var=' ' 或者 var=0 等等. 但是,若变量在比较前,是通过调用函数或者其他表达式赋值的,以上方法可能行不通,因为如果调用的函数如果存在错误或者没

  • 浅谈js函数三种定义方式 & 四种调用方式 & 调用顺序

    在Javascript定义一个函数一般有如下三种方式: 函数关键字(function)语句: function fnMethodName(x){alert(x);} 函数字面量(Function Literals): var fnMethodName = function(x){alert(x);} Function()构造函数: var fnMethodName = new Function('x','alert(x);') // 由Function构造函数的参数个数可变.最后一个参数写函数体

随机推荐