前言

栈是一种实现“先进后出”的存储结构。
本文主要介绍对动态栈的初始化、压栈、遍历、出栈、清空。

对动态栈的操作

初始化

初始化伪算法

初始化代码

void init(PSTACK pS)
{pS->pTop = (PNODE)malloc(NODE); //创建一块动态内存，让pS->pTop指向它 上图1{if(NULL == pS->pTop)   //判断内存是否分配成功{printf("内存分配失败\n");exit(-1);}}else{pS->pBottom = pS->pTop;  //上图2pS->pTop->pNext = NULL;  //上图3}return;
}

压栈

压栈伪算法

压栈代码

void push(PSTACK pS, int val)
{PNODE pNew = (PNODE)malloc(sizeof(NODE));  //4if(NULL == pNew){printf("内存分配失败\n");exit(-1);}pNew->data = val;  //5pNew->pNext = pS->pTop; //6   不能写成pNew->pNext = pS->pBottom; 第一次压栈不会出错，后面就会出错pS->pTop = pNew;  //7return;
}

遍历

遍历代码

void traverse(PSTACK pS)
{PNODE p = pS->pTop;while(p != pS->pBottom){printf("%d ", p->data);p = p->pNext;}printf("\n");return;
}

出栈

出栈代码

//判断栈是否为空
bool is_empty(PSTACK pS)
{if(pS->pTop == pS->pBottom)return true;elsereturn false;
}//出栈
bool pop(PSTACK pS, int *pval)
{if(is_empty(pS))return false;else{PNODE p = pS->pTop;*pval = p->data;  // 返回出栈的值pS->pTop = p->pNext;free(p);p = NULL;return true;}
}

清空

清空伪代码

清空代码

void clear(PSTACK pS)
{if(is_empty(pS))return;else{PNODE p = pS->pTop;  //1PNODE q = NULL;while(p != pS->pBottom) {q = p->pNext;   //2free(p);        //3p = q;          //4}pS->pTop = pS->pBottom;}
}

整体代码实现

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>typedef struct Node
{int data;struct Node *pNext;
}NODE, *PNODE;typedef struct Stack
{PNODE pTop;PNODE pBottom;
}STACK, *PSTACK;//函数声明
void init(PSTACK);
void push(PSTACK, int);
void traverse(PSTACK);
bool pop(PSTACK, int *);
bool is_empty(PSTACK);
void clear(PSTACK);int main(void)
{STACK S;int val;init(&S);push(&S, 1);push(&S, 3);push(&S, 5);traverse(&S);if(pop(&S, &val))printf("出栈成功，出栈的值是%d\n", val);elseprintf("出栈失败\n");traverse(&S);clear(&S);if(pop(&S, &val))printf("出栈成功，出栈的值是%d\n", val);elseprintf("出栈失败\n");traverse(&S);return 0;
}//初始化
void init(PSTACK pS)
{pS->pTop = (PNODE)malloc(sizeof(NODE));if(NULL == pS->pTop){printf("动态内存分配失败\n");exit(-1);}else{pS->pBottom = pS->pTop;pS->pTop->pNext = NULL;}return;
}//压栈
void push(PSTACK pS, int val)
{PNODE pNew = (PNODE)malloc(sizeof(NODE));if(NULL == pNew){printf("动态内存分配失败\n");exit(-1);}pNew->data = val;pNew->pNext = pS->pTop;  //不能写成pNew->pNext = pS->pBottom; 第一次压栈不会出错，后面就会出错pS->pTop = pNew;return;
}//遍历
void traverse(PSTACK pS)
{PNODE p = pS->pTop;while(p != pS->pBottom){printf("%d ", p->data);p = p->pNext;}printf("\n");return;
}//判断栈是否为空
bool is_empty(PSTACK pS)
{if(pS->pTop == pS->pBottom)return true;elsereturn false;
}//出栈
bool pop(PSTACK pS, int *pval)
{if(is_empty(pS))return false;else{PNODE r = pS->pTop;*pval = r->data;pS->pTop = r->pNext;free(r);r = NULL;return true;}
}//清空
void clear(PSTACK pS)
{if(is_empty(pS))return;else{PNODE p = pS->pTop;PNODE q = NULL;while(p != pS->pBottom){q = p->pNext;free(p);p = NULL;p = q;}pS->pTop = pS->pBottom;}
}

参考资料

[1]数据结构–郝斌link.