首页 > 其他分享 >【数据结构】栈和队列

【数据结构】栈和队列

时间：2024-05-25 23:05:25浏览次数：27  
标签：ps obj 队列 Queue int return 数据结构

在这里插入图片描述
个人主页~

栈和队列

一、栈

1、概念

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作，进行数据插入与删除的一端叫做栈顶，另一端叫做栈底，栈中的元素遵循后进先出的原则
这里给的是一个抽象的概念，我们可以把栈看做一个装满大米的米缸，我们想要吃米的时候，后放入米缸的米肯定要先吃，此时缸底就是栈底，缸顶就是栈顶，我们在不破坏缸的情况下只能从缸顶来取用大米
压栈/进栈/入栈：栈在栈顶的插入操作
出栈：栈在栈顶的删除操作
在这里插入图片描述

2、栈的实现

栈一般可以由数组和链表实现，相对来说数组来实现更好一些，因为在尾插数据的时候，单链表每次插入都需要malloc一块新的空间，如果插入的数据比较多，那么效率就会大大降低，但数组来实现的话，数据越多，数组的效率相较于链表就会越高，因为数组每一次扩容都是两倍两倍的扩，越到后边需要扩容的次数就越少
栈分为静态栈与动态栈两种，顾名思义，静态就是固定的，没法改变的，动态就可以自己调节增长与减小，在实际使用中，我们肯定都是选择动态栈

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

#define _CRT_SECURE_NO_WARNINGS

#include "Stack.h"

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_top = 0;
	ps->_capacity = 0;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_capacity == ps->_top)
	{
		int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		//新的容量：如果原容量为0，那么给它赋值为4字节，如果不为0，则赋值为原来的两倍
		STDataType* tmp = (STDataType*)realloc(ps->_a,sizeof(STDataType)*newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->_a = tmp;
		ps->_capacity = newcapacity;
	}
	ps->_a[ps->_top] = data;//将栈顶的数据赋值为为data
	ps->_top++;//将栈顶下标+1
}

void StackPop(Stack* ps)
{
	assert(ps);
	ps->_top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_a);
	return ps->_a[ps->_top - 1];//assert防为空后直接返回栈顶数据
}

int StackSize(Stack* ps)
{
	assert(ps);
	assert(ps->_a);
	return ps->_top - 1;//防为空后直接返回top-1
}

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0;//判断句，真则返回非零数，假则返回0
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS

#include "Stack.h"

int main()
{
	Stack s1;
	StackInit(&s1);//初始化
	printf("%d\n", StackEmpty(&s1));//判空
	
	StackPush(&s1, 1);
	StackPush(&s1, 2);
	StackPush(&s1, 3);
	StackPush(&s1, 4);
	//插入
	printf("%d\n", StackSize(&s1));//大小
	printf("%d\n", StackTop(&s1));//栈顶数据
	
	StackPop(&s1);//删除
	
	printf("%d\n", StackTop(&s1));
	printf("%d\n", StackSize(&s1));
	
	StackDestroy(&s1);//销毁
	return 0;
}

在这里插入图片描述

二、队列

1、概念

队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，特性是先进先出，先进入的先出来
入队列：从插入的一端进入，这一端叫做队尾
出队列：从删除的一端删除，这一端叫做队头
当我们排队打饭的时候，这就是一个队列，在窗口前有一条长队，这就是一个队列，我们要排队，只能排到最后面，我们就插入到了队列中，当最前面的人打完饭时，他就从队列中删除了，在这个队伍中，先来的总是先打完饭，然后离开队伍，后来的总是后打完饭，然后离开队伍，就是先进先出的原则
在这里插入图片描述

2、队列的实现

因为涉及到两边同时工作，一边出数据一边入数据，这里更加推荐使用链表，因为数组在进行出数据的时候，需要进行覆盖操作，所以效率在数据比较多的时候会非常低，而链表的删除插入很方便，所以实现队列我们用链表

Queue.h

#pragma once

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

#define QDataType int

// 链式结构：表示队列
typedef struct QListNode
{
	struct QListNode* _pNext;
	QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}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

#include "Queue.h"

void QueueInit(Queue* q)
{
	assert(q);
	q->_front = q->_rear = (Queue*)malloc(sizeof(Queue));
	//为队列在堆上开辟一块空间，队头队尾都指向这块空间
	if (q->_front == NULL)
	{
		perror("malloc fail");
		return;
	}
	q->_front->_pNext = q->_rear->_pNext = NULL;//置空队头队尾指针

}

void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->_data = data;
	newnode->_pNext = NULL;
	q->_rear->_pNext = newnode;
	q->_rear = newnode;
	//在队尾插入新节点，让新节点成为队尾
}

void QueuePop(Queue* q)
{
	assert(q);

	QNode* del = q->_front;
	q->_front = q->_front->_pNext;
	free(del);
	del = NULL;
}

QDataType QueueFront(Queue* q)
{
	assert(q);
	return q->_front->_pNext->_data;
}

QDataType QueueBack(Queue* q)
{
	assert(q);
	return q->_rear->_data;
}

int QueueSize(Queue* q)
{
	assert(q);
	int count = 0;
	QNode* pur = q->_front->_pNext;
	while (pur)
	{
		pur = pur->_pNext;
		count++;
	}
	return count;
	//遍历一遍，count记录
}

int QueueEmpty(Queue* q)
{
	assert(q);
	return q->_front == q->_rear;
	//判断，当队头队尾位置相同时返回非零，不同返回0
}

void QueueDestroy(Queue* q)
{
	assert(q);
	while (q->_front != q->_rear)
	{
		QNode* del = q->_front;
		q->_front = q->_front->_pNext;
		free(del);
		del = NULL;
	}
}

test.c

#include "Queue.h"

void test()
{
	Queue q;
	QueueInit(&q);//初始化
	printf("%d\n", QueueEmpty(&q));//判空

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
//测试插入
	printf("%d\n", QueueEmpty(&q));//判空

	printf("%d\n", QueueFront(&q));//队头数据

	printf("%d\n", QueueBack(&q));//队尾数据

	printf("%d\n", QueueSize(&q));//队伍大小
	QueuePop(&q);//删除
	printf("%d\n", QueueFront(&q));

	printf("%d\n", QueueSize(&q));
	QueueDestroy(&q);//销毁
}
int main()
{
	test();
	return 0;
}

在这里插入图片描述

三、深入了解栈和队列的特性

当我们了解了队列和栈的基本概念之后，我们可以通过它们的互相实现来进一步加深理解，这种问题在实际生产生活中上没有什么意义，但可以帮助我们更好地掌握栈和队列

1、用队列实现栈

leetcode-用队列实现栈


//这里插入队列的定义，在上方有，这里需要定义了才能使用，因为已经写过了我就不再复制上增加篇幅了

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
//两个栈实现队列
MyStack* myStackCreate() {
    MyStack* new = (MyStack*)malloc(sizeof(MyStack));
    if(new == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    QueueInit(&new->q1);
    QueueInit(&new->q2);
    return new;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
    //两个队列，当两者都为空时，1 2 3 4存入，q1没有数据，q2为1 2 3 4，当出数据时，
    //q2将除了尾节点以外的节点放到q1里边，q2剩下4，把4出掉，再出数据时，
    //q1把除了尾节点以外的节点放到q2里边，出掉3
}

int myStackPop(MyStack* obj) {
    Queue* pEmptyQ = &obj->q1;
    Queue* pNonEmptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        pEmptyQ = &obj->q2;
        pNonEmptyQ = &obj->q1;
    }
//这里可以灵活地将在出数据时的由谁存数据和由谁出数据整理清楚，
//当q1不为空时， pEmptyQ = &obj->q2，pNonEmptyQ = &obj->q1;
//当q1为空时，pEmptyQ = &obj->q1，pNonEmptyQ = &obj->q2;
//pEmptyQ用来存数据，pNonEmptyQ用来出数据
    while(QueueSize(pNonEmptyQ)>1)
    {
        QueuePush(pEmptyQ,QueueFront(pNonEmptyQ));
        QueuePop(pNonEmptyQ);
    }
    int top = QueueFront(pNonEmptyQ);
    QueuePop(pNonEmptyQ);
    return top;
    //访问到出数据队列的数据，将其保存然后pop掉，然后返回值
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
    //看哪个队列不为空，不为空的那个队列的尾节点数据就是栈顶数据
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}//两个都成立则为真，一方不成立则为假，当两个都为空时才为空

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);

    free(obj);
}

2、用栈实现队列

leetcode-用栈实现队列


//这里插入栈的定义，在上方有，这里需要定义了才能使用，因为已经写过了我就不再复制上增加篇幅了

typedef struct {
    Stack s1;
    Stack s2;
} MyQueue;
//用两个栈来实现队列
//一个栈用来存数据，另一个用来出数据，将数据在两个栈中来回倒一下，再出的数据就会是先进先出的队列型
//1 2 3 4存入栈当中，再从这个栈存到另一个栈中，那么另一个栈就是 4 3 2 1，再出数据就是1 2 3 4
//这里s1负责出，s2负责入
MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    if(obj == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    StackInit(&obj->s1);
    StackInit(&obj->s2);

    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->s1,x);
    //因为我们的出数据和入数据的栈在之前就明确好了，那么直接找到一个栈出数据就可以了
}

int myQueuePop(MyQueue* obj) {
    int front = myQueuePeek(obj);//嵌套使用
    StackPop(&obj->s2);
    return front;
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->s2))
    {
        while(!StackEmpty(&obj->s1))
        {
            StackPush(&obj->s2,StackTop(&obj->s1));
            StackPop(&obj->s1);
        }
    }//当s1不为空时，将s1的数据全部放到s2中
    return StackTop(&obj->s2);//返回s2的栈顶数据
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}//两者都为空则为空，否则则不是空

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s2);
    free(obj);
}

3、循环队列

leetcode-循环队列

typedef struct {
    int front;//队头
    int rear;//队尾
    int k;//数据个数，实际开的空间个数是k+1
    int* a;//节点指针
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}//当队头队尾相同时，为空

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->k+1) == obj->front;
}//就是当队尾为队头的前一个节点的前一个节点时，就是满的

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear] = value;
    obj->rear++;
    obj->rear %= (obj->k+1);
    //这里是怕到最后的节点会出现队尾的排号大于存储最大数据个数的情况
    return true; 
}//判断是否还有位置

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front %= (obj->k+1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->front];
}//队头数据

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[(obj->rear+obj->k)%(obj->k+1)];
    //这里同上同下，都是怕队头\尾的排号大于存储最大数据个数的情况
}//队尾数据

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

今日分享就到这里了~

在这里插入图片描述

标签：ps,obj,队列,Queue,int,return,数据结构
From： https://blog.csdn.net/s_little_monster/article/details/138972111

相关文章

  • 【数据结构与算法 | 基础篇】单向链表模拟栈
    1.前言前文我们先后用单向循环链表，环形数组来模拟了队列.队列的特点是先进先出.队头移除元素，队尾添加元素.所以需要两个指针控制.本文我们接下来提及如果和单向链表来模拟栈.栈的特点是后进先出.在栈顶压栈或弹栈.另一侧不动的是栈底.我们可以初始化哨兵节点，自哨兵节......
  • 【数据结构与算法 | 基础篇】数组模拟栈
    1.前言前文我们刚提及了如何用单向链表来模拟栈.我们还可以用数组来模拟栈.使用栈顶指针top来进行栈顶的操作.2.数组模拟栈(1).栈接口publicinterfacestack<E>{//压栈booleanpush(Evalue);//弹栈,栈非空返回栈顶元素Epop();//返回栈......
  • 复习数据结构的第五天（栈）
    上次我们复习了静态链表，它需要系统提前分配一定大小的内存空间，同时它和单链表一样有一个指针（游标）指向下一个节点的数组下标索引。它不具有顺序表随机访问的功能，但它可以像单链表一样插入删除时不需要移动其他元素，只需要改变游标就可以实现。栈的概念栈是一种只能在一端进行插......
  • C语言数据结构栈的概念及结构、栈的实现、栈的初始化、销毁栈、入栈、出栈、检查是否
    文章目录前言栈的概念及结构栈的实现一、栈结构创建二、初始化结构三、销毁栈四、入栈五、出栈六、检查是否为空七、获取栈顶元素八、获取有效元素的个数九、测试1十、测试2总结前言C语言数据结构栈的概念及结构、栈的实现、栈的初始化、销毁栈、入栈、出栈、检......
  • Redis基本数据结构
    String数据结构如果存储的是整型，直接把值存储在RedisObject里面，数据类型为int。如果存储的数据量不大（早期版本，32字节），采用动态字符串SDS存储，存储类型是embstr。超过32字节，采用动态字符串SDS进行存储，存储类型是raw。embstr和raw类型的区别在于，RedisObject和embstr是连续存......
  • Java数据结构与算法(平衡二叉树)
    前言平衡二叉树是为了提高二叉树的查询速度，通过满足特定的条件来保持其平衡性。平衡二叉树具有以下特点：左子树和右子树的高度差不会大于1，这是为了确保树的高度不会过大，从而减少查询时的磁盘I/O开销，提高查询速度。平衡二叉树上的所有结点的平衡因子（左子树深度减去右子树深度的......
  • Redis Stream消息队列
    工具类部分内容packagecom.hwd.campus.common.redis.utils;importcom.hwd.campus.common.redis.constant.RedisKeyPrefixConst;importcom.hwd.campus.common.redis.service.RedisListSelect;importcom.hwd.campus.common.redis.service.RedisSelect;importlombok.AllA......
  • 数据结构（栈）
    1.栈的概念和结构概念：栈是一种线性表，它只能从固定的一端进行数据的插入和删除，这一端称为栈顶，另一端称为栈底。栈遵循先入后出的原则。压栈：栈的插入操作可以称为进栈/压栈/入栈，入数据在栈的顶部。出栈：栈的删除操作叫出栈，出的数据也是在栈顶。进栈：出栈：2.栈的实现栈的实......
  • 数据结构（树）
    1.树的概念和结构树，顾名思义，它看起来像一棵树，是由n个结点组成的非线性的数据结构。下面就是一颗树：树的一些基本概念：结点的度：一个结点含有的子树的个数称为该结点的度；如上图：A的为6叶结点或终端结点：度为0的结点称为叶结点；如上图：B、C、H、I...等结点为叶结点非终端结点或......
  • 数组类型的有界阻塞队列-ArrayBlockingQueue
    一：ArrayBlockingQueue简介  一个由循环数组支持的有界阻塞队列。它的本质是一个基于数组的BlockingQueue的实现。它的容纳大小是固定的。此队列按FIFO（先进先出）原则对元素进行排序。队列的头部是在队列中存在时间最长的元素。队列的尾部是在队列中存在时间最短的元素。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99