C语言实现栈和队列

一、栈（原理：FILO||LIFO）

       实现思想：利用静态顺序表实现栈

                     1.定义结构体，包含值和数组还有栈顶成员变量记录栈内元素个数（栈主要就是对栈顶元素的操作）

                     2.初始化、销毁（比较简单看代码理解）

                     3.增操作：先判断栈是否已满，再在栈顶进行添加；（只能从栈顶添加）

                     4.删操作：先判断栈是否为空，再从栈顶进行删除；（只能从栈顶删除）

                     5.返回栈顶元素：先判断栈内是否有元素，直接返回栈顶元素就可以；

                     6.判断栈是否为空和返回栈内元素个数（比较简单看代码理解）

       具体实现代码：

#pragma once
#include <assert.h>

#define MAX 100

typedef int SDataType;

//利用静态顺序表实现栈
typedef struct Stack
{
	SDataType val;
	SDataType array[MAX];
	int top;
} Stack;

//初始化
void StackInit(Stack* stack)
{
	stack->top = 0;
}

//销毁
void StackDestroy(Stack* stack)
{
	stack->top = 0;
}

//增删改查
//只能从栈顶插入
void StackPush(Stack* stack, SDataType val)
{
	assert(stack);
	assert(stack->top < MAX);
	stack->array[stack->top] = val;
	++stack->top;
}

//只能从栈顶删除
void StackPop(Stack* stack)
{
	assert(stack);
	assert(stack->top > 0);
	--stack->top;
}

//返回栈顶元素
SDataType stackTop(Stack* stack)
{
	assert(stack);
	assert(stack->top > 1);
	return stack->array[stack->top - 1];
}

//判断是否为空
int StackEmpty(Stack* stack)
{
	return stack->top > 0 ? 0 : 1;
}

//返回栈内元素个数
int StackSize(Stack* stack)
{
	return stack->top;
}

二、队列（原理：FIFO）

       实现思想：利用单链表实现队列

                     1.定义两个结构体：一个表示链表元素的信息（值和next），另一个表示整个结构体的信息（队头指针和队尾指针                                                        还有队列中元素个数）；

                     2.初始化（初始化存放结构体信息的结构体）、销毁（删除链表元素，在初始化结构体）；

                     3.增操作：申请新结点，判断是不是一个元素，若是对队头和队尾同时赋值，若不是在队尾添加（只能从队尾插                                              入）；    

                     4.删操作：判断队列是否为空，再进行删除，删除完后再判断队列中是否还有元素，若没有将队尾指针指向NULL，                                       若有直接让对列内元素个数减一；

                     5.返回队头元素：判断队列是否为空，再返回队头元素；

                     6.判断队列是否为空、返回队里元素个数；

       具体实现代码如下：

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

typedef int QDataType;

//用单链表实现队列
typedef struct QNode
{
	QDataType val;
	struct QNode* next;
} QNode;

typedef struct Queue
{
	QNode* front; //指向链表的第一个结点
	QNode* rear;  //指向链表中最后一个结点
	int size;     //队列中元素的个数
} Queue;

//初始化
void QueueInit(Queue* queue)
{
	queue->front = NULL;
	queue->rear = NULL;
	queue->size = 0;
}

//销毁
void QueueDestory(Queue* queue)
{
	QNode* next;
	for (QNode* cur = queue->front; cur != NULL; cur = next)
	{
		next = cur->next;
		free(cur);
	}
	queue->front = NULL;
	queue->rear = NULL;
	queue->size = 0;
}

//增删改查
//只能在队尾插入
void QueuePush(Queue* queue, QDataType val)
{
	//申请新节点
	QNode* node = (QNode*)malloc(sizeof(QNode));
	assert(node);
	node->next = NULL;
	node->val = val;
	if (queue->rear == NULL)
	{
		queue->front = queue->rear = node;
	}
	else
	{
		queue->rear->next = node;
		queue->rear = node;
	}
}

//只能从队首删除
void QueuePop(Queue* queue)
{
	assert(queue->size > 0);
	QNode* cur = queue->front;
	queue->front = queue->front->next;
	free(cur);
	if (queue->front == NULL);
	{
		queue->rear = NULL;
	}
	--queue->size;
}

//返回队首元素
QDataType QueueFront(const Queue* queue)
{
	assert(queue->size > 0);
	return queue->front->val;
}

//判断链表是否为空
int QueueEmpty(const Queue* queue)
{
	return queue->size > 0 ? 0 : 1;
}

//队列的大小
int QueueSize(const Queue* queue)
{
	return queue->size;
}