数据结构：栈和队列

目录

栈

顺序栈

结构体

创建

判断是否满栈

判断是否是空栈

入栈

出栈

遍历打印

销毁

链式栈

入栈：

出栈：

队列

链式队列

入队列：

出队列：

---

栈和队列

栈

栈：

  FILO
    先进后出，后进先出 （等同于水杯）
    栈顶：允许入栈出栈的一端称为栈顶
    栈底：不允许入栈和出栈的一端称为栈底
    入栈（压栈）：将数据元素放入栈顶
    出栈（弹栈）：将数据元素从栈顶位置取出

 分类:空增栈
          空减栈
          满增栈
          满减栈
 

顺序栈

结构体

typedef int DataType;
typedef struct stack
{DataType *data;int top;int tlen;
}SeqStack;

创建

SeqStack *CreateSeqStack(int Maxlen)
{//申请标签空间SeqStack *stack=NULL;stack=malloc(sizeof(SeqStack));if(stack==NULL){return NULL;}//为每个成员赋值stack->tlen=Maxlen;stack->top=0;//申请存放数据的空间stack->data = malloc( Maxlen *sizeof(DataType));if(stack->data==NULL){return NULL;}//返回标签地址return stack;
}

判断是否满栈

int IsFullSeqStack(SeqStack *pTmpStack)
{return pTmpStack->top==pTmpStack->tlen?1:0;
}

判断是否是空栈

int IsEmptySeqStack(SeqStack *pTmpStack)
{return pTmpStack->top==0?1:0;
}

入栈

在栈的top处添加新元素，top再++

int PushSeqStack(SeqStack *pTmpStack, DataType TmpData)
{if(IsFullSeqStack(pTmpStack)){return -1;}pTmpStack->data[pTmpStack->top]=TmpData;pTmpStack->top++;
}

出栈

每次是top-1处出栈

DataType PopSeqStack(SeqStack *pTmpStack)
{if(IsEmptySeqStack(pTmpStack)){return -1;}DataType pTmpdata= pTmpStack->data[pTmpStack->top-1];pTmpStack->top--;return pTmpdata;
}

遍历打印

int ForEachSeqStack(SeqStack *pTmpStack)
{int i=0;for(i=pTmpStack->top;i>0;i--){printf("%d  ",pTmpStack->data[pTmpStack->top-1]);pTmpStack->top--;}return 0;
}

销毁

int DestroySeqStack(SeqStack **ppTmpStack)
{free((*ppTmpStack)->data);free((*ppTmpStack));(*ppTmpStack)=NULL;
}

链式栈

入栈：

        直接使用头插法插入链表

出栈：

        每次都出（删除）第一个节点

#include  "list.h"
#include <stdio.h>
typedef struct data
{struct list_head node;int data;
}data_t;
int main()
{struct list_head pHead;struct list_head *pTmpNode=NULL;INIT_LIST_HEAD(&pHead);data_t d[5]={{{NULL,NULL},1},{{NULL,NULL},2},{{NULL,NULL},3},{{NULL,NULL},4},{{NULL,NULL},5},};//头插法插入链表for(int i=0;i<5;i++){list_add(&d[i].node,&pHead);}//链表不为空，第一个元素出栈while(!list_empty(&pHead)){pTmpNode=pHead.next;/*list_entry利用node偏移量获得整个节点的地址（pTmpNode的地址-node的偏移量）*/printf("%d ",list_entry(pTmpNode,data_t,node)->data);list_del(pTmpNode);}printf("\n");return 0;
}

队列

先入先出，后入后出（等同于排队）

链式队列

入队列：

        使用尾插法入队

出队列：

        每次出（删除）第一个节点 

#include "list.h"
#include <stdio.h>
typedef struct data
{struct list_head node;int data;
}data_t;
int main()
{struct list_head phead;struct list_head *pTmpNode=NULL;INIT_LIST_HEAD(&phead);data_t data[5]={{{NULL,NULL},1},{{NULL,NULL},2},{{NULL,NULL},3},{{NULL,NULL},4},{{NULL,NULL},5},};
//使用尾插法入队列for(int i=0;i<5;i++){list_add_tail(&data[i].node,&phead);}
//出队列每次都是第一个节点出while(!list_empty(&phead)){pTmpNode=phead.next;printf("%d  ",list_entry(pTmpNode,data_t,node)->data);list_del(pTmpNode);}printf("\n");return 0;}