其他概念详情参看前一篇博文：栈的顺序存储 - 设计与实现 - API实现

这里也是运用了链表的链式存储API快速实现了栈的API。

代码：

// linkstack.h // 链式存储栈的API声明 #ifndef _MY_LINKSTACK_H_ #define _MY_LINKSTACK_H_ typedef void LinkStack; // 创建栈 LinkStack* LinkStack_Create(); // 销毁栈 void LinkStack_Destroy(LinkStack* stack); // 清空栈 void LinkStack_Clear(LinkStack* stack); // 将item入栈 int LinkStack_Push(LinkStack* stack, void* item); // 弹出栈顶元素 void* LinkStack_Pop(LinkStack* stack); // 获取栈顶元素 void* LinkStack_Top(LinkStack* stack); // 获取栈的大小 int LinkStack_Size(LinkStack* stack); #endif //_MY_LINKSTACK_H_
// linkstack.cpp // 链式存储栈的API实现 #include <stdio.h> #include <malloc.h> #include "linkstack.h" #include "linklist.h" typedef void LinkStack; typedef struct _tag_LinkStack { LinkListNode node; void* item; }TLinkStack; // 创建一个栈，相当于创建一个线性表 LinkStack* LinkStack_Create() { return LinkList_Create(); } // 销毁栈 void LinkStack_Destroy(LinkStack* stack) { LinkStack_Clear(stack); // 释放栈的结点 LinkList_Destroy(stack); // 释放句柄 return; } // 清空栈 void LinkStack_Clear(LinkStack* stack) { while (LinkList_Length(stack)) { LinkStack_Pop(stack); } return; } // 向栈中添加元素，相当于用头插法向线性表添加结点 int LinkStack_Push(LinkStack* stack, void* item) { int ret = 0; TLinkStack *tStack = NULL; // 把void* item转化成链表结点 tStack = (TLinkStack *)malloc(sizeof(TLinkStack)); tStack->item = item; // 头插法插入结点 ret = LinkList_Insert(stack, (LinkListNode *)tStack, 0); if (ret) { printf("function LinkStack_Push err: %d.\n", ret); free(tStack); return ret; } return ret; } // 弹出栈顶元素，相当于从线性表中删除0号元素 void* LinkStack_Pop(LinkStack* stack) { TLinkStack *tStack = NULL; void* item = NULL; tStack = (TLinkStack *)LinkList_Delete(stack, 0); if (tStack == NULL) { printf("function LinkStack_Pop err.\n"); return NULL; } // 把链表结点转化成栈结点 item = tStack->item; free(tStack); // 记得释放创建时候malloc的内存 return item; } // 获取栈顶元素 void* LinkStack_Top(LinkStack* stack) { TLinkStack *tStack = NULL; void* item = NULL; tStack = (TLinkStack *)LinkList_Get(stack, 0); if (tStack == NULL) { printf("function LinkStack_Top err.\n"); return NULL; } item = tStack->item; return item; } // 获取栈的大小 int LinkStack_Size(LinkStack* stack) { return LinkList_Length(stack); }
// main.cpp // 栈链式存储的测试程序 #include <stdio.h> #include "linkstack.h" const int maxn = 5; void play() { int a[maxn]; for (int i = 0; i < maxn; ++i) { a[i] = i + 1; } LinkStack *stack = NULL; stack = LinkStack_Create(); // 创建栈 // 入栈 for (int i = 0; i < maxn; ++i) { LinkStack_Push(stack, &a[i]); } // 栈属性 printf("size: %d\n", LinkStack_Size(stack)); printf("top: %d\n", *((int *)LinkStack_Top(stack))); LinkStack_Destroy(stack); } int main() { play(); return 0; }
// linklist.h #ifndef _MYLINKLIST_H_ #define _MYLINKLIST_H_ typedef void LinkList; typedef struct _tag_LinkListNode { struct _tag_LinkListNode* next; }LinkListNode; LinkList* LinkList_Create(); void LinkList_Destroy(LinkList* list); void LinkList_Clear(LinkList* list); int LinkList_Length(LinkList* list); int LinkList_Insert(LinkList* list, LinkListNode* node, int pos); LinkListNode* LinkList_Get(LinkList* list, int pos); LinkListNode* LinkList_Delete(LinkList* list, int pos); #endif
// linklist.cpp #include <iostream> #include <cstdio> #include "linklist.h" using namespace std; typedef void LinkList; typedef struct _tag_LinkList { LinkListNode header; int length; }TLinkList; LinkList* LinkList_Create() { TLinkList *tmp = NULL; tmp = (TLinkList *)malloc(sizeof(TLinkList)); if (tmp == NULL) { printf("function LinkList_Create() err.\n"); return NULL; } memset(tmp, 0, sizeof(TLinkList)); // 初始化为空链表 return tmp; } void LinkList_Destroy(LinkList* list) { if (list == NULL) { return; } free(list); return; } void LinkList_Clear(LinkList* list) { if (list == NULL) { return; } TLinkList *tList = NULL; tList = (TLinkList *)list; tList->header.next = NULL; tList->length = 0; return; } int LinkList_Length(LinkList* list) { if (list == NULL) { return -1; } TLinkList *tList = NULL; tList = (TLinkList *)list; return tList->length; } int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) { if (list == NULL || node == NULL || pos < 0) { return -1; } TLinkList *tList = NULL; tList = (TLinkList *)list; LinkListNode *cur = NULL; cur = &(tList->header); // 对pos的容错处理，如果pos过大，，改为最后面 if (pos > LinkList_Length(list)) { pos = LinkList_Length(list); } // 移动到需要插入的位置 for (int i = 0; i < pos; ++i) { cur = cur->next; } // 插入 node->next = cur->next; cur->next = node; ++tList->length; return 0; } LinkListNode* LinkList_Get(LinkList* list, int pos) { if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) { return NULL; } TLinkList *tList = NULL; tList = (TLinkList *)list; LinkListNode *cur = NULL; cur = &(tList->header); for (int i = 0; i < pos; ++i) { cur = cur->next; } return cur->next; } LinkListNode* LinkList_Delete(LinkList* list, int pos) { if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) { return NULL; } TLinkList *tList = NULL; tList = (TLinkList *)list; LinkListNode *cur = NULL; cur = &(tList->header); for (int i = 0; i < pos; ++i) { cur = cur->next; } LinkListNode *ret = NULL; ret = cur->next; // 删除结点 cur->next = ret->next; --tList->length; return ret; }

工程代码详情：Github