【C语言零基础入门篇 - 16】：栈和队列
栈和队列
栈
什么是栈：功能受限的线性数据结构
栈的特点：先进后出 。例如：仓库进货、出货。
栈只有一个开口，先进去的数据在栈底（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 4
list_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));
}
}
原文地址：https://blog.csdn.net/Oh_Python/article/details/142447875
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！