1. Toy模板网首页
  2. > Toy博客

爱上数据结构：栈和队列的概念及使用

7月前 作者：guoguoqiang. 分类：Toy博客 阅读(30) 违法举报

这篇具有很好参考价值的文章主要介绍了爱上数据结构：栈和队列的概念及使用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

​

​
爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构

🔥个人主页：guoguoqiang. 🔥专栏：数据结构

爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构

​

一、栈

1.栈的基本概念

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

栈是后进先出 可以想象为肉串，先串进去的肉最后才能吃到，而后串进去的肉在刚开始就能吃到

爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构
​

2.栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的
代价比较小。
爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构
爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
STDataType _a[N];
int _top; // 栈顶
}Stack;
// 支持动态增长的栈
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);

Stack.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int STDataType;
typedef struct Stack {
	STDataType* a;
	int top;
	int capacity;
}ST;
void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
STDataType STTop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);

Stack.c
#include "Stack.h"
void STInit(ST* ps) {
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void STDestroy(ST* ps) {
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x) {
	assert(ps);
	if (ps->top == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps) {
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}
STDataType STTop(ST* ps) {
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}
int STSize(ST* ps) {
	assert(ps);
	return ps->top;
}
bool STEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}

Test.c
#include "Stack.h"
int main() {
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);
	while (!STEmpty(&s)) {
		int top = STTop(&s);
		printf("%d ", top);
		STPop(&s);
	}
	STDestroy(&s);
	return 0;
}

爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构

二、队列

1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构

队列在我们生活中有很多例子，比如在电影院排队的时候，就是先排队的先买票，后来的后买票。
比如在排火车票的时候，正在排队时，突然有个美女要插队到你前头并说：“着急回家看生病的老人”（并且泪眼迷离），我一个于心不忍就往后退了一个位置，并且让后面的人都退一个位置。后面传来了一阵谩骂…
直到后来有个壮汉冲过来追向这个美女说：“骗了我的钱就想走啊！！”然后追着都走出了队伍，后面的人这才恢复了秩序。

2.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数
组头上出数据，效率会比较低。
爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构

// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}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);

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

typedef int QDataType;
typedef struct QueueNode
{
	int val;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

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

// 入队列
void QueuePush(Queue* pq, QDataType x);
// 出队列
void QueuePop(Queue* pq);

QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);


Queue.c
#include"Queue.h"

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

	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

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

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);

		cur = next;
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

// 入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->val = x;
	newnode->next = NULL;

	if (pq->ptail)
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	else
	{
		pq->phead = pq->ptail = newnode;
	}

	pq->size++;
}

// 出队列
void QueuePop(Queue* pq)
{
	assert(pq);

	// 0个节点
	// 温柔检查
	//if (pq->phead == NULL)
	//	return;

	// 暴力检查 
	assert(pq->phead != NULL);

	// 一个节点
	// 多个节点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}

	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);

	// 暴力检查 
	assert(pq->phead != NULL);

	return pq->phead->val;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);

	// 暴力检查 
	assert(pq->ptail != NULL);

	return pq->ptail->val;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

test.c
#include"Queue.h"

int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);

	printf("%d ", QueueFront(&q));
	QueuePop(&q);

	QueuePush(&q, 3);
	QueuePush(&q, 4);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}

	QueueDestroy(&q);

	return 0;
}

爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构
可以看出就算提前输出也不会影响排队的顺序。队列是先进先出的。
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构
爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构

如果Q->front==Q->rear 则该循环队列为空
如果(Q->rear+1)%(Q->k+1)=Q->front 则该队列满了

设计循环队列
爱上数据结构：栈和队列的概念及使用,数据结构C语言版,数据结构




typedef struct {
    int *a;
    int front;
    int rear;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    int *a=(int *)malloc(sizeof(int)*(k+1));
    obj->a=a;
    obj->front=0;
    obj->rear=0;
    obj->k=k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->k+1)==obj->front;
}

//enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear] = value;
    obj->rear = (obj->rear + 1) % (obj->k + 1);
    return true;
}


bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return false;
    }
    obj->front++;
    obj->front%=(obj->k+1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    else
        return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    else{
        return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
    }
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

感谢大家观看！！！文章来源地址https://www.toymoban.com/news/detail-853685.html

到了这里，关于爱上数据结构：栈和队列的概念及使用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构：栈的概念及栈的实现

    数据结构：栈的概念及栈的实现

    目录 1.栈的概念及结构 2.栈的实现  2.1  初始化栈 2.2 入栈  2.3 出栈  2.4 获取栈顶元素 2.5 获取栈中有效元素个数   2.6  检测栈是否为空，如果为空返回非零结果，如果不为空返回0 2.7 销毁栈  3. 完整代码 test.c  Stack.h Stack.c   栈（后进先出，先进后出） ： 一种 特殊

    2024年02月01日
    浏览(41)
  • 数据结构 栈的概念及栈的实现

    数据结构 栈的概念及栈的实现

    目录 1.栈的概念及结构 2.栈的实现  2.1  初始化栈 2.2 入栈  2.3 出栈  2.4 获取栈顶元素 2.5 获取栈中有效元素个数   2.6  检测栈是否为空，如果为空返回非零结果，如果不为空返回0 2.7 销毁栈  3. 完整代码 test.c  Stack.h Stack.c   栈（后进先出，先进后出） ： 一种 特殊

    2024年01月21日
    浏览(48)
  • 数据结构从入门到精通——排序的概念及运用

    数据结构从入门到精通——排序的概念及运用

    排序是将数据按照一定规则重新排列的过程，常见规则有升序、降序等。排序算法如冒泡排序、快速排序等，广泛用于数据库、搜索引擎等场景，提高数据检索效率。此外，排序也应用于统计分析、机器学习等领域，以获取有序数据集或发现数据间的关联。 排序是一种将一组

    2024年03月21日
    浏览(40)
  • 数据结构 | 二叉树的概念及前中后序遍历

    数据结构 | 二叉树的概念及前中后序遍历

    下面内容来自百度百科 二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能

    2024年02月05日
    浏览(37)
  • 数据结构入门（C语言版）二叉树的顺序结构及堆的概念及结构实现应用

    数据结构入门（C语言版）二叉树的顺序结构及堆的概念及结构实现应用

    普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用 顺序结构的数组来存储 ，需要注意的是 这里的堆和操作系统虚拟进程地址空间中的堆是两回事 ，一个是 数据结构 ，一

    2023年04月19日
    浏览(52)
  • 一起学数据结构（3）——万字解析：链表的概念及单链表的实现

    一起学数据结构（3）——万字解析：链表的概念及单链表的实现

    上篇文章介绍了数据结构的一些基本概念，以及顺序表的概念和实现，本文来介绍链表的概念和单链表的实现，在此之前，首先来回顾以下顺序表的特点： 1. 顺序表是一组地址连续的存储单元依次存储的线性表的数据结构，逻辑上：顺序表中相邻的数据元素，其物理次序也是

    2024年02月13日
    浏览(54)
  • 【数据结构】手撕排序(排序的概念及意义、直接插入和希尔排序的实现及分析)

    【数据结构】手撕排序(排序的概念及意义、直接插入和希尔排序的实现及分析)

    目录 一、排序的概念及其运用  1.1排序的概念  1.2排序运用 1.3 常见的排序算法  二、插入排序 2.1基本思想：  2.2直接插入排序：  2.3步骤： 2.4直接插入排序的实现 三、希尔排序( 缩小增量排序 )  3.1希尔排序的发展历史 3.2 希尔排序的思路 ​编辑 gap = 3的思路讲解 3.3 如何

    2024年02月03日
    浏览(48)
  • 【数据结构】栈和队列(队列篇）

    【数据结构】栈和队列(队列篇）

    上期我们已经学习了数据结构中的栈，这期我们开始学习队列。 目录 1.队列的概念及结构 2.队列的实现 队列结构体定义 常用接口函数 初始化队列 队尾入队列 队头出队列 获取队列头部元素、 获取队列队尾元素 获取队列中有效元素个数 检测队列是否为空 销毁队列 3.循环队

    2024年02月13日
    浏览(42)
  • 数据结构（C语言实现）——二叉树的概念及二叉树顺序结构和链式结构的实现（堆排序+TOP-K问题+链式二叉树相关操作）

    数据结构（C语言实现）——二叉树的概念及二叉树顺序结构和链式结构的实现（堆排序+TOP-K问题+链式二叉树相关操作）

    前面学习了数据结构中线性结构的几种结构，顺序表，链表，栈和队列等，今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点，所以本文着重介绍二叉树的相关概念和性质，以及二叉树的应用。 树是一种非线性的数据结构，它是由n（

    2023年04月21日
    浏览(45)
  • 栈和队列【数据结构】

    栈和队列【数据结构】

    2024年02月16日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包