数据结构之栈和队列

1.简介链表、栈和队列都是一对一的线性结构栈和队列是一种特殊的表状结构栈只允许在栈顶位置入栈和出栈元素链表可以在任意位置插入和删除元素栈和队列只允许在指定位置插入和删除元素2.栈2.1概念先进后出后进先出栈顶允许入栈和出栈的一端称为栈顶栈底不允许入栈和出栈的一端称为栈底入栈 / 压栈将元素放入栈顶位置出栈 / 弹栈将栈顶元素取出栈针记录栈顶位置的标记2.2分类顺序栈增栈栈的方向自低地址向高地址增长减栈栈的方向自高地址向低地址减少空栈栈针指向要入栈的位置满栈栈针指向栈顶元素的位置常见的顺序栈空增栈空减栈 满增栈 满减栈链式栈使用链表的思想实现链式栈参考单向链表结点定义参考单向链表头插法压栈出栈返回链表第一个有效结点的值并删除该节点参考单向链表销毁销毁栈3.链式栈相关操作3.1定义数据类型typedef int Datatype_t;3.2定义结点类型typedef struct Snode { Datatype_t data; struct Snode* pnext; }Snode_t; typedef struct Stack { Snode_t* ptop; int clen; }Stack_t;3.3创建链式栈Stack_t* create_stacklink() { Stack_t* pstack malloc(sizeof(Stack_t)); if (NULL pstack) { printf(malloc error\n); return NULL; } pstack-ptop NULL; pstack-clen 0; return pstack; }3.4创建链式栈结点Snode_t* create_stacknode(Datatype_t data) { Snode_t* psnode malloc(sizeof(Snode_t)); if (NULL psnode) { printf(malloc error\n); return NULL; } psnode-data data; psnode-pnext NULL; return psnode; }3.5判断链式栈是否为空int is_empty_stacklink(Stack_t* pstack) { if (NULL pstack-ptop) { return 1; } return 0; }3.6栈操作入栈操作入栈操作相当于单向链表的头插操作int push_stacklink(Stack_t* pstack, Datatype_t data) { Snode_t* psnode create_stacknode(data); if (NULL psnode) { return -1; } if (is_empty_stacklink(pstack)) { pstack-ptop psnode; } else { psnode-pnext pstack-ptop; pstack-ptop psnode; } pstack-clen; return 0; }出栈操作出栈操作相当于单向链表的头删操作int pop_stacklink(Stack_t* pstack,Datatype_t* pdata) { if (is_empty_stacklink(pstack)) { return -1; } Snode_t* pfree pstack-ptop; pstack-ptop pfree-pnext; if(pdata!NULL) { *pdatapfree-data; } free(pfree); pstack-clen--; return 0; }3.7遍历链式栈int show_stacklink(Stack_t* pstack) { Snode_t* ptmp pstack-ptop; while (NULL ! ptmp) { printf(%d, ptmp-data); ptmp ptmp-pnext; } printf(\n); return 0; }3.8获取栈顶数据int get_top_stacklink(Stack_t* pstack,Datatype_t* pdata) { if(is_empty_stacklink(pstack)) { return -1; } if(pdata!NULL) { *pdatapstack-ptop-data; } return 0; }3.9删除链式栈void destroy_stack(Stack_t *pstack) { while (!is_empty_stacklink(pstack)) { pop_stacklink(pstack, NULL); } free(pstack); }4.队列4.1概念先进先出后进后出队头出队的一端队尾入队的一端入队将元素放入队列末尾出队将元素从队头中取出4.2链式队列相关操作4.2.1定义数据类型typedef int DataType_t;4.2.2定义结点类型typedef struct node { DataType_t data; struct node *pnext; } LQNode_t; typedef struct linkqueue { LQNode_t *phead; LQNode_t *ptail; int clen; } LQueue_t;4.2.3创建链式队列LQueue_t *create_linkqueue() { LQueue_t *pque malloc(sizeof(LQueue_t)); if (NULL pque) { printf(malloc error\n); return NULL; } pque-phead NULL; pque-ptail NULL; pque-clen 0; return pque; }4.2.4创建链式队列结点LQNode_t *create_node(DataType_t data) { LQNode_t *pnode malloc(sizeof(LQNode_t)); if (NULL pnode) { printf(malloc error\n); return NULL; } pnode-data data; pnode-pnext NULL; return pnode; }4.2.5判断链式队列是否为空int is_empty_linkqueue(LQueue_t *pque) { return NULL pque-phead; }4.2.6队列操作入队操作int push_linkqueue(LQueue_t *pque, DataType_t data) { LQNode_t *pnode create_node(data); if (NULL pnode) { return -1; } if (is_empty_linkqueue(pque)) { pque-phead pnode; pque-ptail pnode; } else { pque-ptail-pnext pnode; pque-ptail pnode; } pque-clen; return 0; }出队操作int pop_linkqueue(LQueue_t *pque, DataType_t *pdata) { if (is_empty_linkqueue(pque)) { return -1; } LQNode_t *ptmp pque-phead; pque-phead ptmp-pnext; if (NULL pque-phead) { pque-ptail NULL; } if (pdata ! NULL) { *pdata ptmp-data; } free(ptmp); pque-clen--; return 0; }4.2.7遍历链式队列void show_linkqueue(LQueue_t *pque) { LQNode_t *ptmp pque-phead; while (ptmp ! NULL) { printf(%d , ptmp-data); ptmp ptmp-pnext; } printf(\n); }4.2.8获取队列首元素int get_linkqueue_head(LQueue_t *pque, DataType_t *pdata) { if (is_empty_linkqueue(pque)) { return -1; } if (pdata ! NULL) { *pdata pque-phead-data; } return 0; }4.2.9销毁队列void destroy_linkqueue(LQueue_t **ppque) { while (!is_empty_linkqueue(*ppque)) { pop_linkqueue(*ppque, NULL); } free(*ppque); *ppque NULL; }4.3循环队列相关操作4.3.1定义数据类型typedef int DataType_t;4.3.2定义结点类型typedef struct sque { DataType_t* pbase; int head; int tail; }SQueue_t;4.3.3创建循环队列SQueue_t* create_sysqueue() { SQueue_t* psque malloc(sizeof(SQueue_t)); if (NULL psque) { printf(malloc error\n); return NULL; } psque-pbase malloc(sizeof(DataType_t) * MAX_QUEUE_LEN); if (NULL psque-pbase) { printf(malloc error\n); return NULL; } psque-head 0; psque-tail 0; return psque; }4.3.4判断队列状态判断队列是否为空int is_empty_sysqueue(SQueue_t* psque) { if(psque-head psque-tail) { return 1; } return 0; }判断队列是否为满int is_full_sysqueue(SQueue_t* psque) { if (((psque-tail 1) % MAX_QUEUE_LEN) psque-head) { return 1; } return 0; }4.3.5队列操作入队操作int push_sysqueue(SQueue_t* psque, DataType_t data) { if (is_full_sysqueue(psque)) { return -1; } psque-pbase[psque-tail] data; psque-tail (psque-tail 1) % MAX_QUEUE_LEN; return 0; }出队操作int pop_sysqueue(SQueue_t* psque,DataType_t* pdata) { if (is_empty_sysqueue(psque)) { return -1; } if(pdata!NULL) { *pdatapsque-pbase[psque-head]; } psque-head(psque-head 1)%MAX_QUEUE_LEN; return 0; }清除队列void clear_sysqueue(SQueue_t* psque) { psque-headpsque-tail0; }销毁队列void destroy_sysqueue(SQueue_t** ppsque) { free((*ppsque)-pbase); free(*ppsque); *ppsqueNULL; }4.3.6遍历循环队列int show_sysqueue(SQueue_t* psque) { if (is_empty_sysqueue(psque)) { return -1; } for(int ipsque-head;i!psque-tail;i(i1)%MAX_QUEUE_LEN) { printf(%d ,psque-pbase[i]); } printf(\n); return 0; }