用双链表实现的堆栈和队列

带哨兵元素，新节点添加到链表的头部。

头文件:

#ifndef STACK_H_ #define STACK_H_ #include "d_list.h" byte StackInit(List *plist,word length); // 堆栈初始化 byte StackPush(List *plist,Item item); // 压栈 byte StackPop(List *plist,Item *pitem); // 出栈 byte QueueInit(List *plist,word length); // 队列初始化 byte EnQueue(List *plist,Item item); // 入队列 byte DeQueue(List *plist,Item *pitem); // 出队列 #endif

源文件：

#include <stdio.h> #include <stdlib.h> #include "stack.h" /***************************************************************************/ // =================================================== // 判断堆栈是否为空 // 为空,返回1;不为空,返回0 // =================================================== static byte StackIsEmpty(List *plist) { if(plist->count == 0) return 1; else return 0; } // =================================================== // 判断堆栈是否为满 // 为满,返回1;不为满,返回0 // =================================================== static byte StackIsFull(List *plist) { if(plist->count == plist->max) return 1; else return 0; } /***************************************************************************/ // =================================================== // 堆栈初始化 // 建立一个带哨兵的空链表 // 失败,返回0;成功:返回1 // =================================================== byte StackInit(List *plist,word length) { struct node* pnew; pnew = (struct node *)malloc(sizeof(struct node)); if(pnew == 0) return 0; pnew->next = pnew; pnew->prev = pnew; plist->head = pnew; // 哨兵元素 plist->count = 0; plist->max = length; return 1; } // =================================================== // 压栈 // 将元素添加到链表头(哨兵元素之后) // 成功,返回1;失败,返回0 // =================================================== byte StackPush(List *plist,Item item) { struct node *pnew; if(StackIsFull(plist)) // 若栈满 return 0; pnew = (struct node*)malloc(sizeof(struct node)); if(pnew == 0) return 0; pnew->item = item; pnew->prev = plist->head; pnew->next = plist->head->next; plist->head->next->prev = pnew; plist->head->next = pnew; (plist->count)++; return 1; } // =================================================== // 出栈 // 失败,返回0;成功,返回1 // =================================================== byte StackPop(List *plist,Item *pitem) { struct node *pdel; if(StackIsEmpty(plist)) return 0; pdel = plist->head->next; *pitem = pdel->item; pdel->next->prev = plist->head; // 改变下一个节点的前向指针 plist->head->next = pdel->next; free(pdel); // 释放内存 (plist->count)--; return 1; } // =================================================== // 队列初始化 // =================================================== byte QueueInit(List *plist,word length) { return StackInit(plist,length); } // =================================================== // 添加元素到队首 // =================================================== byte EnQueue(List *plist,Item item) { return StackPush(plist,item); } // =================================================== // 从队尾删除元素 // =================================================== byte DeQueue(List *plist,Item *pitem) { static struct node *pdel; if(plist->count == 0) // 队列为空 return 0; pdel = plist->head->prev; // 队尾元素 *pitem = pdel->item; pdel->prev->next = plist->head; // 哨兵元素 plist->head->prev = pdel->prev; free(pdel); (plist->count)--; return 1; }