今天學(xué)習(xí)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)最大的好處就是沒有空間的限制，通過指針指向?qū)⒔Y(jié)點(diǎn)像一個(gè)鏈子一樣把結(jié)點(diǎn)鏈接，那么棧的同樣可以用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱為鏈棧。想想看，棧只是棧頂來做插入和刪除操作，棧頂放在鏈表的頭部還是尾部呢？由于單鏈表有頭指針，而棧頂指針也是必須的，那么干嘛不讓他們合二為一呢，所以比較好的辦法是把棧頂放到單鏈表的頭部。另外棧頂在頭部了，那么單鏈表的頭結(jié)點(diǎn)也就失去了意義，通常對(duì)于鏈棧來說，是不需要頭結(jié)點(diǎn)的。

同樣對(duì)于鏈棧來說，基本不存在棧滿的情況，除非內(nèi)存已經(jīng)沒有可用的空間了。

下面是鏈棧的指向圖：

同樣鏈棧中最重要的算法是壓棧和彈棧。

壓棧操作：

?

?

操作很簡(jiǎn)單，新建結(jié)點(diǎn)，給結(jié)點(diǎn)數(shù)據(jù)域賦值，指針域指向原來?xiàng)ｍ斣亍?/p>

然后將棧頂指針指向新結(jié)點(diǎn)，元素個(gè)數(shù)+1,就ok。如下圖：

彈棧操作：

?

和壓棧相反，將棧頂元素的數(shù)據(jù)域取通過指針返回這個(gè)數(shù)據(jù)，將要彈出的元素的指針域賦值給棧頂指針，然后釋放這個(gè)元素，這樣棧頂指針就指向新的棧頂了，然后元素個(gè)-1。如圖：

下面我們來看一下相關(guān)代碼的實(shí)現(xiàn)。

?

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #define ERROR 0 #define OK 1 #define TRUE 1 #define FALSE 0 typedef int Status; typedef int EleType; typedef struct StackNode {EleType data;//結(jié)點(diǎn)數(shù)據(jù)域struct StackNode* next;//結(jié)點(diǎn)指針域 }StackNode,* LinkStackPoi; //鏈棧的數(shù)據(jù)結(jié)構(gòu) typedef struct LinkStack {LinkStackPoi top;//棧頂結(jié)點(diǎn)int count;//元素個(gè)數(shù) }LinkStack; //初始化 Status InitLinkStack(LinkStack* stack) {if (!stack){return ERROR;}stack->top = NULL;stack->count = 0;return OK; } //清空數(shù)據(jù)，釋放結(jié)點(diǎn)內(nèi)存，實(shí)際上就是pop所有數(shù)據(jù) Status ClearLinkStack(LinkStack* stack) {if (!stack||!stack->count){return ERROR;}while (stack->count){StackNode* node = stack->top;stack->top = node->next;free(node);stack->count--;}return OK; } //判斷鏈棧是否為空 Status EmptyLinkStack(LinkStack* stack) {if (!stack){return ERROR;}return stack->count == 0 ? 1 : 0; } //獲取元素個(gè)數(shù) int GetLengthLinkStack(LinkStack* stack) {if (!stack ){return -1;}return stack->count; } Status GetTop(LinkStack* stack, StackNode** stackNode) {if (!stack){return ERROR;}*stackNode = stack->top;//將棧頂元素的指針返回，獲取指向可修改棧頂元素內(nèi)容。return OK; } //Status GetTop(LinkStack* stack, StackNode* stackNode) //{ // if (!stack) // { // return ERROR; // } // *stackNode = *(stack->top);//將棧頂元素的副本內(nèi)容，修改不會(huì)影響到棧頂元素。 // return OK; //} /* 彈棧 棧頂指針指向要彈出元素前置結(jié)點(diǎn)，然后釋放彈出元素內(nèi)存空間，然后count-1 */ Status pop(LinkStack* stack,EleType *e) {if (!stack && stack->count){return ERROR;}StackNode* node = stack->top;*e = node->data;stack->top = node->next;//棧頂指針指向新的棧頂元素free(node);//釋放元素空間stack->count--;return OK; } /* 壓棧 先將壓入元素放入到鏈表表中，然后再將棧頂指針指向壓入的元素，然后count+1. */ Status push(LinkStack* stack,EleType e) {if (!stack){return ERROR;}StackNode* node = (StackNode*)malloc(sizeof(StackNode));node->next = stack->top;//將元素加入鏈表中node->data = e;stack->top = node;//棧頂元素指向壓入元素stack->count++;return OK; } void PrintfLinkStack(LinkStack* stack) {if (!stack&&stack->count){return;}StackNode* node = stack->top;while (node){printf("%d,", node->data);node = node->next;}puts("");return; } int main(int argc, char *argv[]) {LinkStack stack;InitLinkStack(&stack);//初始化push(&stack, 1);push(&stack, 2);push(&stack, 3);push(&stack, 4);push(&stack, 5);puts("鏈棧元素：");PrintfLinkStack(&stack);printf("鏈棧元素個(gè)數(shù)：%d\n", GetLengthLinkStack(&stack));EleType e1,e2;pop(&stack, &e1);printf("彈出第一個(gè)元素：%d\n", e1);pop(&stack, &e2);printf("彈出第二個(gè)元素：%d\n", e2);puts("鏈棧元素：");PrintfLinkStack(&stack);printf("鏈棧元素個(gè)數(shù)：%d", GetLengthLinkStack(&stack));printf("\n");return 0; }

驗(yàn)證結(jié)果：

?

學(xué)習(xí)算法，我們首先要去領(lǐng)悟它的這種思想，以后在遇到問題時(shí)才會(huì)有思路。

?

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的栈的链式存储结构及实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。