4.1栈与队列增删查改代码实现

发布时间:2024-10-08 12:01

栈与队列增删查改代码实现

文章目录

  • 栈与队列增删查改代码实现
    • 1.栈的增删查改基本代码
    • 2.队列的增删查改基本代码
    • 注:栈和队列的实现与单链表方法差不多,不过多赘述

1.栈的增删查改基本代码

基本文件:
1.头文件:Stack.h
2.源文件:Stack.c
3.源文件:Test_Stack.c

代码内容

    //Stack.h
    #pragma once
    #include
    #include
    #include
    #include
    
    //静态栈---不实用
    /*struct Stack
    {
    	int a[N];
    	int top;//栈顶的位置
    };*/
    
    typedef int STDataType;
    //动态栈
    typedef struct Stack 
    {
    	STDataType* a;
    	int top;//栈顶的位置
    	int capacity;//容量
    }ST;
    
    void StackInit(ST* ps);//初始化栈
    void StackDestory(ST* ps);//销毁栈
    void StackPush(ST* ps, STDataType x);//插入栈顶元素
    void StackPop(ST* ps);//删除栈顶元素
    bool StackEmpty(ST* ps);//判断空栈
    STDataType StackTop(ST* ps);//查找栈顶元素
    int StackSize(ST* ps);//求栈的元素个数

    //Stack.c
    #include"Stack.h"

    void StackInit(ST* ps)//初始化栈
    {
    	assert(ps);
    	ps->a = NULL;
    	ps->top = ps->capacity = 0;
    	//top初始化为0或-1 那么下面插入和删除方式格式有所不同,但思路一样
    }
    
    void StackDestory(ST* ps)//销毁栈
    {
    	assert(ps);
    	free(ps);
    	ps->top = ps->capacity = 0;
    	ps->a = NULL;
    }
    
    void StackPush(ST* ps, STDataType x)//插入栈顶元素
    {
    	assert(ps);
    	//栈满  要扩容
    	if (ps->top == ps->capacity)
    	{
    		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    		ps->a = realloc(ps->a, newCapacity * sizeof(STDataType));//在原空间后在链接空间
    		if (ps->a == NULL)
    		{
    			printf("realloc fail\n");
    			exit(-1);
    		}
    		ps->capacity = newCapacity;
    	}
    	ps->a[ps->top] = x;
    	ps->top++;
    }
    
    
    void StackPop(ST* ps)//删除栈顶元素
    {
    	assert(ps);
    	assert(ps->top > 0);
    	--ps->top;
    }
    
    bool StackEmpty(ST* ps)//判断空栈
    {
    	assert(ps);
    	return ps->top == 0;//满足top=0返回true,不满足返回false 
    }
    
    STDataType StackTop(ST* ps)//查找栈顶元素
    {
    	assert(ps);
    	return ps->a[ps->top-1];
    }
    
    int StackSize(ST* ps)//求栈的元素个数
    {
    	assert(ps);
    	return ps->top;
    }
    #include"Stack.h"
    int main()
    {
    	ST st;
    	StackInit(&st);
    	StackPush(&st, 1);
    	StackPush(&st, 2);
    	StackPush(&st, 3);
    	StackPush(&st, 4);
    	while (!StackEmpty(&st))
    	{
    		printf("%d ", StackTop(&st));
    		StackPop(&st);
    	}
    	printf("\n");
    	StackDestory(&st);
    	return 0;
    }

2.队列的增删查改基本代码

基本文件:
头文件:.Queue.h
源代码:Queue.c
注:这里就不写Test文件了,没有什么写头

代码内容

    //Queue.h
    #pragma once
    #include
    #include
    #include
    #include
    
    typedef int QDataType;
    
    typedef struct QueueNode//记录结点的结构体
    {
    	QDataType data;
    	struct QueueNode* next;
    }QNode;
    
    
    typedef struct Queue//找头尾的结构体
    {
    	//为了方便队尾的插入 创建两个结点指针
    	QNode* head;
    	QNode* tail; 
    }Qu;
    
    void QueueInit(Qu* pq);//初始化队列
    void QueueDestory(Qu* pq);//销毁队列
    void QueuePush(Qu* pq,QDataType x);//队尾入
    void QueuePop(Qu* pq);//队首出
    bool QueueEmpty(Qu* pq);//判断空队列
    size_t QueueSize(Qu* pq);//求队列长度
    QDataType QueueFront(Qu* pq);//求队首
    QDataType QueueBack(Qu* pq);//求队尾

    //Queue.c
    #include"Queue.h"
    void QueueInit(Qu* pq)//初始化队列
    {
    	assert(pq);
    	pq->head = pq->tail = NULL;
    }
    
    void QueueDestory(Qu* pq)//销毁队列
    {
    	assert(pq);
    	QNode* cur = pq->head;
    	while (cur)
    	{
    		//遍历cur 一个一个的去掉cur的内容
    		QNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	pq->head = pq->tail = NULL;
    }
    
    void QueuePush(Qu* pq, QDataType x)//队尾入
    {
    	assert(pq);
    	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    	assert(newnode);
    	newnode->data = x;
    	newnode->next = NULL;
    	if (pq->tail == NULL)
    	{
    		assert(pq->head == NULL);
    		pq->head = pq->tail = newnode;
    	}
    	else
    	{
    		pq->tail->next = newnode;
    		pq->tail = newnode;
    	}
    }
    
    void QueuePop(Qu* pq)//队首出
    {
    	assert(pq);
    	assert(pq->head && pq->tail);
    	if (pq->head->next == NULL)
    	{
    		free(pq);
    		pq->head = pq->tail = NULL;
    	}
    	else
    	{
    		QNode* next = pq->head->next;
    		free(pq->head);
    		pq->head = next;
    	}
    }
    
    bool QueueEmpty(Qu* pq)//判断空队列
    {
    	assert(pq);
    	return pq->head == NULL;//或者return pq->tail==NULL 判断头、尾都可以
    }
    
    size_t QueueSize(Qu* pq)//求队列长度
    {
    	assert(pq);
    	QNode* cur = pq->head;
    	size_t size = 0;
    	while (cur)
    	{
    		size++;
    		cur = cur->next;
    	}
    	return size;
    }
    
    QDataType QueueFront(Qu* pq)//求队首
    {
    	assert(pq);
    	assert(pq->head);
    	return pq->head->data;
    
    }
    
    QDataType QueueBack(Qu* pq)//求队尾
    {
    	assert(pq);
    	assert(pq->tail);
    	return pq->tail->data;
    }

注:栈和队列的实现与单链表方法差不多,不过多赘述

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号