投稿
  1. 首页
  2. C

【数据结构10】栈和队列的实现

小肥羊火锅店 • 2022-9-27 • C • 阅读 30

【数据结构10】栈和队列的实现,第1张

文章目录
  • 栈
    • 思路
    • 栈的创建
    • 栈的初始化
    • 入栈
    • 出栈
    • 栈顶的数据
    • 栈的数据个数
    • 判空
    • 栈的销毁
  • 队列
    • 思路
    • 队列的创建
    • 队列的初始化
    • 入列
    • 出列
    • 对头数据
    • 对尾数据
    • 队列的数据个数
    • 判空
    • 队列的销毁
  • 完整代码
    • 栈
      • test.c
      • stack.h
      • stack.c
    • 队列
      • test.c
      • Queue.h
      • Queue.c

栈 思路

栈特点：先入后出
想法：
1.用数组实现栈
2.入栈就往数组后面增加数据
3.出栈就把数组最后一个数据删除
细节：
1.当数组空间不够时需要增容
2.所以要创建capacity来记录当前空间大小
3.需要返回栈的数据个数，所以要创建top来记录栈的个数
4.出栈和返回栈顶数据时，栈不为空时才有效

栈的创建 
typedef int STDateType;
typedef struct Stack
{
	STDateType* a;
	int capacity;
	int top;
}ST;
栈的初始化 
void StackInit(ST* ps)
{
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
入栈 
void StackPush(ST* ps, STDateType x)
{
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* pf = realloc(ps->a,sizeof(STDateType) * newcapacity);
		if (pf == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->a = pf;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

每回数据入栈时都需判断栈是否已满

出栈 
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top != 0);
	ps->top--;
}

出栈时需注意栈不能为空

栈顶的数据 
STDateType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top != 0);
	return ps->a[ps->top - 1];
}

返回栈顶数据时需注意栈不能为空

栈的数据个数 
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
判空 
bool StackEmpty(ST* ps)
{
	assert(ps);
	if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
栈的销毁 
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->capacity = 0;
	ps->top = 0;
}
队列 思路

想法：
1.用链表实现栈
2.创建2个指针指向该链表，head和tail，一个指向表头，一个指向表尾
3.每当入列时就将要入列的数据的地址链接在tail后面
4.每当出列时，释放head当前空间，同时将head后一个节点的地址赋给head
细节：
1.入列时，当队列为空需要直接将新节点赋值给head和tail
2.出列时队列一定不能为空
3.返回对头和对尾数据时队列也一定不能为空

队列的创建 
typedef int QDateType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDateType data;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;
队列的初始化 
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
入列 
void QueuePush(Queue* pq, QDateType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	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* cur = pq->head->next;
	free(pq->head);
	pq->head = cur;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

注意出列时队列一定不能为空

对头数据 
QDateType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

注意队列一定不能为空

对尾数据 
QDateType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

注意队列一定不能为空

队列的数据个数 
int QueueSize(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));
	int count = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
判空 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
队列的销毁 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
}
完整代码 栈 test.c 
#include "stack.h"
TestStack()
{
	ST s1;
	StackInit(&s1);
	StackPush(&s1, 1);
	StackPush(&s1, 2);
	StackPush(&s1, 3);
	StackPush(&s1, 4);
	StackPrin(&s1);

	StackPop(&s1);
	StackPop(&s1);
	StackPrin(&s1);

	printf("%d", StackTop(&s1));
	StackDestroy(&s1);
}
int main()
{
	TestStack();
	return 0;
}
stack.h 
#pragma once
#include 
#include 
#include 
#include 

typedef int STDateType;
typedef struct Stack
{
	STDateType* a;
	int capacity;
	int top;
}ST;

void StackInit(ST* ps);
void StackPush(ST* ps,STDateType x);
void StackPop(ST* ps);
void StackDestroy(ST* ps);
STDateType StackTop(ST* ps);
int StackSize(ST* ps);
bool StackEmpty(ST* ps);
void StackPrin(ST* ps);
stack.c 
#include "stack.h"
void StackInit(ST* ps)
{
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
void StackPush(ST* ps, STDateType x)
{
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* pf = realloc(ps->a,sizeof(STDateType) * newcapacity);
		if (pf == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->a = pf;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top != 0);
	ps->top--;
}
void StackPrin(ST* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->top; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->capacity = 0;
	ps->top = 0;
}
STDateType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top != 0);
	return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
队列 test.c 
#include "Queue.h"
TestQueue()
{
	Queue st;
	QueueInit(&st);
	QueuePush(&st, 1);
	QueuePush(&st, 2);
	QueuePush(&st, 3);
	QueuePush(&st, 4);

	QueuePop(&st);
	QueuePop(&st);
	QueuePop(&st);
	//QueuePop(&st);
	//QueuePop(&st);

	int count = QueueSize(&st);
	printf("%d\n", count);

	int ret1 = QueueFront(&st);
	printf("%d\n", ret1);
	int ret2 = QueueBack(&st);
	printf("%d\n", ret2);


	QueueDestroy(&st);
}
int main()
{
	TestQueue();
	return 0;
}
Queue.h 
#pragma once
#include 
#include 
#include 
#include 

typedef int QDateType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDateType data;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq,QDateType x);
void QueuePop(Queue* pq);
QDateType QueueFront(Queue* pq);
QDateType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
Queue.c 
#include  "Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
}
void QueuePush(Queue* pq, QDateType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	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* cur = pq->head->next;
	free(pq->head);
	pq->head = cur;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}
QDateType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
QDateType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));
	int count = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/3002080.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
小肥羊火锅店 小肥羊火锅店 一级用户组
0 0
上一篇 2022-09-27
下一篇 2022-09-27

发表评论

登录后才能评论

评论列表（0条）

保存