栈的概念

一句话：先进后出！ 请添加图片描述

我可以实现顺序栈，或者链式栈，但是由于栈只需要找尾，然后删除，故顺序栈是最优选！

栈的创建

和顺序表很类似！

typedef int STDataType;

typedef struct Stack
{
	STDataType* data;//数据	
	int top;//栈顶
	int capacity;//容量
}Stack;

初始化栈

void StackInit(Stack* ps)
{
	assert(ps);
	ps->capacity = 0;
	ps->data = NULL;
	ps->top = 0;
}

入栈

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity)//判断容量
	{
		int newcapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity);//扩容后的容量
		STDataType*tmp=realloc(ps->data,sizeof(STDataType)*newcapacity);//扩容
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->data = tmp;
	}
	ps->data[ps->top] = data;//压入数据
	ps->top++;
}

出栈

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top);//防止为空
	ps->top--;
}

获取栈顶元素

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top);//防止为空
	return ps->data[ps->top-1];//top位置是压入数据的位置，所以栈顶元素也就是它前一个元素
}

获取栈的元素个数

int StackSize(Stack* ps)
{
	return ps->top;
}

检测栈是否为空

int StackEmpty(Stack* ps)
{
	if (ps->top == 0)return 1;
	else return 0;
}

销毁栈

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->data);
	ps ->data= NULL;
	ps->top = 0;
	ps->capacity = 0;
}

队列的概念

一句话：和栈相反，就是先进先出！
请添加图片描述
队列也有顺序队列和链式队列，这里我们优选链式队列，因为我们的头和尾要频繁移动，但是有同学会说，用单链表的话找尾不是要遍历吗？这里我要说的是由于队列只需要尾插而不需要尾删，我们直接可以定义一个指针指向尾即可！

创建队列

typedef int QNodeType;

typedef struct QueueNode// 节点
{
	QNodeType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	int size;//记录个数
	QueueNode* head;
	QueueNode* tail;
}Queue;

初始化队列

void QueueInit(Queue* q)//初始化
{
	assert(q);
	q->head = q->tail = NULL;
	q->size = 0;
}

入列（就是尾插）

void QueuePush(Queue* q, QNodeType x)//入列
{
	assert(q);
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newNode->next = NULL;
	newNode->data = x;
	if (q->head == NULL)
	{
	q->head=q->tail = newNode;
	q->size++;
	}
	else
	{
		q->tail->next = newNode;
		q->size++;
		q->tail = newNode;
	}

}

出列（就是头删）

void QueuePop(Queue* q)//出列
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head->next == NULL)//一个数据
	{
		free(q->head);
		q->head = NULL;
	}
	else//多个数据
	{
		QueueNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	q->size--;


}

队列的头（先出去）

QNodeType QueueFront(Queue* q)//队列的头
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}

队列的尾（后出去）

QNodeType QueueBack(Queue* q)//队列的尾
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

判断队列是否为空

int QueueEmpty(Queue* q)//判断是否为空
{
	if (q->head == NULL)
		return 1;
	else
		return 0;
}

输出队列的元素个数

int QueueSize(Queue* q)//输出个数
{
	return q->size;
}

销毁队列

void QueueDestory(Queue* q)//销毁队列
{
	assert(q);
	QueueNode* cur = q->head;
	while (cur)
	{
		if(cur->next==NULL)
		{
			free(cur);
			cur = NULL;
		}
		else
		{
			QueueNode* next = cur->next;
			free(cur);
			cur = next;
		}
	}
	QueueInit(q);
}