当前位置: 首页 > article >正文

栈和队列

目录

1、栈的概念及结构

 2、栈的实现

2.1 top的指向

2.2 动态增长顺序栈

2.2.1 Stack.h

2.2.2 Stack.c

2.3 链式堆栈

2.3.1 Stack.h

2.3.2 Stack.c

队列

1、队列的概念及结构

2、队列的实现

2.1 链式队列

2.1.1 Queue.h

2.1.2 Queue.c

2.2 顺序循环队列

2.2.1 Queue.h

2.2.2 Queue.c

Tips:

1、栈(一般实现顺序栈)

2、队列(一般实现链式队列)


1、栈的概念及结构

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

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

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

 2、栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小

2.1 top的指向

两种指向没什么区别,以下采取top指向栈顶数据的下一个位置 即 top指向待插入的位置

2.2 动态增长顺序栈

2.2.1 Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
2.2.2 Stack.c
#include "Stack.h"

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;
}

//动态申请
void Stackcapacity(Stack* ps)
{
	if (ps->_top == ps->_capacity)
	{
		ps->_capacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
		STDataType* tmp = (STDataType*)realloc(ps->_a, ps->_capacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("Stackcapacity()::realloc()");
			return;
		}
		ps->_a = tmp;
	}
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	Stackcapacity(ps);//动态申请
	ps->_a[ps->_top] = data;
	ps->_top++;
}

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	if (ps->_top == 0)
	{
		printf("栈已空\n");
		return;
	}
	ps->_top--;
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top != 0);
	return ps->_a[ps->_top - 1];
}

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->_top == 0)
		return 1;
	else
		return 0;
}

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;
}

2.3 链式堆栈

2.3.1 Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include "vld.h"

typedef int DataType;
typedef struct snode
{
	DataType data;
	struct snode* next;
}LSNode;

void StackInitiate(LSNode** head);//初始化

int StackNotEmpty(LSNode* head);//非空,返回1,否则返回0

void StackPush(LSNode* head, DataType x);//入栈

int StackPop(LSNode* head, DataType* x);//出栈,成功,返回1,否则,返回0

int StackTop(LSNode* head, DataType* x);//取栈顶元素,成功,返回1,否则,返回0

void Destroy(LSNode** head);//撤销栈
2.3.2 Stack.c
#include "LinStack.h"

void StackInitiate(LSNode** head)//初始化
{
	*head = (LSNode*)malloc(sizeof(LSNode));
	if (*head == NULL)
	{
		perror("StackInitiate():: malloc()");
		return;
	}
	(*head)->next = NULL;
}

int StackNotEmpty(LSNode* head)//非空,返回1,否则返回0
{
	if (head->next == NULL)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

void StackPush(LSNode* head, DataType x)//入栈 
{
	LSNode* s = (LSNode*)malloc(sizeof(LSNode));
	if (s == NULL)
	{
		perror("StackPush():: malloc()");
		return;
	}
	s->data = x;
	s->next = head->next;
	head->next = s;
}

int StackPop(LSNode* head, DataType* x)//出栈,成功,返回1,否则,返回0
{
	if (!StackNotEmpty(head))
	{
		printf("栈已空!\n");
		return 0;
	}
	else
	{
		LSNode* del = head->next;
		*x = del->data;
		head->next = head->next->next;
		free(del);
		del = NULL;
		return 1;
	}
}

int StackTop(LSNode* head, DataType* x)//取栈顶元素,成功,返回1,否则,返回0
{
	if (!StackNotEmpty(head))
	{
		printf("栈已空!\n");
		return 0;
	}
	else
	{
		*x = head->next->data;
		return 1;
	}
}

void Destroy(LSNode** head)//撤销栈
{
	/*LSNode* p = *head;
	LSNode* del;
	while( p != NULL)
	{
		del = p;
		p = p->next;
		free(del);
	}
	del = NULL;*/
	while (StackNotEmpty(*head))
	{
		LSNode* del = *head;
		*head = (*head)->next;
		free(del);
	}
	free(*head);
	*head = NULL;
}

队列

1、队列的概念及结构

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

入队列:进行插入操作的一端称为队尾

出队列:进行删除操作的一端称为队头

2、队列的实现

队列也可以数组链表的结构实现,使用链表的结构实现更优一些,因为在数组头上出数据效率比较低。

2.1 链式队列(rear初始化为NULL,之后指向队尾元素)

2.1.1 Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int QDataType;
// 链式结构:表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
2.1.2 Queue.c
#include "Queue.h"

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->_front = q->_rear = NULL;
	q->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	if (tmp == NULL)
	{
		perror("QueueNode()::malloc()");
		return;
	}
	tmp->_next = NULL;
	tmp->_data = data;
	if (q->size == 0)
	{
		q->_front = q->_rear = tmp;
	}
	else
	{
		q->_rear->_next = tmp;
		q->_rear = tmp;
	}
	q->size++;
}

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	if (q->size == 0)
	{
		printf("队列已空\n");
		return;
	}
	QNode* del = q->_front;
	q->_front = q->_front->_next;
	if (q->_front == NULL)
	{
		q->_rear = NULL;
	}
	free(del);
	del = NULL;
	q->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_front);
	return q->_front->_data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->_rear);
	return q->_rear->_data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	return q->size;
}

// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q)
{
	if (q->size == 0)
		return 1;
	else
		return 0;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	while (q->_front)
	{
		QNode* del = q->_front;
		q->_front = q->_front->_next;
		free(del);
	}
	q->_rear = NULL;
	q->size = 0;
}

2.2 顺序循环队列(rear初始化为0,指向待插入元素的位置)

2.2.1 Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define MaxQueueSize 6

typedef char DataType;
typedef struct
{
	DataType queue[MaxQueueSize];
	int front;
	int rear;
	int count;
}SeqCQueue,*pSeqCQueue;

void QueueInitiate(pSeqCQueue pmyQueue);//初始化队列

int QueueNotEmpty(SeqCQueue myQueue);//队列非空返回1,否则返回0

int QueueAppend(pSeqCQueue pmyQueue,DataType x);//入列,成功返回1,否则返回0

int QueueDelete(pSeqCQueue pmyQueue, DataType* x);//出列,成功返回1,否则返回0

int QueueGet(SeqCQueue myQueue, DataType* y);//取队头元素,成功返回1,否则返回0
2.2.2 Queue.c
#include "Queue.h"

void QueueInitiate(pSeqCQueue pmyQueue)//初始化队列
{
	pmyQueue->front = 0;
	pmyQueue->rear = 0;
	pmyQueue->count = 0;
}

int QueueNotEmpty(SeqCQueue myQueue)//队列非空返回1,否则返回0
{
	if (myQueue.count == 0)
		return 0;
	else
		return 1;
}

int QueueAppend(pSeqCQueue pmyQueue,DataType x)//入列,成功返回1,否则返回0
{
	if (pmyQueue->count == MaxQueueSize)
	{
		printf("队列已满!\n");
		return 0;
	}
	else
	{
		pmyQueue->queue[pmyQueue->rear] = x;
		pmyQueue->rear = (pmyQueue->rear + 1) % MaxQueueSize;
		pmyQueue->count++;
		return 1;
	}
}

int QueueDelete(pSeqCQueue pmyQueue, DataType* x)//出列,成功返回1,否则返回0
{
	if (!QueueNotEmpty(*pmyQueue))
	{
		printf("队列已空!\n");
		return 0;
	}
	else
	{
		*x = pmyQueue->queue[pmyQueue->front];
		pmyQueue->front = (pmyQueue->front + 1) % MaxQueueSize;
		pmyQueue->count--;
		return 1;
	}
}

int QueueGet(SeqCQueue myQueue, DataType* y)//取队头元素,成功返回1,否则返回0
{
	if (!QueueNotEmpty(myQueue))
	{
		printf("队列已空!\n");
		return 0;
	}
	else
	{
		*y = myQueue.queue[myQueue.front];
		return 1;
	}
}

Tips:

1、栈(一般实现顺序栈)

1.1 n个元素 依次进栈出栈的情况有多少种?

1.2 无论多简单都要写成一个函数,规范,不容易出错,如:stack.arr[top],不一定是栈顶元素,因为不知道top是哪种指向

1.3 在实现括号匹配时,注意  栈是后进先出 且可以边进边出,然后注意多种情况

2、队列(一般实现链式队列)

2.1 在实现循环队列时,注意  怎么循环(%)返回队尾元素小心越界


http://www.kler.cn/a/287908.html

相关文章:

  • 【Python · PyTorch】卷积神经网络(基础概念)
  • PostgreSQL物化视图详解
  • Python如何获取request response body
  • # ubuntu 安装的pycharm不能输入中文的解决方法
  • 嵌入式硬件电子电路设计(五)MOS管详解(NMOS、PMOS、三极管跟mos管的区别)
  • uniapp h5地址前端重定向跳转
  • 一 lua学习笔记:概述
  • 第L2周:机器学习-线性回归
  • Ubuntu系统本地搭建WordPress网站并一键发布内网站点至公网实战
  • 20-22 - 打造专业的编译环境
  • Language Models are Few-Shot Learners
  • 【计算机网络复习资料】
  • hello树先生——红黑树
  • go中的并发处理
  • 书生大模型实战营(1)——InterStudio基础知识+Vscode SSH连接远程服务器+Linux基础指令
  • 深度解析MFT损坏:原因、恢复策略与预防措施
  • 知道哪些键值型存储数据结构?这些数据结构的时间、空间复杂度分别是什么?什么时候选⽤?
  • 【C++】C++ 多态的底层实现
  • Python进阶04-网络编程
  • 和字符串有关的经典OJ题——字符串的逆置和字符串的翻转
  • 【TPAMI 2024】Occlusion-Aware Self-Supervised Monocular 6D Object Pose Estimation
  • 音视频解码 AVIO内存输入模式
  • nexus 清理 docker 镜像
  • rv1126-rv1109-mkcramfs-mkfs.cramfs-打包文件系统
  • 干货含源码!如何用Java后端操作Docker(命令行篇)
  • 基于STM32实现智能园艺系统