数据结构学习：栈
棧是一種后進(jìn)先出(Last in First Out)的數(shù)據(jù)結(jié)構(gòu)。
由于棧比較好理解，這里只附上用c實(shí)現(xiàn)棧的代碼。
棧的鏈?zhǔn)絻Υ?/strong>
#include <stdio.h> #include <stdlib.h>#define SUCCEED 1 #define FAIL 0 #define TestNum 5typedef int SElemType; typedef int Status;//棧的結(jié)點(diǎn)結(jié)構(gòu)體 typedef struct StackNode {SElemType data;struct StackNode *next; }StackNode,*LinkStackPtr;//棧的結(jié)構(gòu)體 typedef struct LinkStack{LinkStackPtr top;int count; }LinkStack;Status Push(LinkStack *S,SElemType data){LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));s->data = data;s->next = S->top;S->top = s;S->count++;return SUCCEED; }Status Pop(LinkStack *S,SElemType *e){LinkStackPtr tmp;if(S->count == 0) return FAIL;*e = S->top->data;tmp = S->top;S->top = S->top->next;S->count--;free(tmp);return SUCCEED; }int main(){int i;LinkStack test;SElemType data[]={1,2,3,4,5};SElemType topData;printf("Push test\n");for(i = 0 ; i < TestNum ; i++){Push(&test, data[i]);}printf("The Count of this Stack is %d\n",test.count);printf("Pop test\n");for(i = 0 ; i < TestNum ; i++){Pop(&test,&topData);printf("The top Data is %d\n",topData);printf("There are %d remain in Stack\n",test.count);}return 0; }棧的順序儲存
#include <stdio.h> #include <stdlib.h>#define SUCCEED 1 #define FAIL 0 #define TestNum 5 #define StackMax 1000 //該棧的最大sizetypedef int SElemType; typedef int Status;//棧的結(jié)點(diǎn)結(jié)構(gòu)體 typedef struct StackNode {SElemType data; }StackNode;//棧的結(jié)構(gòu)體 typedef struct LinkStack{StackNode *Stack;int top; //用來保存棧頂?shù)南禂?shù)int count; //用來保存棧的大小 }LinkStack;Status Push(LinkStack *S,SElemType data){StackNode *stack;stack = S->Stack;S->top++; //更新頭結(jié)點(diǎn)的位置stack[S->top].data = data;S->count ++;return SUCCEED; }Status Pop(LinkStack *S,SElemType *e){if(S->count == 0) return FAIL;*e = S->Stack[S->top].data; //利用e傳回棧頂?shù)臄?shù)據(jù)S->top--;S->count--;return SUCCEED; }//初始化棧 Status initStack(LinkStack *S){S->Stack = (StackNode*)malloc(sizeof(StackNode)*StackMax);S->top = -1;S->count = 0;return SUCCEED; }int main(){int i;LinkStack test;SElemType data[]={1,2,3,4,5};SElemType topData;initStack(&test); //初始化棧printf("Push test\n");for(i = 0 ; i < TestNum ; i++){Push(&test, data[i]);}printf("The Count of this Stack is %d\n",test.count);printf("Pop test\n");for(i = 0 ; i < TestNum ; i++){Pop(&test,&topData);printf("The top Data is %d\n",topData);printf("There are %d remain in Stack\n",test.count);}return 0; }聊聊個人對C語言中串行計算，函數(shù)調(diào)用，與棧之間的初步理解。
當(dāng)調(diào)用函數(shù)時，被調(diào)用函數(shù)的參數(shù)和返回值被儲存當(dāng)前程序的棧區(qū)，之后被調(diào)用函數(shù)再為自身的自動變量和臨時變量在棧區(qū)上分配空間。當(dāng)函數(shù)調(diào)用返回時，在棧區(qū)內(nèi)的參數(shù)返回值、自動變量和臨時變量等都會被釋放。
單線程在程序執(zhí)行時，所走的程序路徑按照連續(xù)順序排下來，前面的必須處理好，后面的才會執(zhí)行。C語言程序在運(yùn)行是就是單線程串行計算。當(dāng)遇到調(diào)用其他函數(shù)的時候，就會把當(dāng)前的當(dāng)前的參數(shù)傳出去，運(yùn)行的位置當(dāng)前參數(shù)保存在棧頂，并開辟新的棧區(qū)（我是這么理解的）。調(diào)用的函數(shù)運(yùn)行完畢，就返回之前的函數(shù)，并接著運(yùn)行下去。
當(dāng)遇到調(diào)用自己的情況（遞歸），就會將運(yùn)行的位置和當(dāng)前參數(shù)push進(jìn)去，傳參，當(dāng)遞歸結(jié)束后一層層pop直到棧底。當(dāng)遞歸次數(shù)過多就會overflow。
轉(zhuǎn)載于:https://www.cnblogs.com/he11o-liu/p/7503263.html
總結(jié)
- 上一篇： 新应用上线 Snippet
- 下一篇： Linux 随机启动 Mysql