棧的簡單介紹

關于棧的性質咳咳

棧：棧是一種特殊的線性表,其中只讓在一端插入和刪除元素。

后進先出

進行插入刪除的那一端叫棧頂，另一端叫棧底

我們實現的棧是基于一個動態順序表的的棧，會實現棧的? ?入棧，出棧，獲取棧頂元素，獲取棧中元素個數，判斷棧是否為空（純c語言版本）

操作的命名如下

棧的信息

這是棧的信息，

接下來初始化

我們在創建好棧的信息后定義一個棧，然后進行初始化，初始時我們可以讓棧中放4個元素，在開一段可以放入4個元素的內存，讓a指向

初始化

初始化要用到的函數malloc,這個不懂的可以看這個

動態內存管理（）-CSDN博客

在我們開空間的化可能會開失敗，如果開失敗的化，直接把返回的指針給ps->a程序會出現內存問題，所以我們創建一個臨時變量，存放新開空間首位置的指針，如果這個指針不為空，就把臨時的tmp指針給ps->a。這個操作在后續操作用到，比如在入棧時棧滿，我們還要進行一次擴容，所以我們可以寫一個擴容函數

入棧

代碼如下

判空

判空這個操作實現的功能是如果這個棧里面沒有元素的化返回假，有元素返回真

在? Stack.h 中加入#include<stdbool.h>? ?就可以用布爾類型了，我們的棧中的top

真好就是棧中元素的真是個數-1，因為top,從0開始就有元素了，所以返回 top+1;即可

代碼如下

出棧

我們判空操作實現后就方便出棧了

在出棧時需要考慮一個棧是否為空的情況所以直接調用上面的函數特判一下，不為空讓top--，就可以了

代碼

獲取棧頂元素

判斷一下不是空，然后返回棧中top指向的元素，代碼如下

woc,怎末感覺突然沒話講了，

獲取棧中元素個數，棧的銷毀

完整的代碼

//Stack.h#include<stdio.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<ctype.h>
#include<stdbool.h>
#include<assert.h>
#include<windows.h>//棧的元素類型
typedef int STaType;typedef struct Stack
{STaType* a;int top;//棧頂int capacity;//棧滿容量
}Stack;//棧的打印
void Stack_print(Stack p);
//棧中元素的輸入
void Stack_scan(STaType* x);
//擴容
void Stack_Check();
//初始化
void Stack_Lnit(Stack* ps);
//入棧，出棧
void Stack_push(Stack* ps, STaType x);
void Stack_pop(Stack* ps);
//獲取棧頂元素
STaType Stack_top(Stack* ps);
//獲取棧內元素個數
int Stack_size(Stack* ps);
//判空
bool Stack_empty(Stack* ps);
//銷毀
void Stack_Destroy(Stack* ps);

//Stack.c#include"Stack.h"//typedef struct Stack
//{
//	STaType* a;
//	int top;//棧頂
//	int capacity;//棧滿容量
//}Stack;//棧的打印
void Stack_print(Stack p)
{printf("\n現在棧如下\n");while (p.top != -1){printf("%d\n", p.a[p.top]);p.top--;}printf("\n");printf("\n");
}//棧中元素的輸入
void Stack_scan(STaType* x)
{scanf("%d", x);
}//擴容
void Stack_Check(Stack*ps)
{assert(ps);int x = ps->capacity==0?4:ps->capacity*2;if (ps->top == ps->capacity){STaType* tmp = (STaType*)malloc(sizeof(STaType)*x);assert(tmp);ps->a = tmp;}ps->capacity = x;
}//初始化
void Stack_Lnit(Stack* ps)
{assert(ps);ps->capacity = 4;ps->top = -1;//棧頂有元素STaType *tmp= (STaType*)malloc(sizeof(STaType)*ps->capacity);if (tmp != NULL)ps->a = tmp;
}//入棧，出棧
void Stack_push(Stack* ps, STaType x)
{assert(ps);Stack_Check(ps);//判斷擴容ps->a[++ps->top] = x;
}void Stack_pop(Stack* ps)
{assert(ps);if(!Stack_empty(ps))ps->top--;else{printf("棧為空,出棧失敗\n");return;}
}//獲取棧頂元素
STaType Stack_top(Stack* ps)
{assert(ps);if (Stack_empty(ps)){printf("棧為空,出棧失敗\n");return 0;}return ps->a[ps->top];
}//獲取棧內元素個數
int Stack_size(Stack* ps)
{assert(ps);return ps->top + 1;
}//判空
bool Stack_empty(Stack* ps)
{//為空返回真，不為空返回假assert(ps);return ps->top == -1;
}//銷毀
void Stack_Destroy(Stack* ps)
{if (ps->a){free(ps->a);}ps->a = NULL;ps->top = ps->capacity = 0;
}

//Text.c#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"void enumm()
{printf("********************************************************************\n");printf("********************************************************************\n");printf("********************************************************************\n");printf("********************************************************************\n");printf("**1  初始化                           2.入棧                                 **************\n");printf("**3  出棧                           4.獲取棧頂元素                   **************\n");printf("**5  獲取棧中元素個數       6判空                                 **************\n");printf("**7  銷毀棧                        0退出                                 **************\n");printf("********************************************************************\n");printf("*******************************************************************\n");printf("********************************************************************\n");
}void text()
{Stack pp;enumm();do{int po; scanf("%d", &po);switch (po){case 1://創Stack_Lnit(&pp);break;case 2://入棧STaType x;Stack_scan(&x);Stack_push(&pp, x);Stack_print(pp);break;case 3://出棧Stack_pop(&pp);Stack_print(pp);break;case 4://獲取棧頂元素STaType xx= Stack_top(&pp);printf("%d", xx);break;case 5://獲取棧中元素個數int n = Stack_size(&pp);printf("%d", n);break;case 6://判空if (!Stack_empty(&pp)) printf("不是空\n");else printf("是空\n");break;case 7://銷毀棧Stack_Destroy(&pp);case 0://退出goto xxx;break;}//system("cls");} while (1);
xxx:;}signed main()
{text();getchar();return 0;
}