【数据结构】栈与队列-EW帮帮网

本文是小编巩固自身而作，如有错误，欢迎指出！

1.栈

1.1 概念与结构

栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。

栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价⽐较⼩。（在之前我们学过，数组的尾插时间复杂度是O（1），而链表的复杂度是O（N））

1.2栈的实现

1.2.1栈的结构


//定义栈的结构
typedef int stdatatype;
struct Stack
{
	stdatatype* arr;
	int top;//指向栈顶
	int capacity;//栈的容量
};
typedef struct Stack ST;

这里的栈我们采用类似于顺序表的方式实现，一个栈包含如上码所示的三个内容。

1.2.2栈的初始化

和顺序表类似，将数组置空，数据置零。

void stackinit(ST* ps)//栈初始化
{
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

1.2.3入栈

void stackpush(ST* ps, stdatatype x)//入栈
{
	if (ps->top == ps->capacity)//栈满了
	{
		//增容
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		stdatatype* tmp = (stdatatype*)realloc(ps->arr, newcapacity*sizeof(stdatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
     //栈未满
	ps->arr[ps->top++] = x;
}

1.2.4出栈

void stackpop(ST* ps)//出栈
{
	assert(!stackempty(ps));//判空
	--ps->top;
}

在出栈时需要考虑是否为空的情况我们这里使用bool函数。

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

1.2.5取栈顶元素

stdatatype stacktop(ST* ps)//取栈顶元素
{
	assert(!stackempty(ps));
	return ps->arr[ps->top - 1];
}

1.2.6销毁栈

void stackdestroy(ST* ps)//销毁栈
{
	if (ps->arr)
	{
		free(ps->arr);
		ps->arr = NULL;
		ps->top = ps->capacity = 0;
	}
}

1.3完整代码实现

.h文件

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

//定义栈的结构
typedef int stdatatype;
struct Stack
{
	stdatatype* arr;
	int top;//指向栈顶
	int capacity;//栈的容量
};
typedef struct Stack ST;

void stackinit(ST* ps);//栈初始化
void stackpush(ST* ps, stdatatype x);//入栈
void stackpop(ST* ps);//出栈
bool stackempty(ST* ps);//判空
stdatatype stacktop(ST* ps);//取栈顶元素
void stackdestroy(ST* ps);//销毁栈

.c文件

#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"

void stackinit(ST* ps)//栈初始化
{
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
void stackpush(ST* ps, stdatatype x)//入栈
{
	if (ps->top == ps->capacity)
	{
		//增容
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		stdatatype* tmp = (stdatatype*)realloc(ps->arr, newcapacity*sizeof(stdatatype));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	ps->arr[ps->top++] = x;
}
bool stackempty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
void stackpop(ST* ps)//出栈
{
	assert(!stackempty(ps));//判空
	--ps->top;
}
stdatatype stacktop(ST* ps)//取栈顶元素
{
	assert(!stackempty(ps));
	return ps->arr[ps->top - 1];
}
void stackdestroy(ST* ps)//销毁栈
{
	if (ps->arr)
	{
		free(ps->arr);
		ps->arr = NULL;
		ps->top = ps->capacity = 0;
	}
}

.c文件（测试）

#define _CRT_SECURE_NO_WARNINGS
#include"stack.h"
void test01()
{
	ST st;
	stackinit(&st);
	stackpush(&st, 1);
	stackpush(&st, 2);
	stackpush(&st, 3);
	stackpush(&st, 4);
	stackpop(&st);
	while (!stackempty(&st))
	{
		int top = stacktop(&st);
		printf("%d ", top);
		stackpop(&st);
	}
}
int main()
{
	test01();
	return 0;
}

2.队列

2.1概念与结构

概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出。

队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，因为如果使⽤数组的结构，出队列在数组头上出数据，效率会比较低。

2.2队列的实现

2.2.1队列的结构

typedef int QDdatatype;
//节点结构
typedef struct QueueNode
{
	QDdatatype data;
	struct QueueNode* next;
}QUnode;
//队列结构
typedef struct Queue
{
	struct QueueNode* phead;
	struct QueueNode* ptail;
	//int size;//有效数据的个数
}QU;

为了避免像一般单链表在尾部进行操作导致时间复杂度增加，我们相较于单链表多创建一个尾节点。

2.2.2队列的初始化

void QUinit(QU* pq)//初始化
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	//pq->size = 0;
}

2.2.3入队--队尾

void QUpushi(QU* pq, QDdatatype x)//入队--队尾
{
	assert(pq);
	//队列为空
	QUnode* newnode = (QUnode*)malloc(sizeof(QUnode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	//pq->size++;
}

类似于链表中尾插。

2.2.4出队--队头

void QUpop(QU * pq)//出队--队头
	{
		assert(!QUempty(pq));
		//只有一个节点
		if (pq->phead == pq->ptail)
		{
			free(pq->phead);
			pq->phead = pq->ptail = NULL;
		}
		else
		{
			QUnode* next = pq->phead->next;
			free(pq->phead);
			pq->phead = next;
		}
		/*pq->size--;*/
	}

在出队时就要考虑队列为空的情况

bool QUempty(QU* pq)//队列判空
{
	assert(pq);
	return pq->phead == NULL;
}

2.2.5 取头、尾数据

QDdatatype QUfront(QU* pq)//取头数据
	{
		assert(!QUempty(pq));
	    return pq->phead->data;
	}
	QDdatatype QUback(QU* pq)//取尾数据
	{
		assert(!QUempty(pq));
		return pq->ptail->data;
	}

2.2.6销毁队列

void QUdestroy(QU* pq)//销毁队列
	{
		assert(pq);
		QUnode* pcur = pq->phead;
		while (pcur)
		{
			QUnode* next = pq->phead;
			free(pcur);
			pcur = next;
		}
		pq->phead = pq->ptail = NULL;
		/*pq->size = 0;*/
	}

2.3完整代码实现