基本概念
其它概念详情參看前一篇博文：栈的顺序存储 - 设计与实现 - 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;
}
project代码详情：Github