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

数据结构—队列和栈

ds 2025/8/10 14:20:08

1.二级指针的使用

二级指针：
1. 在被调函数中，想要修改主调函数中的指针变量，需要传递该指针变量的地址，形参用二级指针接收。
2.指针数组的数组名是一个二级指针，指针数组的数组名作为参数传递时，可用二级指针接收。
指针数组：保存多个指针的数组。
数组名：数组首元素地址。

2.内核链表

内核链表：双向循环链表
不再将数据存储在链表节点中，而是将结点嵌入到存储的数据中。
包含的宏：
offset_of : 获取内核链表中链表结点到结构体起始位置的偏移量。
container_of:通过偏移量，获取结构体的首地址（结点首地址-偏移量）。

3.栈

（1）基本概念

①系统栈

特点：先进后出: FILO

②数据结构的栈

栈：只允许从一端进行数据的插入和删除的线性存储结构，称之为栈结构
特点：先进后出: FILO

a.顺序栈

满增栈、满减栈、空增栈、空减栈
满栈、空栈：栈顶所在位置是否存在数据
增栈、减栈：按照栈的生长方向区分

b.链式栈

（2）基本操作

①创建一个栈

Stack_t *create_stack()
{Stack_t *pstack = malloc(sizeof(Stack_t));if(NULL == pstack){return NULL;}pstack->clen = 0;pstack->ptop = NULL;return pstack;
}

②判断一个栈是否为空

int is_empty_stack(Stack_t *pstack)
{return NULL == pstack->ptop;
}

③遍历

int stack_for_each(Stack_t *pstack)
{STNode_t *ptmp = pstack->ptop;if(NULL == pstack){return -1;}else{while(ptmp != NULL){printf("%d  ", ptmp->data);ptmp = ptmp->pnext;}puts("");}
}

④插入

int push_stack(Stack_t *pstack, Data_t data)
{STNode_t *ptmp = malloc(sizeof(STNode_t));if(NULL == ptmp){return -1;}ptmp->data = data;ptmp->pnext = NULL;ptmp->pnext = pstack->ptop;pstack->ptop = ptmp;pstack->clen++;return 1;
}

⑤删除

int pop_stack(Stack_t *pstack,Data_t *pdata)
{if(NULL == pstack){return -1;}STNode_t *ptmp = pstack->ptop;pstack->ptop = ptmp->pnext;if(pdata != NULL){*pdata = ptmp->data;}free(ptmp);pstack->clen--;return 0;}

⑥获取栈顶元素

int get_pop_stack(Stack_t *pstack, Data_t *pdata)
{if(NULL == pstack){return -1;}if(NULL == pdata){return -1;}*pdata = pstack->ptop->data;return 0;}

⑦销毁栈

void destroy_stack(Stack_t *pstack)
{if(is_empty_stack(pstack)){free(pstack);return ;}else{STNode_t *ptmp = pstack->ptop;STNode_t *p = NULL;while(ptmp->pnext != NULL){p =ptmp->pnext;free(ptmp);ptmp = p;}    free(ptmp);}free(pstack);
}

void stack_destory(Stack_t **pstack)
{while(!is_empty_stack(*pstack)){pop_stack(*pstack, NULL);}free(*pstack);*pstack = NULL;
}

4.队列

（1）基本概念

队列：允许从一端进行数据的插入，另一端进行数据删除的线性存储结构，称为队列结构
插入操作，叫入队操作，插入的这端称为队列的队尾；
删除操作，叫出队操作，删除的这端称为队列的队头。
特点：先进先出（FIFO）
应用：数据缓存

①链式队列

②顺序队列

循环队列
[head， tail)
循环队列为了区分队空和队满，将来少存储一个数据。
循环队列如何判空？--》队头和队尾处于同一位置，此时认为队列为空
循环队列如何判满？--》当队尾+1跟上队头时，任务认为队列为满

（2）基本操作

①链式队列

a.创建队列

LQueue_t *create_linkque()
{LQueue_t *plq = malloc(sizeof(LQueue_t));if(NULL == plq){return NULL;} plq->clen = 0;plq->phead = NULL;plq->ptail = NULL;return plq;
}

b.判空

int is_empty_linkque(LQueue_t *plq)
{return NULL == plq->phead;
}

c.遍历

void linkque_for_each(LQueue_t *plq)
{LQNode_t *ptmp = plq->phead;while(ptmp != NULL){printf("%d  ", ptmp->data);ptmp = ptmp->pnext;}puts("");
}

d.插入

int insert_linkque_tail(LQueue_t *plq, Data_type_t data)
{LQNode_t * ptmp = malloc(sizeof(LQNode_t));if(NULL == ptmp){return -1;}ptmp->data = data;ptmp->pnext = NULL;if(is_empty_linkque(plq)){plq->phead = ptmp;plq->ptail = ptmp;}else{plq->ptail->pnext = ptmp;plq->ptail = ptmp;} plq->clen++;return 1;
}

e.删除

int delete_linkque_head(LQueue_t *plq, Data_type_t *pdata)
{if(is_empty_linkque(plq)){return -1;}LQNode_t *ptmp = plq->phead;plq->phead = ptmp->pnext;if(pdata != NULL){*pdata = ptmp->data;}free(ptmp);if (NULL == plq->phead){plq->ptail = NULL;}plq->clen--;return 1;}

f.获取队头元素

int get_linkque_head(LQueue_t *plq)
{if(is_empty_linkque(plq)){return -1;}return plq->phead->data;
}

g.销毁队列

void destroy_linkque(LQueue_t **plq)
{while(!is_empty_linkque(*plq)){delete_linkque_head(*plq);}free(*plq);*plq = NULL;
}

②顺序队列---》循环队列

a.创建

Seqque_t *create_seqque()
{Seqque_t *psq = malloc(sizeof(Seqque_t));if (NULL == psq){printf("malloc error\n");return NULL;}psq->head = 0;psq->tail = 0;psq->pbase = malloc(sizeof(Data_type_t) * SEQQUE_MAX_LEN);if (NULL == psq->pbase){printf("malloc error\n");return NULL;}return psq;
}

b.判满

int is_full_seqque(Seqque_t *psq)
{if ((psq->tail+1)%SEQQUE_MAX_LEN == psq->head){return 1;}return 0;

c.判空

int is_empty_seqque(Seqque_t *psq)
{if (psq->head == psq->tail){return 1;}return 0;
}

d.入队

int push_seqque(Seqque_t *psq, Data_type_t data)
{if (is_full_seqque(psq)){printf("seqque is full\n");return -1;}psq->pbase[psq->tail] = data;psq->tail = (psq->tail+1) % SEQQUE_MAX_LEN;return 0;
}

e.遍历

void seqque_for_each(Seqque_t *psq)
{for (int i = psq->head; i < psq->tail; i = (i+1)%SEQQUE_MAX_LEN){printf("%d ", psq->pbase[i]);}printf("\n");
}

f.出队

int pop_seqque(Seqque_t *psq, Data_type_t *pdata)
{if(is_empty_seqque(psq) || NULL == pdata){return -1;}if(pdata != NULL){*pdata = psq->pbase[psq->head];psq->head = (psq->head + 1) % SEQQUE_MAX_LEN;}return 0;
}

g.获取队头元素

int top_seqque(Seqque_t *psq)
{if(is_empty_seqque(psq)){return -1;}return psq->pbase[psq->head];}

h.销毁队列

void destroy_seqque(Seqque_t *psq)
{free(psq->pbase);free(psq);
}

5.栈和队列的不同

1. 存取规则不同
队列：先进先出（FIFO, First In First Out）
先进入队列的元素先被取出（类似排队）。
栈：后进先出（LIFO, Last In First Out）
最后入栈的元素最先被取出（类似叠盘子）。
2. 操作接口不同
队列：
enqueue（入队）：在队尾添加元素。
dequeue（出队）：从队头移除元素。
栈：
push（入栈）：在栈顶添加元素。
pop（出栈）：从栈顶移除元素。