数据结构——栈和队列

embedded/2025/1/16 11:12:26/

栈和队列

1.栈FILO

顺序栈：（空增栈）

链式栈

2.队列

栈和队列

栈和队列是特殊的表状结构
表可以在任意位置插入和删除
栈和队列只允许在固定位置插入和删除

1.栈FILO

先进后出，后进先出

栈顶：允许入栈出栈的一端称为栈顶
栈底：不允许入栈和出栈的一端称为栈底
入栈（压栈）：将数据元素放入栈顶
出栈（弹栈）：将数据元素从栈顶位置取出

顺序栈：（空增栈）

结构体定义：

//存放数据的类型
typedef int DataType;//标签类型
typedef struct stack 
{DataType *pData;int Top;int tLen;
}SeqStack

SeqStack *CreateSeqStack(int MaxLen)
{SeqStack *pTmpStack = NULL;//1.申请标签空间pTmpStack = malloc(sizeof(SeqStack));if (NULL == pTmpStack){return NULL;}//2.对每个成员赋初值pTmpStack->tLen = MaxLen;pTmpStack->Top = 0;pTmpStack->pData = malloc(MaxLen * sizeof(DataType));if (NULL == pTmpStack->pData){return NULL;}//3.申请存放数据的空间//4.返回标签地址 return pTmpStack;
}int IsFullSeqStack(SeqStack *pTmpStack)
{return pTmpStack->tLen == pTmpStack->Top ? 1 : 0;
}int IsEmptySeqStack(SeqStack *pTmpStack)
{return 0 == pTmpStack->Top ? 1 : 0;
}int PushSeqStack(SeqStack *pTmpStack, DataType TmpData)
{if (IsFullSeqStack(pTmpStack)){return -1;}pTmpStack->pData[pTmpStack->Top] = TmpData;pTmpStack->Top++;return 0;
}DataType PopSeqStack(SeqStack *pTmpStack)
{if (IsEmptySeqStack(pTmpStack)){return -1;}pTmpStack->Top--;return pTmpStack->pData[pTmpStack->Top];
}int DestroySeqStack(SeqStack **ppTmpStack)
{free((*ppTmpStack)->pData);free(*ppTmpStack);*ppTmpStack = NULL;return 0;
}

链式栈

可以使用内核链表实现

步骤：1.使用头插法，插入到链表中（入栈）

2.每次删除，始终删头结点指向的下一个节点next;（出栈）

#include "list.h"
#include <stdio.h>typedef struct data 
{struct list_head node;int data;
}data_t;int main(void)
{struct list_head *ptmpnode = NULL;data_t d[5] = {{{NULL, NULL}, 1},{{NULL, NULL}, 2},{{NULL, NULL}, 3},{{NULL, NULL}, 4},{{NULL, NULL}, 5},};int i = 0;//定义链表空节点，并初始化struct list_head head;INIT_LIST_HEAD(&head);//将5个数据头插法插入链表中for (i = 0; i < 5; i++){list_add(&d[i].node, &head);}//只要链表不为空将第一个节点出栈while (!list_empty(&head)){   ptmpnode = head.next;printf("%d ", list_entry(ptmpnode, data_t, node)->data);list_del(head.next);}printf("\n");return 0;
}