数据结构基础--栈和队列

一、栈

 栈：一种特殊的线性表，只允许在固定的一端进行插入与删除元素操作。
进行数据插入和删除操作的一段，称为栈顶，另一端称为栈底
栈中的数据元素遵循后进先出LIFO的原则
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈。出数据在栈顶

如果用数组实现，相当于顺序表的尾插尾删，用尾去做了栈顶，唯一的缺陷就是空间不够需要增容
如果用链表实现，如果用链表尾做栈顶，那么用双向链表更方便
如果要用单链表实现，那么就用头去做栈顶更好，入栈出栈效率都是O(1)

 栈的接口函数：

#pragma once
#include
#include
#include
#include
#include
 
typedef int STDataType;
 
typedef struct Stack
{
	STDataType* a;//建立一个动态数组
	STDataType top;//栈顶
	STDataType capacity;//栈的容量
}ST;
 
//接口函数
void StackInit(ST* ps);//初始化
void StackDestory(ST* ps);//销毁
void StackPush(ST*ps,STDataType x);//入栈，不分头插尾插，因为栈只能在栈顶操作
void StackPop(ST* ps);//出栈
STDataType StackTop(ST* ps);//取栈顶数据
int StackSize(ST* ps);//得到栈的数据个数
bool StackEmpty(ST* ps);//判断栈是否为空

 栈接口函数的实现：

#include"Stack.h"
//栈：一种特殊的线性表，只允许在固定的一端进行插入与删除元素操作。
//进行数据插入和删除操作的一段，称为栈顶，另一端称为栈底
//栈中的数据元素遵循后进先出LIFO的原则
//压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
//出栈：栈的删除操作叫做出栈。出数据在栈顶
 
//如果用数组实现，相当于顺序表的尾插尾删，用尾去做了栈顶，唯一的缺陷就是空间不够需要增容
//如果用链表实现，如果用链表尾做栈顶，那么用双向链表更方便
//如果要用单链表实现，那么就用头去做栈顶更好，入栈出栈效率都是O(1)
 
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a==NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
	//初始top=0，意味着top指向栈顶元素的下一个
	//初始top=-1，意味着top指向栈顶元素
}
 
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
 
void StackPush(ST* ps,STDataType x)
{
	assert(ps);
	if (ps->top==ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp==NULL)
		{
			printf("realloc fail\n");
			exit(-1);//终止程序
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}
 
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top>0);//空栈时调用top直接终止程序报错
	ps->top--;//直接将栈顶数据删除，下一次有数据入栈会覆盖top位置
}
 
STDataType 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);
	return ps->top == 0;//如果top为零，说明栈中没有元素，为空
	//返回布尔值为1
}

二、队列

 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
队列具有先进先出的特点
入队列：进行插入操作的一段称为队尾
出队列：进行删除操作的一段称为队头

如果采用数组，队头出数据需要挪动数据
如果采用单链表，入数据就是尾插，出数据就是头删

队列的接口函数：

#pragma once
 
#include
#include
#include
#include
 
typedef int QDataType;
 
typedef struct QueueNode//创建一个队列节点
{
	struct QueueNode* next;
	QDataType data;
}QNode;
 
 
typedef struct Queue//创建一个队列
{
	QNode* head;//指向队头
	QNode* tail;//指向队尾
}Queue;
 
 
void QueueInit(Queue* Q1);
void QueueDestory(Queue* Q1);
void QueuePush(Queue* Q1,QDataType x);//队尾入
void QueuePop(Queue* Q1);//队头出
QDataType QueueFront(Queue* Q1);
QDataType QueueBack(Queue* Q1);
int QueueSize(Queue* Q1);
bool QueueEmpty(Queue* Q1);

队列接口函数的实现： 

//队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
//队列具有先进先出的特点
//入队列：进行插入操作的一段称为队尾
//出队列：进行删除操作的一段称为队头
 
//如果采用数组，队头出数据需要挪动数据
//如果采用单链表，入数据就是尾插，出数据就是头删
#include"Queue.h"
void QueueInit(Queue* Q1)
{
	assert(Q1);
	Q1->head = Q1->tail = NULL;
}
 
void QueueDestory(Queue* Q1)
{
	assert(Q1);
	QNode* cur = Q1->head;
	while (cur)
	{
				QNode * next = cur->next;
				free(cur);
				cur = next;
	}
}
 
void QueuePush(Queue* Q1,QDataType x)
{
	assert(Q1);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode==NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (Q1->tail==NULL)
	{
		Q1->head =Q1->tail= newnode;
	}
	else
	{
		Q1->tail->next = newnode;//在tail后插入新结点
		Q1->tail = newnode;//将新结点变为为结点
     }
}
 
 
void QueuePop(Queue* Q1)
{
	assert(Q1);
	assert(Q1->head);//保证队列存在，并且队列不为空
	if (Q1->head->next==NULL)
	{
		free(Q1->head);
		Q1->head = Q1->tail = NULL;//将队头队尾指针置空，避免野指针问题
	}
	else
	{
		QNode* next = Q1->head->next;
	    free(Q1->head);
	    Q1->head = next;
	}
}
 
QDataType QueueFront(Queue* Q1)
{
	assert(Q1);
	assert(Q1->head);
 
	return Q1->head->data;
}
 
QDataType QueueBack(Queue* Q1)
{
	assert(Q1);
	assert(Q1->tail);
	return Q1->tail->data;
}
 
int QueueSize(Queue* Q1)
{
	assert(Q1);
	int size = 0;
	QNode* cur = Q1->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
 
bool QueueEmpty(Queue* Q1)
{
	assert(Q1);
	return Q1->head == NULL;
}