數據結構----線性表（棧及其棧的實現）C語言學習筆記

棧：線性邏輯結構

棧的分類?

順序棧：順序存儲結構實現的棧

鏈式棧：鏈式存儲結構實現的棧

棧的性質

性質：先進后出或后進先出。

棧頂“指針”和棧底“指針”

棧底“指針”：標記棧底位置
棧頂“指針”：標記棧頂位置
這里的“指針”并非真的的指針，這里這是為了方便描述。

應用場景

1.函數調用的實現（遞歸）
2.業務需求，倒著的邏輯。比如：撤銷，網頁頁面，歷史記錄
3.物理上的堆棧：先進后出
4.c++ STL庫stack

溢出的概念（為什么要判空和判滿？）

1.上溢：棧滿之后，繼續入棧。
2.下溢：棧空之后，繼續出棧。

棧的實現

1.順序棧

棧底“指針”指向下標為0的位置。
棧頂“指針”指向位置，有兩個位置指向：

1）指向真正棧頂元素的位置

操作：

I.初始化? ?

II.入棧?

III.出棧?

IV.得到棧頂元素?

2）指向真正棧頂元素的下一位置

I.初始化 top=0；

//定義一個順序棧
typedef struct {int* data;  //指針模擬開數組int top;    //棧頂“指針”
}stack;
//初始化
stack initstack(){stack s;s.data= (int*)malloc(sizeof(int*) * maxsize);if (s.data == NULL) {printf("分配空間失敗。\n");}else {s.top = -1;    //指向真正的棧頂元素的位置//s.top=0;     指向真正棧頂元素的下一位置}return s;
}

II.入棧 s->data[s->top]=k; s->top++;

//入棧
void PushStack(stack* s,int k) {//判滿if (s->top == maxsize - 1) {printf("棧滿。\n");}else {//指向真正的棧頂元素的位置/*s->top++;s->data[s->top] = k;*///指向真正棧頂元素的下一位置s->data[s->top] = k;s->top++;}
}

III.出棧 s->top--;

//出棧
void PopStack(stack* s) {//判空if (s->top == -1) {printf("空棧，無法出棧。\n");}else {s->top--;int x = s->data[s->top];printf("刪除了棧頂元素%d \n", x);}
}

IV.得到棧頂元素 top--；s->data[s->top];

//得到棧頂元素
int GetStack(stack* s) {/*指向真正的棧頂元素的位置return s->data[s->top];*///指向真正棧頂元素的下一位置s->top--;return s->data[s->top];
}

2.鏈棧------基于單鏈表實現的

I.初始化：初始化一個帶頭結點的的單鏈表

//定義一個鏈棧
struct stack{int data;struct stack* next;
};
typedef stack* LinkStack;
//初始化
LinkStack initStack() {LinkStack s = (stack*)malloc(sizeof(stack));if (s == NULL) {printf("空間分配失敗。\n");}else {s->next = NULL;}return s;
}

II.入棧：頭插法

//入棧
LinkStack PushStack(LinkStack s,int k) {stack* p = (stack*)malloc(sizeof(stack));if (p == NULL) {printf("入棧時，空間分配失敗。\n");}else {//頭插p->data = k;p->next = s->next;s->next = p;}return s;
}

III.出棧：刪除首元結點

//出棧
LinkStack PopStack(LinkStack s) {if (s->next == NULL) {printf("空棧，無法出棧。\n");}else {s->next= s->next->next;}return s;
}

IV.得到棧頂元素：首元結點的元素

//得到棧頂元素
LinkStack GetStack(LinkStack s) {if (s->next == NULL) {printf("空棧，無棧頂元素。\n");}else {int a=s->next->data;printf("棧頂元素是%d \n", a);}return s;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/89376.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/89376.shtml
英文地址，請注明出處：http://en.pswp.cn/web/89376.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！