首页 > 其他分享 >栈和队列（一）

栈和队列（一）

时间：2024-10-29 18:18:37浏览次数：6  
标签：ps para 队列 Queue queue assert

目录

一、栈（后入先出）

1、概念和结构

2、栈的实现（顺序表）

主程序（test.c）　

头文件（stack.h）

调用函数（stack.c）

二、队列（先入先出）

1、队列的概念及结构

2、队列的实现

主程序（test.c）

头文件（queue.h）

调用函数（queue.c）

一、栈（后入先出）

1、概念和结构

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除数据

  • 栈顶：进行数据插入和删除操作的一端
  • 栈底：另外一端
  • 压栈：栈的插入叫做进栈/压栈/入栈，入数据在栈顶
  • 出栈：栈的删除操作叫做出栈，出数据也在栈顶

2、栈的实现（顺序表）

栈用数组实现比较好

  • 主程序（test.c）　

#define _CRT_SECURE_NO_WARNINGS 1

#include "Stack.h"

int main()
{
	ST stack;

	//栈初始化
	STInit(&stack);


	//入栈
	STpush(&stack, 4);
	STpush(&stack, 3);
	STpush(&stack, 2);
	//出栈
	STpop(&stack);
	STpush(&stack, 1);
	STpop(&stack);
	STpop(&stack);

	//栈中数据的个数 
	STsize(&stack);

	//查询栈顶元素
	printf("栈顶的元素为->%d\n", STTop(&stack));

	return 0;
}

  • 头文件（stack.h）

#define _CRT_SECURE_NO_WARNINGS 1

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

typedef int STDatatype;
typedef struct Stack
{
	int* a;
	int top;//top =0 指向栈顶元素下一个元素位置，top=-1指向栈顶
	int capacity;
}ST;

//栈初始化
void STInit(ST* para);
//销毁栈
void STdestroy(ST* para);
//入栈
void STpush(ST* para, STDatatype x);
//出栈
void STpop(ST* para);
//栈中数据的个数
void STsize(ST* para);
//判断栈是否为空
bool STempty(ST* para);
//查询栈顶元素
STDatatype STTop(ST* para);

  • 调用函数（stack.c）

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"

//栈初始化
void STInit(ST* para)
{
	assert(para);

	para->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	para->capacity = 4;
	para->top = -1;
}

//销毁栈
void STdestroy(ST* para)
{
	assert(para);
	free(para->a);
	para->capacity = 0;
	para->top = -1;
}

//入栈
void STpush(ST* para, STDatatype x)
{
	assert(para);
	if (para->top == para->capacity)
	{
		para->capacity = para->capacity * 2;
		int* new = (STDatatype*)realloc(para->a ,sizeof(STDatatype) * (para->capacity));
		if (new == NULL)
		{
			perror("malloc:");
			return NULL;
		}
		para->a = new;
	}
	para->top++;
	para->a [para->top ] = x;
}

//出栈
void STpop(ST* para)
{
	assert(para);
	assert(!STempty(para));

	printf("%d ", para->a[para->top]);
	para->top--;
}

//栈中数据的剩余个数
void STsize(ST* para)
{
	assert(para);
	printf("\n栈中还有%d个数据 \n", para->top + 1);
}

//判断栈是否为空
bool STempty(ST* para)
{
	assert(para);

	return para->top == -1;
}

//栈顶元素
STDatatype STTop(ST* para)
{
	assert(para);
	assert(!STempty(para));

	return para->a[para->top];
}

二、队列（先入先出）

1、队列的概念及结构

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

  • 入队列：进行插入操作的一端称为“队尾”
  • 出队列：进行删除操作的一端称为“队头”

2、队列的实现

单链表比较适合实现队列，定义头指针和尾指针

  • 主程序（test.c）

#define _CRT_SECURE_NO_WARNINGS 1
#include "queue.h"

void Print(Queue* ps)
{
	printf("队头数据为->%d\n", QueueFront(ps));
	printf("队尾数据为->%d\n", QueueBack(ps));
}
int main()
{
	//创建队列
	Queue queue;

	//初始化
	QueueInit(&queue);

	//入队列
	Queuepush(&queue, 1);
	Queuepush(&queue, 2);
	Queuepush(&queue, 3);
	Queuepush(&queue, 4);
	Print(&queue);

	//出队列
	Queuepop(&queue);
	//查看队列中的元素个数
	int n = Queuesize(&queue);
	printf("%d\n", n);
	Print(&queue);

	Queuepush(&queue, 5);
	n = Queuesize(&queue);
	printf("%d\n", n);
	Print(&queue);

	//销毁队列
	QueueDestroy(&queue);
	return 0;
}

  • 头文件（queue.h）

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef int QDataType;
typedef struct Queuenode
{
	QDataType a;
	struct Queuenode* next;
}Qnode;

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

//初始化队列
void QueueInit(Queue* ps);
//销毁队列
void QueueDestroy(Queue* ps);
//入队列
void Queuepush(Queue* ps, QDataType x);
//出队列
void Queuepop(Queue* ps);
//查看队列中的元素个数
int Queuesize(Queue* ps);
//判断队列是否为空
bool QueueEmpty(Queue* ps);
//查看队首
QDataType QueueFront(Queue* ps);
//查看队尾
QDataType QueueBack(Queue* ps);

  • 调用函数（queue.c）

#define _CRT_SECURE_NO_WARNINGS 1
#include "queue.h"

//创建新节点
Qnode* Creatnode(QDataType x)
{
	Qnode* node = (Qnode*)malloc(sizeof(Qnode));
	if (node == NULL)
	{
		perror("malloc:");
		return NULL;
	}
	node->a = x;
	node->next = NULL;
	return node;
}

//初始化
void QueueInit(Queue* ps)
{
	assert(ps);

	ps->head = NULL;
	ps->size = 0;
	ps->tail = NULL;
}

//判断队列是否为空
bool QueueEmpty(Queue* ps)
{
	assert(ps);

	return ps->size == 0;
}

//销毁队列
void QueueDestroy(Queue* ps)
{
	assert(ps);
	Qnode* cur = ps->head;
	while (cur)
	{
		Qnode* next = cur->next;
		free(cur);
		cur = next;
	}

	ps->head = ps->tail = NULL;
	ps->size = 0;
}

//入队列
void Queuepush(Queue* ps, QDataType x)
{
	assert(ps);

	Qnode* newnode = Creatnode(x);
	if (ps->head == NULL)
	{
		ps->head = ps->tail = newnode;
	}
	else
	{
		ps->tail->next = newnode;
		ps->tail = newnode;
	}
	ps->size++;
}

//出队列
void Queuepop(Queue* ps)
{
	assert(ps);
	//断言看ps里面是否有数据，非空执行，空的话报错
	assert(!QueueEmpty(ps));

	if (ps->head == ps->tail)
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
		ps->size--;
	}
	else
	{
		Qnode* cur = ps->head;
		ps->head = ps->head->next;
		free(cur);
		cur = NULL;
		ps->size--;
	}
}
//查看队列中的元素个数
int Queuesize(Queue* ps)
{
	assert(ps);

	return ps->size;
}

//查看队首
QDataType QueueFront(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->a;
}
//查看队尾
QDataType QueueBack(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->tail->a;
}

标签：ps,para,队列,Queue,queue,assert
From： https://blog.csdn.net/Xiaodao12345djs/article/details/143293086

相关文章

  • 队列与树 数据结构复习笔记
    2.3队列队列(Queue)，它是一种运算受限的线性表,先进先出(FIFOFirstInFirstOut)队列是一种受限的线性结构受限之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作Python标准库中的queue模块提供了多种队列实现，包括普通队列、双端队列、优先队......
  • c语言-数组队列-学习笔记
    数组队列#include<stdio.h>#include<stdlib.h>/*数组顺序队列*/typedefstructSqQueue{ intdata[10]; intfront; intrear;}SqQueue;voidInitQueue(SqQueue*Q){ Q->front=Q->rear=0;}voidEnQueue(SqQueue*Q,inta){ Q->data[Q->rear......
  • 代码随想录-栈与队列6、7
    逆波兰表达式思路用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中这里记录string类型相关操作：判断token是否是数字，不可像char类型用string重载的>=,<=，前者由于用ASCII码表示，后者按字典序比较，例如1<2所以字符串比较"10"<"2"。所以直接......
  • 队列的实现方式
    目录使用数组实现的队列（固定大小）使用链表实现的队列使用Java标准库中的LinkedListJava中队列（Queue）可以通过多种方式实现，包括使用数组、链表以及Java标准库中的Queue接口及其实现类（如LinkedList、PriorityQueue等）。使用数组实现的队列（固定大小）虽然Java标准库中并没有直......
  • 手撸优先队列——二叉堆
    在数据结构中，队列可以对应我们生活中的排队现象，像买早点排队，上公共汽车排队等。但是有一些情况，我们要优先某些元素，比如：上公共汽车时，虽然在排队，还是要优先老幼病残孕先上车；当有多个电脑向打印机发送打印请求时，一台电脑要打印100页，而其他电脑都是单页打印，此时更合理的做法时，优先打印......
  • 栈和队列(上)-栈
    1.栈的概念    引入:        我们平时拿羽毛球,是从盒子顶部的羽毛球开始拿的,而顶部的元素是我们最后放进去的.    栈:一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈......
  • Java 中的 队列（Queue）与双端队列（Deque）
    这篇笔记期初是因为在刷算法题的过程中，发现其他解题方法很多地方有采用栈或者队列来解题，我在这方面比较薄弱，特此学习记录一下。关于队列，我的初始印象就是先进先出，但是通过学习，了解到队列还有双端队列（Deque）、优先队列（PriorityQueue）等类型，不同的队列有不同的进出规则。 队列（Qu......
  • 重生之“我打数据结构，真的假的？”--3.栈和队列（无习题）
    栈和队列C语言中的栈和队列总结在C语言中，**栈（Stack）和队列（Queue）**是两种非常重要的数据结构。它们广泛用于各种应用中，比如内存管理、任务调度、表达式求值等。本文将对这两种数据结构进行详细的介绍，并展示如何在C语言中实现它们。1.栈（Stack）栈是一种先进后出（LIFO，LastIn......
  • 栈与队列（概念与实现）
    目录前言一，栈1，栈（Stack）2，栈的实现3，栈的用途二，队列1，队列（Queue）2，队列的实现3，队列的用途4，环形队列5，环形队列的用途前言     栈与队列，作为核心的数据结构，对于每一位程序员来说都至关重要。它们简化了问题解决的过程，提升了代码的效率。    在这篇博客中，......
  • 数据结构之队列
    一、队列的定义队列是一种操作受限的线性表，队列只允许在表的一端进行插入，在表的另一端进行删除。可进行插入的一段称为队尾，可进行删除的一端称为队头。队列的主要特点就是先进先出。依照存储结构可分为：顺序队和链式队。二、顺序队列一开始front(队头)和rear(队尾)都在数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99