鏈棧介紹

鏈棧也是我們所說的采用鏈式存儲結構的棧。往往通過單鏈表的方式來實現，使用鏈式棧的優點在于它能夠克服用數組實現的順序棧空間利用率不高的特點，但是需要為每個棧元素分配額外的指針空間用來存放指針域。棧 是一種受限制的線性表，它具有后進先出（Last-In-First-Out）的特性。所以呢本次編寫鏈棧呢 采用以前寫的企業級單鏈表形式編寫。不知道企業級單鏈表？請看數據結構與算法：企業級鏈表實現（超詳細），感覺這種思想超贊，你值得擁有。

鏈棧相關算法接口

同樣對外提供LinkStack類型也就是void* ，對用戶隱藏底層代碼實現，鏈表結點只維護鏈表結構和用戶數據分類。用戶數據只需在業務數據結構體最上面提供4個字節的空間即可。

#pragma once #ifndef __LINKSTACK_H__ #define __LINKSTACK_H__ #define MAXSIZE 1024 typedef enum { FALSE, TRUE } Boolean;typedef struct StackNode {struct StackNode* next; }StackNode;typedef void* LinkStack;//初始化 LinkStack Init_LinkStack(); //壓棧 void Push_LinkStack(LinkStack stack, void* data); //彈棧 void* Pop_LinkStack(LinkStack stack); //獲取棧頂 void* Top_LinkStack(LinkStack stack); //是否為空棧 //1 是空，0 非空 int IsEmpty_LinkStack(LinkStack stack); //棧元素個數 int Size_LinkStack(LinkStack stack); //銷毀 棧 void Destroy_LinkStack(LinkStack stack);#endif // !__LINKSTACK_H__

鏈棧相關算法實現

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include "LinkStack.h"//鏈棧 typedef struct LStack {StackNode header;//鏈棧頭結點header.next 指向棧頂元素int size; }LStack;//初始化 LinkStack Init_LinkStack() {LStack* stack = (LStack*)malloc(sizeof(LStack));stack->header.next = NULL;stack->size = 0;return stack; } //壓棧 void Push_LinkStack(LinkStack stack, void* data) {if (stack == NULL || data == NULL){return;}LStack* myStack = stack;((StackNode*)data)->next = myStack->header.next;myStack->header.next = data;myStack->size++; } //彈棧 void* Pop_LinkStack(LinkStack stack) {LStack* myStack = stack;if (stack == NULL || myStack->size == 0){return NULL;}StackNode* node = myStack->header.next;myStack->header.next = node->next;myStack->size--;return node; } //獲取棧頂 void* Top_LinkStack(LinkStack stack) {LStack* myStack = stack;if (stack == NULL || myStack->size == 0){return NULL;}StackNode* node = myStack->header.next;return node; } //是否為空棧 //1 是空，0 非空 int IsEmpty_LinkStack(LinkStack stack) {LStack* myStack = stack;if (stack == NULL){return 1;}if (myStack->size == 0){return 1;}return 0; } //棧元素個數 int Size_LinkStack(LinkStack stack) {LStack* myStack = stack;if (stack == NULL){return 0;}return myStack->size; } //銷毀 棧 void Destroy_LinkStack(LinkStack stack) {LStack* myStack = stack;if (stack == NULL){return;}free(myStack);myStack = NULL; }

代碼運行檢測

Main.c測試代碼

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include "LinkStack.h" //測試 數據 typedef struct Person {StackNode node;char name[64];int age; }Person;int main(int argc, char *argv[]) {Person p1 = { NULL,"Lily",11 };Person p2 = { NULL,"Laymond",21 };Person p3 = { NULL,"John",31 };Person p4 = { NULL,"Leo",41 };Person p5 = { NULL,"Zeo",51 };LinkStack stack = Init_LinkStack();Push_LinkStack(stack, &p1);Push_LinkStack(stack, &p2);Push_LinkStack(stack, &p3);Push_LinkStack(stack, &p4);Push_LinkStack(stack, &p5);printf("棧頂元素:name=%s,age=%d\n", ((Person*)Top_LinkStack(stack))->name, ((Person*)Top_LinkStack(stack))->age);printf("棧的元素個數:%d\n", Size_LinkStack(stack));Person* p = NULL;while (!IsEmpty_LinkStack(stack)){p = Pop_LinkStack(stack);printf("name=%s,age=%d\n", p->name, p->age);}printf("棧的元素個數:%d\n", Size_LinkStack(stack));Destroy_LinkStack(stack);return 0; }

運行結果

總結

以上是生活随笔為你收集整理的线性表：链栈算法实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。