博客

前言

栈和队列是两种常用的数据结构，因此，了解他们的概念、结构和实现方法是十分基础且必要的。

一、栈

1.栈的概念及结构

栈

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

压栈

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


出栈

：栈的删除操作叫做出栈，出数据也在栈顶。

1.栈的实现

数组和链表都可以用来实现栈，一般来说用数组实现更优、因为数组尾插的代价较小。

实现思路

：建立一个结构体Stack、结构体成员包括存储栈元素的数组a、栈顶top、和栈容量capacity，通过栈顶值控制入栈（top++）出栈（top–）、判空（top==0）等操作、当栈顶与容量相等时，实现自动扩容（cap*=2 + realloc）。具体过程见代码：

头文件
***Stack.h***

#pragma once

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

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

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


//后进先出
void StackInit(Stack *pst);//栈的初始化
void StackDestory(Stack *pst);//栈的销毁
void StackPush(Stack* pst, STDataType x);//压栈
void StackPop(Stack* pst);//出栈
int StackSize(Stack* pst);//获取栈内有效元素的个数
STDataType StackTop(Stack* pst);//获取栈顶元素
//返回1 为空，非空返回0
int StackEmpty(Stack* pst);//判断栈是否为空

主体部分
***Stack.c***


#include "Stack.h"

//后进先出
void StackInit(Stack *pst)
{
	assert (pst);

	//开辟大小自选
	pst->a = malloc(sizeof(STDataType) * 4);
	pst->top = 0;
	pst->capacity = 4;

}
void StackDestory(Stack *pst) 
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
void StackPush(Stack* pst, STDataType x)
{
	
	assert(pst);

	if (pst->top == pst->capacity) 
	{
		//pst->a = realloc(pst->a,sizeof(STDataType)*2*pst->capacity);
		STDataType *tmp = realloc(pst->a, sizeof(STDataType) * 2 * pst->capacity);
		if (tmp == NULL) 
		{
			printf("realloc fail\n");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity *= 2;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
void StackPop(Stack* pst) 
{
	assert(pst);
	//为空报错
	assert(!StackEmpty(pst));
	
	pst->top--;
}
int StackSize(Stack* pst) 
{
	assert(pst);

	return pst->top;
}
STDataType StackTop(Stack* pst) 
{
	assert(pst);
	assert(!StackEmpty(pst));

	return pst->a[pst->top-1];
}
//返回1 为空，非空返回0
int StackEmpty(Stack* pst) 
{
	assert(pst);

	return pst->top == 0 ? 1 : 0;
}

测试文件
test.c
#include"Stack.h"


void test() {
	Stack  st;
	
	StackInit(&st);
	
	StackPush(&st,1);
	StackPush(&st,2);
	StackPush(&st,3);
	StackPush(&st,4);
	StackPush(&st,5);
	while (!StackEmpty(&st))
	{
		printf("%d", StackTop(&st));
		StackPop(&st);
	}
	StackDestory(&st);
}

int main() {

	test();
	return 0;
}

共实现七个常用接口，包括栈的初始化、栈的销毁、压栈、出栈、获取栈内有效元素的个数、获取栈顶元素、与判断栈是否为空。测试文件测试结果如下：



可以看到栈后进先出的规律。

二、队列

1.队列的概念及结构

队列

：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 。


入队列

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


出队列

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

2.队列的实现

队列也可以用数组和链表实现，使用链表的结构实现更优，因为如果使用数组结构，出队列在数组头出数据，效率较低

实现思路

：创建一个结构体Queue、结构体成员包括两个链表节点front和tail，分别代表队列的队头和对尾。通过对两个成员进行操作，实现队列的入队、出队等操作。具体过程见代码：

头文件
***Queue.h***

#pragma once

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

typedef int QDataType;
typedef struct QueueNode 
{
	QDataType data;
	struct QueueNode* next;
	
}QueueNode;

typedef struct Queue
{
	QueueNode* front;
	QueueNode* tail;
}Queue;

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

void QueuePush(Queue* pq, QDataType x);//入队
void QueuePop(Queue* pq);//出队
QDataType QueueFront(Queue* pq);//获取队列头部元素
QDataType QueueBack(Queue* pq);//获取队列尾部元素
int QueueSize(Queue* pq);//获取队列有效元素个数
int QueueEmpty(Queue* pq);//队列判空

主体
***Queue.c***

#include"Queue.h"


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

	pq->front = 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->tail == NULL)
	{
		pq->front = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->front == pq->tail)
	{

		free(pq->front);
		pq->front = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->front->next;
		free(pq->front);
		pq->front = next;
	}
}
int QueueSize(Queue* pq)
{
	assert(pq);

	int size = 0;
	QueueNode* cur = pq->front;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

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

	return pq->tail->data;
}
int QueueEmpty(Queue* pq)
{
	assert(pq);

	return  pq->front == NULL ? 1 : 0;
}
void QueueDestory(Queue* pq)
{
	assert(pq);

	QueueNode* cur = pq->front;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->front = pq->tail = NULL;
}

测试部分
***test.c***

#include"Queue.h"


void test()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	while (!QueueEmpty(&q))
	{
		int front = QueueFront(&q);
		printf("%d", front);
		QueuePop(&q);
	}
	printf("\n");
	QueueDestory(&q);
}


int main()
{
	test();
	return 0;
}

实现七个接口，包括队列初始化、销毁队列、入队、出队、获取队列头部元素、获取队列尾部元素、获取队列有效元素个数和队列判空。

测试代码结果如下：



可以观察到其先进先出的特性。