【数据结构】线性表之栈和队列

一、栈

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

        进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，栈中的数据元素遵守后进先出的原则。

        它的插入操作叫做进栈（或进栈/入栈），插入的数据在栈顶；删除操作叫做出栈。出的数据也在栈顶。

        它主要通过数组来实现（其实数组或者链表实现均可，但相对而言数组更优），有静态栈和动态栈之分。静态栈拥有两个通过结构体封装的结构体成员——存储数据的定长数组和栈顶元素的下标。

#define N 10
struct Stack
{
	int a[N];
    int top;
};

        和顺序表类似，存储数据的数组虽然可以由定长数组来充当，但有不确定的容量问题。所以，实际应用一般仍是以拥有动态数组的动态栈为主。  

        动态栈拥有三个通过结构体封装的结构体成员——存储数据的动态数组、空间容量和栈顶的相关下标，同时拥有一系列函数接口。

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;    //存储数据的动态数组
	int capacity;     //空间容量
	int top;          //栈顶的相关下标

}ST;

void STInit(ST* ps);                    //初始化栈
void STPush(ST* ps, STDataType x);      //入栈
void STPop(ST* ps);                     //出栈
bool STEmpty(ST* ps);                   //验空
int STSize(ST* ps);                     //获取有效数据个数
STDataType STTop(ST* ps);               //访问栈顶元素
void STDestroy(ST* ps);                 //销毁栈

1、初始化栈

        开辟动态数组的空间，并初始化空间容量和栈顶的相关下标。

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就是栈顶元素位置
}

2、验空

        若栈顶的相关下标在数组的起始位置，即栈顶的相关下标值为0，则栈为空。

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

3、入栈

        入栈前应先检查栈的空间容量，空间容量不足就先扩容再入栈。

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;
	}
    
    //入栈
	ps->a[ps->top] = x;

    //入栈后top应自增1
	ps->top++;
}

4、出栈

        使栈顶的相关下标自减1即可。

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

5、获取有效数据个数

        栈顶的相关下标的值，即为有效数据个数。

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

6、访问栈顶元素

        因为初始化时栈顶的相关下标top是实际栈顶元素的下一位，故 top - 1 为栈顶元素的下标。

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}

7、销毁栈

        释放动态数组，将空间容量和栈顶的相关下标和空间容量置为0即可。

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

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

· 代码汇总

        Stack.h

#define _CRT_SECURE_NO_WARNINGS\


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

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;


void STInit(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);
void STDestroy(ST* ps);

        Stack.c

#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;  
}

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;
	}

	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;
}

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];
}

二、队列

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

         队列主要通过链表来实现（其实数组和链表均可，但使用数组的结构出队列时，在数组头上出数据效率会比较低，故链表更优 ），拥有三个通过结构体封装的结构体成员——头节点（队头）、尾节点（队尾）和有效数据个数，每个节点由两个结构体成员组成——当前节点数据和指向下一节点的next指针。与此同时，它还有一系列接口。

typedef char QDatatype;

//节点
typedef struct QueueNode
{
	QDatatype data;            //数据
	struct QueueNode* next;    //指向下一节点的指针
}QNode;

//队列
typedef struct Queue
{
	QNode* head;    //头节点
	QNode* tail;    //尾节点
	int size;       //有效数据个数
}Queue;


void QueueInit(Queue* pq);                //初始化队列
bool QueueEmpty(Queue* pq);               //验空
void QueuePush(Queue* pq, QDatatype x);   //入队
void QueuePop(Queue* pq);                //出队
int QueueSize(Queue* pq);                //获取有效数据个数
QDatatype QueueFront(Queue* pq);         //取队头
QDatatype QueueBack(Queue* pq);          //取队尾
void QueueDestroy(Queue* pq);            //销毁队列

  

1、初始化队列

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;    //将头节点、尾节点均置空
	pq->size = 0;                  //将有效数据个数置为0
}

2、验空

        有效数据个数size的值为0，则队列为空。

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

3、入队

        将一个新节点与队尾连接即可。

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++;        //节点入队后，有效数据个数自增1
}

4、出队

        将头节点释放，并让头节点的下一个节点成为新的头节点。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);

	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;                 //释放原先的头节点，然后将第二个节点设为新的头节点
	}

	pq->size--;    //出队后，有效数据个数自减1
	
}

5、获取有效数据个数

        获取队列中的有效数据个数size即可。

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

6、取队头

        取头节点中的数据即可。

QDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

7、取队尾

        取尾节点中的数据即可。

QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

8、销毁队列

        遍历队列，逐个节点释放，结束后将头尾节点置空、有效数据个数置为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;
}

· 代码汇总

        Queue.h​​​​​​​

#define _CRT_SECURE_NO_WARNINGS

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

typedef char QDatatype;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDatatype data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;


void QueueInit(Queue* pq);
bool QueueEmpty(Queue* pq);
void QueuePush(Queue* pq, QDatatype x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);
void QueueDestroy(Queue* pq);

        Queue.c

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

	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;
	}

	pq->size--;
	
}

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

	return pq->head->data;
}

QDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

[补] 循环队列

        循环队列（或称环形队列）可以使用数组实现，也可以使用循环链表实现，也是实际中常用的一种队列。本博客于此仅展示其理论的逻辑结构，具体实现暂不展开。