1、定義棧的數(shù)據(jù)結(jié)構(gòu)：
/* 節(jié)點(diǎn)結(jié)構(gòu)體*/
typedef struct Node {
int value; // 節(jié)點(diǎn)的值
struct Node* next; // 下一個(gè)節(jié)點(diǎn)的地址
} Node;
/* 棧結(jié)構(gòu)體*/
typedef struct {
Node* top; // 棧頂纬霞，指向首個(gè)節(jié)點(diǎn)的地址
} Stack;
2凌埂、初始化棧
void InitStack(Stack* stack){
stack->top = (Node*)malloc(sizeof(Node)); // 為棧頂申請內(nèi)存
stack->top->next = NULL; // 將棧頂?shù)闹赶虻南乱粋€(gè)節(jié)點(diǎn)置為空，防止出現(xiàn)野指針
}
3诗芜、入棧瞳抓，即向棧的頭部追加一個(gè)新的節(jié)點(diǎn)
void Push(Stack *stack,int value){
Node* node; // 創(chuàng)建新節(jié)點(diǎn)
node = (Node*)malloc(sizeof(Node)); // 為節(jié)點(diǎn)申請內(nèi)存
node->value = value; // 為節(jié)點(diǎn)賦值
node->next = stack->top->next; // 將棧頂指向的節(jié)點(diǎn)放在新創(chuàng)的節(jié)點(diǎn)之后
stack->top->next = node; // 將棧頂指向新的節(jié)點(diǎn)
}
4、出棧伏恐，即將隊(duì)尾的元素彈出
Node* Pop(Stack *stack){
Node* del = NULL; // 創(chuàng)建一個(gè)空節(jié)點(diǎn)用來儲(chǔ)存首個(gè)節(jié)點(diǎn)
del = stack->top->next; // 將棧的首個(gè)節(jié)點(diǎn)賦值給剛剛創(chuàng)建的空節(jié)點(diǎn)
if(del != NULL){ // 判斷棧內(nèi)是否有節(jié)點(diǎn)
stack->top->next = del->next; // 將棧頂指向下一個(gè)節(jié)點(diǎn)
}
return del;
}
5孩哑、 得到棧的長度
int Length(Stack *stack)
{
int length = 0;
Node *nNode; // 創(chuàng)建新節(jié)點(diǎn)
nNode = stack->top->next; // 將棧頂指向節(jié)點(diǎn)賦值給新節(jié)點(diǎn)
while (nNode != NULL) // 判斷是否循環(huán)到隊(duì)尾
{
length++;
nNode = nNode->next; // 將指針指向下一個(gè)節(jié)點(diǎn)
}
return length;
}
5翠桦、顯示單個(gè)節(jié)點(diǎn)的值
void NodeDisPlay(Node* node){
printf("This Node Value is %d.\n",node->value);
}
6横蜒、遍歷棧，每次將指針指向下個(gè)節(jié)點(diǎn)輸入節(jié)點(diǎn)的值销凑，通過指針是否為空判斷是否到達(dá)棧尾
void StackDisplay(Stack *stack){
Node *nNode; // 創(chuàng)建新節(jié)點(diǎn)
nNode = stack->top->next; // 將棧頂指向節(jié)點(diǎn)賦值給新節(jié)點(diǎn)
while (nNode != NULL) // 判斷是否循環(huán)到隊(duì)尾
{
NodeDisPlay(nNode); // 顯示當(dāng)前節(jié)點(diǎn)的值
nNode = nNode->next; // 將指針指向下一個(gè)節(jié)點(diǎn)
}
}
- 清空棧
void CleanStack(Stack *stack){
Node *pNode, *tmp; // pNode節(jié)點(diǎn)用來存儲(chǔ)棧節(jié)點(diǎn)丛晌，tmp用來釋放內(nèi)存
pNode = stack->top->next; // 將棧頂指向節(jié)點(diǎn)賦值給pNode
while(pNode != NULL){
tmp = pNode; // 記住需要釋放的內(nèi)存地址
pNode = pNode->next;
free(tmp); // 釋放該地址的內(nèi)存
}
}
- 銷毀整個(gè)棧
void Destory(Stack *stack){
CleanStack(stack); // 首先清空棧
free(stack->top); // 釋放棧
}
- 下面是完整的代碼
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int value; // 節(jié)點(diǎn)的值
struct Node *next; // 下一個(gè)節(jié)點(diǎn)的地址
} Node;
typedef struct
{
Node *top; // 棧頂，指向首個(gè)節(jié)點(diǎn)的地址
} Stack;
void InitStack(Stack *stack)
{
stack->top = (Node *)malloc(sizeof(Node)); // 為棧頂申請內(nèi)存
stack->top->next = NULL; // 將棧頂?shù)闹赶虻南乱粋€(gè)節(jié)點(diǎn)置為空斗幼，防止出現(xiàn)野指針
}
void Push(Stack *stack, int value)
{
Node *node; // 創(chuàng)建新節(jié)點(diǎn)
node = (Node *)malloc(sizeof(Node)); // 為節(jié)點(diǎn)申請內(nèi)存
node->value = value; // 為節(jié)點(diǎn)賦值
node->next = stack->top->next; // 將棧頂指向的節(jié)點(diǎn)放在新創(chuàng)的節(jié)點(diǎn)之后
stack->top->next = node; // 將棧頂指向新的節(jié)點(diǎn)
}
Node *Pop(Stack *stack)
{
Node *del = NULL; // 創(chuàng)建一個(gè)空節(jié)點(diǎn)用來儲(chǔ)存首個(gè)節(jié)點(diǎn)
del = stack->top->next; // 將棧的首個(gè)節(jié)點(diǎn)賦值給剛剛創(chuàng)建的空節(jié)點(diǎn)
if (del != NULL)
{ // 判斷棧內(nèi)是否有節(jié)點(diǎn)
stack->top->next = del->next; // 將棧頂指向下一個(gè)節(jié)點(diǎn)
}
return del;
}
int Length(Stack *stack)
{
int length = 0;
Node *nNode; // 創(chuàng)建新節(jié)點(diǎn)
nNode = stack->top->next; // 將棧頂指向節(jié)點(diǎn)賦值給新節(jié)點(diǎn)
while (nNode != NULL) // 判斷是否循環(huán)到隊(duì)尾
{
length++;
nNode = nNode->next; // 將指針指向下一個(gè)節(jié)點(diǎn)
}
return length;
}
void NodeDisPlay(Node *node)
{
printf("This Node Value is %d.\n", node->value);
}
void StackDisplay(Stack *stack)
{
Node *nNode; // 創(chuàng)建新節(jié)點(diǎn)
nNode = stack->top->next; // 將棧頂指向節(jié)點(diǎn)賦值給新節(jié)點(diǎn)
while (nNode != NULL) // 判斷是否循環(huán)到隊(duì)尾
{
NodeDisPlay(nNode); // 顯示當(dāng)前節(jié)點(diǎn)的值
nNode = nNode->next; // 將指針指向下一個(gè)節(jié)點(diǎn)
}
}
void CleanStack(Stack *stack)
{
Node *pNode, *tmp; // pNode節(jié)點(diǎn)用來存儲(chǔ)棧節(jié)點(diǎn)澎蛛，tmp用來釋放內(nèi)存
pNode = stack->top->next; // 將棧頂指向節(jié)點(diǎn)賦值給pNode
while (pNode != NULL)
{
tmp = pNode; // 記住需要釋放的內(nèi)存地址
pNode = pNode->next;
free(tmp); // 釋放該地址的內(nèi)存
}
}
void Destory(Stack *stack)
{
CleanStack(stack); // 首先清空棧
free(stack->top); // 釋放棧
}
int main()
{
Stack *stack;
InitStack(stack);
Push(stack, 1);
Push(stack, 2);
Push(stack, 3);
StackDisplay(stack);
printf("This Stack's length is %d.\n",Length(stack));
Node *newNode = Pop(stack);
printf("This Stack's length is %d.\n", Length(stack));
NodeDisPlay(newNode);
StackDisplay(stack);
Destory(stack);
return 0;
}
