C語言中順序棧和鏈棧的定義和使用詳解
棧的基本內容
無論是我們接下來要講的棧還是後面要講到的隊列,他們雖然在名字上不同於我們之前的順序表或者單鏈表,但是它們本質也是線性表,隻是在基本操作上沒有表那麼“自由”。比如:棧隻能從棧頂進行插入和刪除,而隊列隻能從對頭進行刪除,隊尾進行插入。
舉例:
疊放在一起的盤子,當想要加入新的盤子時,隻能在底部或者尾部加入,刪除同樣也是。
空棧:
棧頂和棧底:
順序棧
既然上文都說到“棧”和“隊列”都是一種“特殊的”線性表”,那麼順序棧,顧名思義就是按照順序存儲的棧。
定義
既然是順序存儲的,那麼我們依然可以和順序表相類似,采用數組去存放!
typedef struct { int data[size]; int top;//棧頂指針 }seqstack;//seqstack為結構體類型
入棧操作
對於順序表的插入操作,我們在棧中叫做“入棧”,由於棧的特殊性,隻能在棧頂進行操作。
需要提醒的是:一定是棧頂指針先進行移動,再將新插入的元素賦給棧頂空間。也就是說S.top = S.top + 1;S.data[S.top] = x;
的順序不能發生顛倒。
void Pushstack(seqstack& S) { if (S.top == size) printf("棧滿,拒絕元素繼續入棧!"); else { printf("請依次輸入你要入棧的元素:\n"); int x,i; for (i = 0; i < size; i++) { scanf("%d", &x); S.top = S.top + 1; S.data[S.top] = x; printf("入棧成功!\n"); } } }
舉例:
出棧
雖然是“出棧”,但是如果後續沒有入棧操作對出棧位置進行數據覆蓋的話,其實出棧並不是真正意義上的“消失”,隻是在邏輯上上被刪除瞭,其實給出下標地址,依然可以找到該元素。**return S.data[S.top];**就是將該元素的值返回,以便下次能夠快速找到。
int PopStack(seqstack& S) { if (S.top == -1) { printf("棧為空,沒有元素輸出!"); } { printf("當前棧頂元素為:"); return S.data[S.top]; S.top = S.top - 1; } }
關於順序棧的其他操作都是比較簡單的,這裡就不一一進行講解瞭,需要註意的事項我會在下面的完整代碼中註釋出來!
順序棧的缺點
棧的大小不可發生變化。
出棧順序的計算方法
如上圖所示:
進棧順序為a->b->c->d->e,則對應的出棧順序為e->d->c->b->a
但有時候出棧和進棧是穿插進行的:
舉例:
這種進棧出棧穿插的方式有很多種。
由此,我們可以得出一個結論:
鏈棧
既然上文都說到“棧”和“隊列”都是一種“特殊的”線性表”,那麼鏈棧,顧名思義就是按照鏈式存儲的棧。
基本實現方法和單鏈表相同,這裡就不一一進行講解瞭,需要註意的事項我會在下面的完整代碼中註釋出來!
鏈棧完整代碼如下:
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #define size 5 typedef struct LinkNode { int data; struct LinkNode* next; }Linkstack; //初始化 void Iniststack(Linkstack *L) { L= (LinkNode*)malloc(sizeof(LinkNode)); if (!L->data) { printf("申請失敗"); } else { L->data = 0; L->next = NULL; } } //入棧 void Pushstack(Linkstack *L) { int e,x; printf("請輸入你要創建的鏈棧長度:"); scanf("%d", &x); printf("請輸入你要入棧的元素:\n"); for (int i = 0; i < x; i++) { LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode)); scanf("%d", &e); s->data = e; s->next = L->next; L->next = s; } } //出棧 int Popstack(Linkstack* L) { LinkNode* s= L->next; s->data = L->data; L->next = s->next; return s->data; } //讀取棧頂元素 int Getstack(Linkstack* L) { if (!L->data) { printf("棧為空!"); } else { int e = L->next->data; return e; } } //輸出棧中元素 void Printsatck(Linkstack* L) { if (!L->data) { printf("棧為空!"); } else { LinkNode* p; p = L; printf("棧中元素如下:"); while (p) { p = p->next; printf("%d", p->data); } } } int main() { Linkstack L; Iniststack(&L); Pushstack(&L); Popstack(&L); Getstack(&L); Printsatck(&L); }
輸出:
順序棧完整代碼如下:
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #define size 5 typedef struct { int data[size]; int top; }seqstack; //初始化操作 void InistStack(seqstack &S) { S.top = -1; } //判空操作 void IsEmpty(seqstack& S) { if (S.top == -1) printf("目前棧為空!\n"); } //入棧操作 void Pushstack(seqstack& S) { if (S.top == size) printf("棧滿,拒絕元素繼續入棧!"); else { printf("請依次輸入你要入棧的元素:\n"); int x,i; for (i = 0; i < size; i++) { scanf("%d", &x); S.top = S.top + 1; S.data[S.top] = x; printf("入棧成功!\n"); } } } //讀取棧頂元素 void Getstack(seqstack& S) { if (S.top == -1) { printf("棧為空,沒有元素輸出!"); } { printf("當前棧頂元素為:"); printf("%d\n", S.data[S.top]); } } //輸出棧中元素 void Printstack(seqstack& S) { if (S.top == -1) { printf("棧為空,沒有元素輸出!"); } else { printf("棧中元素如下:"); for (int i = 0; i < size; i++) { printf("%d", S.data[i]); } printf("\n"); } } //出棧 int PopStack(seqstack& S) { if (S.top == -1) { printf("棧為空,沒有元素輸出!"); } { printf("當前棧頂元素為:"); return S.data[S.top]; S.top = S.top - 1; } } //刪除棧頂元素 int Deletestack(seqstack& S) { if (S.top == -1) { printf("棧為空!\n"); } else { int e; for (int i = 0; i < size; i++) { e = S.data[S.top]; S.top = S.top - 1; return e; } printf("所有元素已被刪除!\n"); } } //清棧 void Clearstack(seqstack& S) { S.top = -1; printf("棧已經被清空!\n"); } int main() { seqstack S; int x; InistStack(S); IsEmpty(S); Pushstack(S); Getstack(S); Printstack(S); /*x=PopStack(S);*/ Deletestack(S); Clearstack(S); Printstack(S); }
輸出:
以上就是C語言中順序棧和鏈棧的定義和使用詳解的詳細內容,更多關於C語言順序棧 鏈棧的資料請關註WalkonNet其它相關文章!