文章目錄

• • • 1 鏈棧定義
    • 2 鏈棧基本操作
    • 3 鏈棧代碼實(shí)現(xiàn)

1 鏈棧定義

鏈棧：采用鏈?zhǔn)酱鎯?chǔ)的棧稱為鏈棧

在一個(gè)鏈棧中，棧底就是鏈表的最后一個(gè)結(jié)點(diǎn)，而棧頂總是鏈表的第一個(gè)結(jié)點(diǎn)。因此，新入棧的元素即為鏈表新的第一個(gè)結(jié)點(diǎn)，只要系統(tǒng)還有存儲(chǔ)空間，就不會(huì)有棧滿的情況發(fā)生。

鏈棧的優(yōu)點(diǎn)在于多個(gè)棧共享存儲(chǔ)空間和提高其效率，且不存在棧滿上溢的情況，通常采用單鏈表實(shí)現(xiàn)，并規(guī)定所有操作都是在單鏈表的表頭進(jìn)行的。

2 鏈棧基本操作

初始化鏈棧

void InitStack（LinkStack*s） {*s=（LinkSNode*）malloc（sizeof（LinkSNode））；（*s）->next=NULL； }

判斷棧空

int LinkStackEmpty（LinkStack*S） {return S->top==NULL； }

入棧操作

void Push（LinkStack s，int e） {LinkStack p=（LinkStack）malloc（sizeof（LinkSNode））；p->data=e；p->next=s->next；s->next=p； }

將要入棧的元素構(gòu)造結(jié)點(diǎn)p，然后將其插入到棧頂指針s之后，讓s始終指向新插入的結(jié)點(diǎn)（保證s永遠(yuǎn)是棧頂指針）

出棧操作

int Pop（LinkStack s，int*e） {LinkStack p；if（EmptyStack（s））return ERROR；p=S->next；*e=p->data；s->next=p->next；free（p）；return OK； }

• 入出都要保證s永遠(yuǎn)是棧頂指針
• 所有棧（隊(duì)列）的操作，都要注意入棧（隊(duì)）判滿，出棧（隊(duì)）判空的檢查
• 是否為滿，滿時(shí)不進(jìn)，是否為空，空時(shí)不出

取棧頂元素

int Get Top（LinkStack s，int*e） {if（EmptyStack（s））return ERROR；*e=s->next->data；return OK； }

3 鏈棧代碼實(shí)現(xiàn)

#include <stdio.h> #include <stdlib.h>typedef int ElementType; // 特殊的線性表，只有在棧頂一端進(jìn)行插入刪除 typedef struct node {ElementType data;struct node *Next; } *Stack;Stack InitStack(void) {Stack s = (Stack)malloc(sizeof(struct node));s->data = 0;s->Next = NULL; }void Push(Stack s, ElementType e) //保證S永遠(yuǎn)是棧頂指針 {Stack p = (Stack)malloc(sizeof(struct node));p->data = e;p->Next = s->Next;s->Next = p; }void Pop(Stack s, ElementType *e) //保證S永遠(yuǎn)是棧頂指針 {if (s->Next == NULL) {return;}Stack p = s->Next;*e = p->data;s->Next = p->Next;free(p); }void PrtStack(Stack s) {Stack p = s->Next;while (p) {printf("%d ", p->data);p = p->Next;}printf("\n"); }int main(void) {ElementType e;Stack s = InitStack();printf("please input a element :");scanf("%d", &e);Push(s, e);PrtStack(s);Pop(s, &e);printf("Pop a element : %d ", e);return 0; }

總結(jié)

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

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