数据结构之栈和队列

栈

栈的概念及结构栈的实现 队列

队列的概念及结构队列的实现循环队列

本章学习线性表中的栈和队列。

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

栈是线性表的一种，那么栈的存储形式可以选择连续存储或者链式存储。

数组栈：数组尾作为栈顶，尾插、尾删效率高，缓存命中率高，缺点是空间不够需要扩容。

链式栈：头结点作为栈顶，可以选择单链表；如果尾结点作为栈顶，那么选择双向链表，否则删除、插入效率低。

单链表栈

双向链表栈


二者更推荐数组栈。

下面我们来实现动态数组栈

定义数组栈结构体类型

#pragma once
#include 
#include 
#include 
#include 

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
//栈初始化
void StackInit(ST* ps);
//销毁栈
void StackDestroy(ST* ps);
//数组容量检查
void CheckCapacity(ST* ps);
//入栈
void StackPush(ST* ps, STDataType data);
//出栈
void StackPop(ST* ps);
//返回栈顶元素
STDataType StackTop(ST* ps);
//栈大小
int StackSize(ST* ps);
//栈是否为空
bool StackEmpty(ST* ps);

接口实现

#include "stack.h"


void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//top指向栈顶元素的下一个
	//ps->top = -1;//top指向栈顶数据
	ps->capacity = 0;
}

void StackDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

//判断空间大小
void CheckCapacity(ST* ps)
{
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;

		//扩容
		STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			exit(-1);
		}

		ps->a = tmp;

		ps->capacity = newCapacity;
	}
}

//入栈
void StackPush(ST* ps, STDataType data)
{
	assert(ps);
	
	CheckCapacity(ps);

	ps->a[ps->top] = data;

	ps->top++;

}
//出栈
void StackPop(ST* ps)
{
	assert(ps);

	assert(ps->top > 0);

	ps->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);

	//if (ps->top == 0)
	//{
	//	return false;
	//}
	//else
	//{
	//	return true;
	//}

	return ps->top == 0;
}

练习
括号匹配问题

队列是限制在两端进行插入操作和删除操作的线性表，允许进行存入操作的一端称为“队尾”，允许进行删除操作的一端称为“队头”。

队列的特点：

1.队列具有先进先出FIFO(First In First Out) 或者后进后出LILO（Last In Last Out）
2.队列只能在队头和队尾进行数据操作

队列也可以用数组和链表的结构实现，但是使用链表的结构实现更优一些，因为如果使用数组的结构（顺序存储，从头开始存储，中间不能跳跃），那么入队在数组尾入数据，出队列在数组头上出数据，效率会比较低。

队列的链式存储

对于单链表，我们只定义了头指针，没有定义尾指针，因为即使定义尾指针，尾插方便了，但是尾删仍然不方便，所以对于单链表定义尾指针没有意义。

对于队列，一端进一端出，所以我们定义两个指针，并且把链表的尾作为队尾，元素从这端进，链表的头作为队头，数据从这端出。

//队列数据元素的类型
typedef int QDataType;

//队列中数据元素结构体
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

//队列结构体
typedef struct Queue
{
	QueueNode* head;//队头指针
	QueueNode* tail;//队尾指针
	//size_t size;//队列元素个数
}Queue;

对于队列的实现，我们使用链式存储，选择没有哨兵位，这里，我们定义了两个指针，所以选择使用结构体（存放多个成员），当然也可以不使用结构，定义两个指针作为参数（需传入二级指针）。

需要实现如下接口：

//队列初始化
void QueueInit(Queue* pq);

//销毁队列
void QueueDestroy(Queue* pq);

//入队
void QueuePush(Queue* pq,QDataType x);

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

//获取队头元素
QDataType QueueFront(Queue* pq);

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

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

//检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq);

代码如下：

//队列初始化
void QueueInit(Queue* pq)
{
	//我们需要改变结构体的内容（需要改变结构成员head,tail），所以传入结构体指针
	//对于结构的指针成员，要初始化
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;

	while (cur != NULL)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = NULL;
	}
	pq->head = pq->tail = NULL;
}

//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		//1.队列为空
		pq->head = pq->tail = newnode;
	}
	else
	{
		//2.队列不为空，尾部直接插入
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	//队列为空时 head == NULL
	return pq->head == NULL;
}

//出队
void QueuePop(Queue* pq)
{
	assert(pq);//结构体指针是不可能为空的，结构体成员指针指向NULL,与结构体指针为空没有任何关系
	
	//1.队列空
	//assert(pq->head!=NULL);
	assert(!QueueEmpty(pq));

	
	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;

	if (pq->head == NULL)
	{
		//2.只有一个元素 head = tail 注意处理tail变成野指针的情况
		//链表已经删完了
		pq->tail = NULL;
	}	
}

//获取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//assert(pq->tail!=NULL);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

//获取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//assert(pq->head!=NULL);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

//获取队列元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	int sz = 0;
	
	//遍历队列
	while (cur!= NULL)
	{
		sz++;
		cur = cur->next;
	}
	return sz;
}

练习
用队列实现栈
用栈实现队列

循环队列特点：
1.先进先出
2.大小固定，首尾相接
3.可以重复利用之前的空间

环形队列可以使用数组实现，也可以使用循环链表实现。
对于循环队列，无论是数组实现还是循环链表实现，都要多开一个空间，也就是说，要是一个存k个数据的循环队列，就要开k+1个空间，否则没办法实现判空和判满。

数组实现

循环队列为空：front == tail

循环队列满了：(tail+1)%(k+1) == front

tail指向队尾元素的下一个位置，是队尾的下标，front是对头的下标，k是循环队列能够存储数据的大小

（1）空队列

（2）入队

（3）出队

（4）队列满了

tail = 0,front = 1,k = 6
(tail+1)%(k+1) = 1%7 = 1 = front,队列满了。

循环链表实现

（1）空队列

（2）入队

（3）队列满了

tail->next == front;

循环队列练习
循环队列

本章完。