当前位置：首页 > news >正文

【C语言零基础入门篇 - 16】：栈和队列

news 来源：原创 2024/9/23 7:55:37

文章目录

栈和队列
- 栈
- - 栈功能的实现
  - 源代码
- 队列
- - 队列功能的实现
  - 源代码

栈和队列

栈

什么是栈：功能受限的线性数据结构

栈的特点：先进后出。例如：仓库进货、出货。

栈只有一个开口，先进去的数据在栈底（bottom），后进来的元素在栈顶(top)。栈结构的数据操作只在栈顶。

栈的结构示意图：
在这里插入图片描述

栈功能的实现

栈的基本操作：增、删、改、查。
栈中数据的插入和删除结构示意图：
在这里插入图片描述

源代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct STACK
{int top; //栈顶元素下标int maxSize; //栈的最大容量int*data; //数据域 data作为指针，管理动态数组
}ST;//初始化栈结构
ST*init_stack()
{ST*temp = (ST*)malloc(sizeof(ST));//栈结构成员的初始化temp->top = -1;// 栈中没有元素temp->maxSize = 0;temp->data = NULL;return temp;
}void stack_push(ST*st, int data) //data表示要入栈的元素
{if (st->maxSize == 0)//之前没有内存{st->maxSize = 10;//设置当前的最大容量st->data = (int*)malloc(sizeof(int)*(st->maxSize));}//元素增加，栈顶元素下标+1(st->data)[++st->top] = data;
}//出栈 元素值返回
int stack_pop(ST*st) //st=stack
{if (st->top < 0) //如果栈是空的{printf("栈空，出栈操作失败\n");assert(NULL); //断言 报错}return st->data[st->top--];
}
int main()
{ST*stack = init_stack(); //stack指向栈结构//1 2 3 入栈stack_push(stack, 1);printf("%d\t", stack_pop(stack));stack_push(stack, 2);printf("%d\t", stack_pop(stack));stack_push(stack, 3);printf("%d\t", stack_pop(stack));return 0;
}

队列

什么是队列：功能受限的线性数据结构

队列的特点：先进先出 。例如：排队打疫苗。

队列有队首(front)和队尾(back)，队首（front）指向队列的第一个数据，队尾（back）指向队列中的最后一个数据。数据从队尾入队，从队首出队。

队列的结构示意图：
在这里插入图片描述

队列功能的实现

队列的基本操作：增、删、改、查。

队列中数据的插入和删除结构示意图：
在这里插入图片描述

源代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>#define TYPE int//单链表结点
typedef struct Node
{TYPE data; //数据域struct Node*next; //指针域 保存下一个结点的地址
}node;//队列结构
typedef struct LinkList
{node*front; //队首指针node*back; //队尾指针
}LIST;//建立队列结构，初始化成员
LIST*list_init()
{LIST*temp = (LIST*)malloc(sizeof(LIST));temp->front = temp->back = NULL;return temp;
}//创建单链表 - 新结点
node*createNode(TYPE val)//val表示要增加的新数据
{node*temp = (node*)malloc(sizeof(node));temp->data = val;temp->next = NULL;return temp;
}//入队
void list_push(LIST*list, TYPE val)
{//1、入队的元素是第一个  需要更新队首和队尾指针if (list->front == NULL){list->front = list->back = createNode(val);}//2、入队的元素不是第一个 需要更新队尾指针else{list->back->next = createNode(val);//让新节点成为队尾，也就是让队尾指向新结点list->back = list->back->next;}
}//出队
TYPE list_pop(LIST*list)
{//队列结构是否存在assert(list);//队列是否有单链表结点assert(list->front);//1、找到要出队的元素值node*temp = list->front;TYPE val = temp->data; //出队之前，需要把元素保存下来//2、更新队首指针的指向list->front = temp->next;//3、释放要出队的结点free(temp);return val;
}int main()
{LIST*LL = list_init();//入队 1 2 3 4list_push(LL, 1);list_push(LL, 2);list_push(LL, 3);list_push(LL, 4);//出队for (int j = 1; j < 4; j++){printf("%d\t", list_pop(LL));}
}