数据结构（四）栈和队列

栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作

进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则

 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶

出栈：栈的删除操作叫做出栈

出数据也在栈顶  后进先出

栈的实现

头文件

声明

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

//创建栈
typedef int STDataType;
typedef struct Stack
{
	int* a;
	int top;
	int capacity;
}ST;

//栈的初始化和销毁
void STInit(ST* ps);
void STDestroy(ST* ps);

//插入
void STPush(ST* ps, STDataType x);

//删除
void STPop(ST* ps);

//计算栈的大小
int STSize(ST* ps);

//判断是否为空
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);

源文件

实现

#include"Stack.h"


void STInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->capacity = 4;
	ps -> top = 0;	//top是栈顶元素下一个位置
  //ps ->top = -1;	  top是栈顶元素位置
}


void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}


void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//满了扩容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity*2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	//没满把数据放进去，top++
	ps->a[ps->top] = x;
	ps->top++;
}


void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));//暴力检查
	ps->top--;

}


int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
	//给0的时候是top
	//给-1的时候是top+1
}


bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}


STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top-1];
}

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表

队列具有先进先出 FIFO(First In First Out) 的特点

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出

队列在数组头上出数据，效率会比较低

头文件

声明

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

//链式结构：表示队列
typedef int QDatatype;
typedef struct QueueNode
{
	struct	QueueNode* next;
	QDatatype data;
}QNode;


//队列的结构
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

// 队列的初始化和销毁
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);

//队尾入队列
void QueuePush(Queue* pq,QDatatype x);

//队头出队列
void QueuePop(Queue* pq);

//获取队列中有效元素个数
int QueueSize(Queue* pq);

//检测队列是否为空
bool QueueEmpty(Queue* pq);

//获取队列头部元素
QDatatype QueueFront(Queue* pq);

//获取队列队尾元素
QDatatype QueueBack(Queue* pq);

源文件

实现

#include"queue.h"


void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}


void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}


void QueuePush(Queue* pq, QDatatype x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		assert(pq->tail == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}


void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);
	//法一
	QNode* next = pq->head->next;
	free(pq->head);
	pq->head= next;
	if (pq->head == NULL)
		pq->tail = NULL;
	pq->size--;

	/*法二
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}*/

}


int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}


bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}


QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//因为这个QueueEmpty是一个函数，所以需要调用
	return pq->head->data;
}


QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}