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

栈是一种以后进先出为顺序对对象进行添加或删除的数据结构

对栈进行形象记忆就像是桌子上的一堆书或一堆盘。对盘子取或者存盘子,都只能对最上面的书或者盘子进行操作。

648B4318-2B4C-9F23-15C9-913413CAA3B1.png

对于栈而言,只有弹栈才能获取其数据。

当我们用C语言实现栈这个数据结构。

其实有三种方法实现

  • 1,数组
  • 2,单链表
  • 3,双向链表

但是,对于双向链表,实现栈而言过于复杂。

可以选择数组或者单链表。

数组实现
标题全部代码
Stack_array.c
#include "Stack_array.h"
void InitStack(STstack* st)//栈的初始化
{
	st->top = 0;
	st->arr = (STData*)malloc(CAP*sizeof(STData));
	st->capacity = CAP;
}
void StackPush(STstack* st, STData n)//元素入栈
{
	if (st->top == st->capacity)//判断是否需要扩容
	{
		StackExpansion(st);
	}
	st->arr[st->top++] = n;
}
STData StackPop(STstack* st)//元素退栈
{
	assert(st);
	assert(!StackEmpty(st));//判断是否为空栈
	return st->arr[--st->top];
}
int StackEmpty(STstack* st)//判断栈是否为空
{
	if (st->top == 0)
		return 1;
	return 0;
}
void StackDestory(STstack* st)//销毁栈,防止内存泄漏
{
	free(st->arr);
	st->arr = NULL;
}
void StackExpansion(STstack* st)//扩容
{
	STData* tmp = (STData*)realloc((STData*)st->arr, sizeof(STData) * (st->capacity) * 2);
	if (tmp == NULL)
	{
		printf("Exparsion Error\n");
		exit(-1);
	}
	st->arr = tmp;
	st->capacity *= 2;
}
void StackPrint(STstack* st)//打印栈的元素,但前提是要退栈才能得到元素
{
	while(st->top)
	{
		STData ret = StackPop(st);
		printf("%d ", ret);
	}
}
Stack_array.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define CAP 4
typedef int STData;
typedef struct Stack//结构体用于维护栈
{
	int top;//栈顶标记
	STData* arr;//栈的指针
	int capacity;//栈的容量
}STstack;
void InitStack(STstack* st);//栈的初始化
void StackPush(STstack* st, STData n);//元素入栈
STData StackPop(STstack* st);//元素退栈
void StackExpansion(STstack* st);//扩容
int StackEmpty(STstack* st);//判断栈是否为空
void StackDestory(STstack* st);//销毁栈,防止内存泄漏
void StackPrint(STstack* st);//打印栈的元素,但前提是要退栈才能得到元素

对于数组实现而言。创建一个结构体用于维护整个栈。而其中有一个用于链接创建的数组。

typedef int STData;
typedef struct Stack//结构体用于维护栈
{
	int top;//栈顶标记
	STData* arr;//栈的指针
	int capacity;//栈的容量
}STstack;

作为数组栈,需要一个动态的数组。则这就需要一个Capacity作为衡量是否需要扩容的标准。而top需要作为入栈元素的位置。

当top的值等于Capacity时就意味着栈已经满了。因为数组是从0开始的

9D0C053D-79D0-F267-9BB4-2DD0E00576D4.png

初始化数组栈

在初始化时,要先动态开辟一个数组空间,且,未压栈压入数据元素,其top要设为0.要保证当需要压栈时有明确指定的空间。同时,top的位置要为最后压入数据的下一个下标。

void InitStack(STstack* st)//栈的初始化
{
	st->top = 0;
	st->arr = (STData*)malloc(CAP*sizeof(STData));
	st->capacity = CAP;
}
满栈后扩容

其Capacity要作为判断是否满栈的标准。且,满栈后要进行扩容(因为是动态数组)。

void StackExpansion(STstack* st)//扩容
{
	STData* tmp = (STData*)realloc((STData*)st->arr, sizeof(STData) * (st->capacity) * 2);
	if (tmp == NULL)
	{
		printf("Exparsion Error\n");
		exit(-1);
	}
	st->arr = tmp;
	st->capacity *= 2;
}

同时,还要每次更改栈的容量,为下一次是否满栈作为标准。

是否为空栈
int StackEmpty(STstack* st)//判断栈是否为空
{
	if (st->top == 0)
		return 1;
	return 0;
}

其是否为空。也就是top的位置在数组的0下标位。

压栈和退栈
void StackPush(STstack* st, STData n)//元素入栈
{
	if (st->top == st->capacity)//判断是否需要扩容
	{
		StackExpansion(st);
	}
	st->arr[st->top++] = n;
}
STData StackPop(STstack* st)//元素退栈
{
	assert(st);
	assert(!StackEmpty(st));//判断是否为空栈
	return st->arr[--st->top];
}

压栈

每次压栈,都需要判断是否满栈,并决定是否扩容。

同时,当在原先top位置的数位置进行赋值。并之后要将top向后移动一个位置。保证下一次压栈。

退栈

退栈返回top的上一个位置的元素。同时top向前移动一个位置,不需要free,下次压栈会自动覆盖。

链表实现
stack_chain.h
#include <stdio.h>
#include <stdlib.h>
#define N 3
typedef struct stackele
{
	int n;
	int* point;
}sta;
sta* top;
void initstack(sta* a);//初始化栈
void pushstack(sta* a,int num);//入栈
//void printstack(sta* a);//打印栈
//void fullstack(sta* a);//检查是否满栈的情况
void emptystack(sta* a);//检查是否空栈的情况

int popstack(sta*a);//出栈
stack_chain.c
#include "stack_chain.h"
void initstack(sta* a)//初始化栈
{
	top= NULL;
}
void pushstack(sta* a, int num)//入栈
{
	sta* p = (sta*)malloc(sizeof(sta));
	p->n = num;//新节点赋值
	p->point = top;
	top = p;
}
int popstack(sta* a)//出栈
{
	emptystack(a);//检查是否空栈的情况

	int date;
	sta* des = top;
	top = top->point;
	date = des->n;
	free(des);
	des = NULL;
	return date;
}
void emptystack(sta* a)//检查是否空栈的情况
{
	if (top == NULL)
	{
		printf("Stack empty");
		exit(0);
	}
}

对于链表实现栈而言,和数组其实差不多。只不够,每次压栈都需要重新动态开辟一个新节点,并且链入栈中。但是,这并不是普通的直接链入。而是需要头插入栈

4D5C8DC5-42B1-AE2E-0F88-4A81C6C1172E.png

这样头插入栈,可以方便退栈的时候,可以找到上一个元素。而压栈是不需要什么顺序。每一个压栈节点就是top节点。

整个压栈流程

446A65CB-463F-3CF6-27FD-D8D4DE971AEE.png

void pushstack(sta* a, int num)//入栈
{
	sta* p = (sta*)malloc(sizeof(sta));
	p->n = num;//新节点赋值
	p->point = top;
	top = p;
}
整个弹栈流程

949CC9D2-751C-2303-34AA-9442BC8C61DE.png

int popstack(sta* a)//出栈
{
	emptystack(a);//检查是否空栈的情况

	int date;
	sta* des = top;
	top = top->point;
	date = des->n;
	free(des);
	des = NULL;
	return date;
}
出栈情况

尤其要把握一个条件:空栈

由于不是数组,且链式结构的特性,是不需要扩容的。即不需要判断满栈的情况。

只考虑空栈的条件

void emptystack(sta* a)//检查是否空栈的情况
{
	if (top == NULL)
	{
		printf("Stack empty");
		exit(0);
	}
}

这里空栈的条件是top指针指向NULL时也就是

F4451610-8836-DD4B-2361-34498D5EB474.png

为什么呢?

因为每次弹栈的时候,都会free掉top指向的空间然后让top指向下一个节点。就这样不断移动。但是我设计初始化的时候是top= NULL;而且每次压栈都是p->point = top;这就会有一个标准来限定空栈的情况。

对于栈而言,其更像是一个递归的具象化。

队列

97AB5BDC-5636-66F1-53FA-E2D95744F43D.png

这种数据结构就像是银行柜台的取号机,

先取号的先去柜台

始终满足先入先出的概念

队列的实现
queue_chain.h
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int QUData;
typedef struct queue
{
	QUData data;
	struct queue* next;
}queue;
typedef struct Queue//结构体用于维护队列
{
	queue* Dequeue;//队头指针
	queue* Enqueue;//队尾指针
}QUqueue;
void InitQueue(QUqueue* qu);//栈的初始化
void QueuePush(QUqueue* qu, QUData n);//元素入队
QUData QueuePop(QUqueue* qu);//元素出队
int QueueEmpty(QUqueue* qu);//判断队列是否为空
void QueueDestory(QUqueue* qu);//销毁队,防止内存泄漏
void QueuePrint(QUqueue* qu);//打印队列中的元素,但前提是要出队才能得到元素
queue_chain.c
#include "queue_chain.h"
void InitQueue(QUqueue* qu)//队列的初始化
{
	qu->Dequeue = qu->Enqueue = NULL;
}
void QueuePush(QUqueue* qu, QUData n)//元素入队
{
	queue* newcell = (QUData*)malloc(sizeof(QUData));
	newcell->data = n;
	newcell->next = NULL;
	if (qu->Dequeue == NULL)
	{
		qu->Enqueue = qu->Dequeue = newcell;
	}
	else
	{
		qu->Enqueue->next = newcell;
		qu->Enqueue = newcell;
	}
}
QUData QueuePop(QUqueue* qu)//元素出队
{
	if (QueueEmpty(qu))
	{
		printf("Queue Is Empty");
		exit(-1);
	}
	QUData ret = qu->Dequeue->data;
	qu->Dequeue = qu->Dequeue->next;
	return ret;
}
int QueueEmpty(QUqueue* qu)//判断队列是否为空
{
	if (qu->Dequeue == qu->Enqueue)
		return 1;
	return 0;
}
void QueueDestory(QUqueue* qu)//销毁队,防止内存泄漏
{
	queue* cur = qu->Dequeue;
	while (cur)
	{
		queue* pnext = cur->next;
		free(cur);
		cur = pnext;
	}
	qu->Dequeue = qu->Enqueue = NULL;
}
void QueuePrint(QUqueue* qu)//打印队列中的元素,但前提是要出队才能得到元素
{
	queue* cur = qu->Dequeue;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

队 毕竟是先入先出的数据结构。

所以要两个指针,

qu->Dequeue 指向队头,

qu->Enqueue 指向队尾,

不然每次都去找队尾是相当浪费时间的。

一个结构体类型用于维护这个队列
typedef int QUData;
typedef struct queue//描述每个队的元素
{
	QUData data;
	struct queue* next;
}queue;
typedef struct Queue//结构体用于维护队列
{
	queue* Dequeue;//队头指针
	queue* Enqueue;//队尾指针
}QUqueue;

队头指针负责出队,

队尾指针负责入队。

概念流程图

入队

1EE4AF28-8A0F-9FE9-4F9E-94ED0668C729.png

65047784-6DA1-79EA-A925-335D0D169A7F.png

C8B84B83-9C79-9E4E-912E-F72ED3BB79FF.png

6C3F4355-C0E4-FAFB-017F-5AFCBEEFA024.png

入队列的实现
void QueuePush(QUqueue* qu, QUData n)//元素入队
{
	queue* newcell = (QUData*)malloc(sizeof(QUData));
	newcell->data = n;
	newcell->next = NULL;
	if (qu->Dequeue == NULL)
	{
		qu->Enqueue = qu->Dequeue = newcell;
	}
	else
	{
		qu->Enqueue->next = newcell;
		qu->Enqueue = newcell;
	}
}

**当然,入队列在刚开始的时候,头尾指针还是一起指向NULL。

当入第一个元素时,那个元素即是第一个元素也是最后一个元素。要独立判断。**这是一个特殊情况。

出队

1EE4AF28-8A0F-9FE9-4F9E-94ED0668C729.png

6C41119F-0240-C43B-EAB5-294F1CA593D2.png

1254E3A7-1F7C-82FD-4D6B-2A6FC12DBA68.png

出队列的实现
QUData QueuePop(QUqueue* qu)//元素出队
{
	if (QueueEmpty(qu))
	{
		printf("Queue Is Empty");
		exit(-1);
	}
	QUData ret = qu->Dequeue->data;
	qu->Dequeue = qu->Dequeue->next;
	return ret;
}

但是每次出队列都需要判断是否为空队。如果是空队还继续出队会相当于NULL->next ,这是直接报错的。

所以还要一个函数判断是否空队。

是否空队
int QueueEmpty(QUqueue* qu)//判断队列是否为空
{
	if (qu->Dequeue == qu->Enqueue)
		return 1;
	return 0;
}

空队就是相当于回到了初始化的情形qu->Dequeue = qu->Enqueue = NULL;

也就是两者都指向同一处,也就是NULL。

收藏 (0)
评论列表
正在载入评论列表...
我是有底线的
为您推荐
    暂时没有数据