数据结构-栈和队列

文章目录

• • 栈
  • • 什么是栈
    • 栈的操作
    • 栈的特点
    • 栈的实现
    • 栈的时间复杂度
    • 栈的应用
  • 队列
  • • 队列的概念
    • 队列的操作
    • 队列的实现
    • 队列的时间复杂度

栈

什么是栈

堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。

栈的操作

这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈的特点

先进后出，后进先出

栈的实现

顺序栈：
一、思路
1.通过动态数组的来实现，保证数组的空间足够
2.我们要实现栈需要实现入栈和出栈等函数
3.通过结构体来存储不同数据

二、框架
Stack.h

//需要用的函数头文件
#include <stdio.h>//输入
#include <stdlib.h>//扩容
#include <assert.h>//断言
#include<stdbool.h> //判断真假

typedef int STDataType;//定义类型名
typedef struct Stack//构建结构体和定义类型名
{
	STDataType* a;//指针
	int top;//数组下标
	int capacity;//容量
}ST;

test.c

void test() {
	ST  s;//结构体变量
	}

三、函数实现
1.初始化函数
初始化结构体内容

void StackInit(ST* ps)//初始化
{
	assert(ps);//断言
	ps->a = (STDataType*)malloc(sizeof(STDataType)*4);//开始先给四个空间
	ps->capacity = 4;//容量大小
	ps->top = 0;//数组下标
}

ST  s;
StackInit(&s);//初始化，改变内容需要用传址调用

2.入栈函数
将数据压栈到栈顶

（1）.栈底是固定的，栈顶会随着入栈变化
（2）.入栈要判断空间是否够，不够扩容

代码实现：

void StackPush(ST* ps, STDataType x) //入栈
{
	assert(ps);
	//先判断是否需要扩容
	if (ps->capacity == ps->top) {
		STDataType* p = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);
		if (p == NULL) {//是否扩容成功
			printf("reallocfail\n");
			exit(-1);//终止程序
		}
		else {
			ps->a =p;
			ps->capacity = ps->capacity * 2;//更新容量大小
		}
	}
	ps->a[ps->top] = x;//压栈
	ps->top++;//元素增加
}

3.出栈函数
从栈顶出栈

代码实现：

void StackPop(ST* ps) {// 出栈
	assert(ps);//断言
	assert(ps->top);//断言是否有元素
	ps->a[ps->top - 1] = 0;//置0
	ps->top--;//元素个数减1
}

4.元素大小函数
直接放回我们记录的元素大小即可
代码实现

int StackSize(ST* ps) {//数组元素个数
	assert(ps);//断言
	return ps->top;//返回数组元素的个数
}

5.判断是否为空函数
通过bool类型来判断，空的话为真，否则返回假
代码实现

bool StackEmpty(ST* ps) {//判断是否为空
	assert(ps);//断言
	return ps->top==0;//如果top==0就返回真
}

6.释放函数
当我们不用时就将申请的空间释放
代码实现

void StackDestory(ST* ps) {//释放
	assert(ps);//断言
	//释放并置空
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

7.总代码：
Stack.h

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

typedef int STDataType;

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

void StackInit(ST* ps);//初始化
void StackDestory(ST* ps);//释放
// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);
STDataType StackTop(ST* ps);//出栈的元素

int StackSize(ST* ps);//返回元素个数
bool StackEmpty(ST* ps);//是否为空

Stack.c

#include"Stack.h"
void StackInit(ST* ps)//初始化
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType)*4);
	ps->capacity = 4;
	ps->top = 0;
}
void StackPush(ST* ps, STDataType x) //入栈
{
	assert(ps);
	if (ps->capacity == ps->top) {
		STDataType* p = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);
		if (p == NULL) {
			printf("reallocfail\n");
			exit(-1);//终止程序
		}
		else {
			ps->a =p;
			ps->capacity = ps->capacity * 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps) {// 出栈
	assert(ps);
	assert(ps->top);
	ps->a[ps->top - 1] = 0;
	ps->top--;
}
STDataType StackTop(ST* ps) {//出栈的元素
	assert(ps);
	assert(ps->top);
	return ps->a[ps->top - 1];
}
int StackSize(ST* ps) {//数组元素个数
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps) {//判断是否为空
	assert(ps);
	return ps->top==0;
}
void StackDestory(ST* ps) {//释放
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

test.c

#include"Stack.h"
void test() {
	ST  s;
	StackInit(&s);
	//压栈
	StackPush(&s, 1);
	StackPush(&s, 2);
    StackPush(&s, 3);
	while (s.top) {
		STDataType te = StackTop(&s);//打印出栈
		StackPop(&s);
		printf("%d ", te);
	}
}
int main() {
	test();
	return 0;
}

运行结果：

先进栈的后出栈，所以先出3>2>1

栈的时间复杂度

因为每一次压栈出栈只需要进行一次操作，所以时间复杂度为O（1）

栈的应用

车厢调度问题：

分析
1.从A方向来的车厢有可能进入车站C后就留在车站C，这个过程就是我们的压栈，也有可能进入后就往B的方向行使了，这个过程就是我们的出栈。
2.因为车厢是不连接的，所以每节车厢离开的情况是不同的，有可能是进C就直接离开，也有可能停留，这样就要等其他车厢都离开后才能离开了
比如：

3.就是先要实现一个栈，再根据题目输入出栈的顺序，然后从1开始到n进行压栈，要是在压栈的过程中有与我们输入顺序相同的数据就出栈，直到压到n，再然后就是判断是否n个都符合条件出栈了，要是没有就按先进后出，后进先出的规则，来出栈与剩下输入顺序的数据对比，要是相同就继续，没有就打破，最后判断栈是否为空，为空则符合，不为空则输入顺序不符合
代码实现：

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

typedef int STDataType;

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

void StackInit(ST* ps);//初始化
void StackDestory(ST* ps);//释放
// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);
STDataType StackTop(ST* ps);//出栈的元素

int StackSize(ST* ps);//返回元素个数
bool StackEmpty(ST* ps);//是否为空

void StackInit(ST* ps)//初始化
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType)*4);
	ps->capacity = 4;
	ps->top = 0;
}
void StackPush(ST* ps, STDataType x) //入栈
{
	assert(ps);
	if (ps->capacity == ps->top) {
		STDataType* p = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);
		if (p == NULL) {
			printf("reallocfail\n");
			exit(-1);//终止程序
		}
		else {
			ps->a =p;
			ps->capacity = ps->capacity * 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps) {// 出栈
	assert(ps);
	assert(ps->top);
	ps->a[ps->top - 1] = 0;
	ps->top--;
}
STDataType StackTop(ST* ps) {//出栈的元素
	assert(ps);
	assert(ps->top);
	return ps->a[ps->top - 1];
}
int StackSize(ST* ps) {//数组元素个数
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps) {//判断是否为空
	assert(ps);
	return ps->top==0;
}
void StackDestory(ST* ps) {//释放
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

//上面是栈的实现
bool test1() {
	int arr[1000] = { 0 },n=0;//按照题目要求。n最大为1000
	scanf("%d", &n);//车厢个数
	for (int i = 0; i < n; i++)//输入出站顺序
		scanf("%d", &arr[i]);
	ST s;
	StackInit(&s);
	int j = 1;
	int t = 0;
	while (j <= n) {//从1开始进站
		StackPush(&s, j);//压栈
		if (j == arr[t]) {//相同的数据就出栈
			StackPop(&s);
			t++;
		}
		j++;
	}
	while (t < n) {//判断是否都出了
		STDataType te = StackTop(&s);//取出栈顶的元素
		if (te == arr[t]) {//对比
			StackPop(&s);
			t++;
		}
		else {
			break;
		}
	}
	bool pd=StackEmpty(&s);//判断栈是否为空
	StackDestory(&s);//释放
	return pd;/返回
}

int main() {
	if (test1())
	printf("YES\n");
	else
		printf("NO\n");
	return 0;
}

队列

队列的概念

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。

队列的操作

进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的实现

单链表实现:
一、思路
1.通过两个指针来实现，一个指向对头，一个指向队尾，这样方便了插入和删除
2.实现头删和尾插等函数
二、框架
Queue.h

//用到的头文件
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;//重新命名

typedef struct QueueNode
{
	struct QueueNode* next;//前驱指针
	QDataType data;//数据
}QNode;重新命名

typedef struct Queue
{
	QNode* head;//队头的指针
	QNode* tail;//队尾指针
}Queue;//重新命名

test.c

void test() {
	Queue p;//结构体变量
	}

三、实现函数
1.初始化函数
将结构体变量初始化
代码实现

void QueueInit(Queue* pq) {//初始化
	assert(pq);//断言
	pq->head = pq->tail = NULL;//将两个结构体指针都置空
}

2.插入函数
（1）先扩容
（2）从队尾插入数据
代码实现

void QueuePush(Queue* pq, QDataType x) {//队尾入
	assert(pq);
	QNode* p = (QNode*)malloc(sizeof(QNode));//扩容
	if (p == NULL) {//判断是否成功
		printf("malloc fail\n");
		exit(-1);
	}
	p->data = x;//再新的空间加入数据
	p->next = NULL;
	//判断是否是没有数据
	if (pq->tail == NULL)
		pq->head = pq->tail = p;
	else {
		pq->tail->next = p;
		pq->tail = p;
	}
}

3.删除数据函数
分为只有1个数据和有多个数据
代码实现

void QueuePop(Queue* pq) {
	assert(pq);
	//一个
	if (pq->head->next == NULL) {
		free(pq->head);//只有一个数据随便释放一个队头或者队尾都行，并置空
		pq->head = pq->tail == NULL;
	}
	//多个
	//
	else {
		Queue* p = pq->head->next;//先保存下一个结点，在释放队头
		free(pq->head);
		pq->head = NULL;
		pq->head = p;//换队头
	}
}

4.取出队头函数
我们直接利用队头指针去放回数据即可
代码实现

QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(pq->head);//队头不能为空
	return pq->head->data;//取数据
}

5.计算队列大小函数
（1）设置一个计算变量
（2）为了队头不变。先将队头复制，再通过遍历迭代到队尾

int QueueSize(Queue* pq) {
	assert(pq);
	assert(pq->tail);
	int n = 0;//计数器
	QNode* p = pq->head;//复制
	while (p)
	{
		n++;
		p = p->next;//迭代
	}
	return  n;//返回计算器
}

6.判断队列是否为空
我们只需要判断队头即可，对头为空，则队列为空

bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->head==NULL;
}

7.释放函数
（1）.我们通过队头找到下一个结点，再释放队头
（2）.通过迭代方式实现逐个释放，并最后要将队头和队尾都释放

void QueueDestory(Queue* pq) {
	assert(pq);
	while (pq->head) {
		QNode* p = pq->head->next;
		free(pq->head);
		pq->head = NULL;
		pq->head = p;//迭代
	}
	pq->head = pq->tail = NULL;//队头和队尾都释放
}

8.总代码：
Queue.h

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;

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

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

void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);

// 队头出
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);//头出
QDataType QueueBack(Queue* pq);//尾出
int QueueSize(Queue* pq);//个数
bool QueueEmpty(Queue* pq);//是否为空

Queue.c

#include"Queue.h"
void QueueInit(Queue* pq) {//初始化
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x) {//队尾入
	assert(pq);
	QNode* p = (QNode*)malloc(sizeof(QNode));
	if (p == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}
	p->data = x;
	p->next = NULL;
	if (pq->tail == NULL)
		pq->head = pq->tail = p;
	else {
		pq->tail->next = p;
		pq->tail = p;
	}
}

void QueuePop(Queue* pq) {
	assert(pq);
	//一个
	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail == NULL;
	}
	//多个
	else {
		Queue* p = pq->head->next;
		free(pq->head);
		pq->head = NULL;
		pq->head = p;
	}
}

QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
int QueueSize(Queue* pq) {
	assert(pq);
	assert(pq->tail);
	int n = 0;
	QNode* p = pq->head;
	while (p)
	{
		n++;
		p = p->next;
	}
	return  n;
}

bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->head==NULL;
}

void QueueDestory(Queue* pq) {
	assert(pq);
	while (pq->head) {
		QNode* p = pq->head->next;
		free(pq->head);
		pq->head = NULL;
		pq->head = p;
	}
	pq->head = pq->tail = NULL;
}

test.c

#include"Queue.h"
void test() {
	Queue p;
	QueueInit(&p);
	QueuePush(&p,1);//插
	QueuePush(&p, 2);
	QueuePush(&p, 3);
	while (p.head) {//打印数据
		QDataType te=QueueFront(&p);
		QueuePop(&p);//删
		printf("%d ", te);
	}
}

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

根据代码来运行：

队列的时间复杂度

队列的操作过程（插和删）中的时间复杂度都为O（1）

以上就是我的分享了，如果有什么错误，欢迎在评论区留言。
最后，谢谢大家的观看！