栈是线性结构的常见应用,是一种可以实现"先进后出"的存储结构,🌰:让我们想一下箱子📦,往📦里面放东西,最先放入📦中的东西被放在底部,后放入的反而在上面,假设我们从上至下的拿东西,那么就是先放入的后出,后放入的先出,即这就是一个"先入后出"的存储结构。
栈的应用非常的广泛:函数调用、中断、表达式求值、内存分配、缓存、迷宫都有应用栈的知识。
栈和队列实现虽然不同,但都可以通过数组和链表实现,栈分为静态栈和动态栈,静态栈有数组构成,动态栈有链表构成。
其中的核心操作就是:压栈和出栈。压栈就是放入栈中,出栈就是拿出栈中。下面我们看看栈的基本结构:
栈顶Top 栈底Bottom
👇 👇
[data|next]——>[data|next]——>[data=NULL|next]——> NULL
确认一个栈只需要两个参数,栈顶Top和栈底Bottom,初始创建时,栈顶Top等于栈底Bottom;压栈时,栈顶Top移动;出栈时,还是栈顶Top移动。
#C语言栈实现
首先我们先来做好初始化的准备:
// 链表元素结构体
typedef struct Node {
int data;
struct Node * next;
}Node, *pNode;
// 栈的参数
typedef struct Stack {
pNode pTop; // 栈顶
pNode pBottom; // 栈底
}Stack, *pStack;
// 初始化
void initStack(pStack s);
// 压栈
void pushStack(pStack s, int value);
// 遍历
void traverseStack(pStack s);
// 出栈
bool popStack(pStack s);
以上就是栈的基本操作,下面是函数的实现
// 初始化
void initStack(pStack s) {
s->pTop = (pNode)malloc(sizeof(Node));
if(s->pTop == NULL) {
printf("内存分配失败");
exit(-1);
}
s->pBottom = s->pTop;
s->pTop->next = NULL;
}
// 压栈
void pushStack(pStack s, int value){
pNode pNew = (pNode)malloc(sizeof(Node));
if(pNew == NULL) {
printf("内存分配失败");
exit(-1);
}
s->pTop = pNew;
pNew->data = value;
pNew->next = s->pBottom;
}
// 遍历
void traverseStack(pStack s){
pNode top = s->pTop;
while(top->next != NULL){
peintf("%d\n", top->data);
top = top->next;
}
}
// 出栈
bool popStack(pStack s){
pNode node = s->pTop;
if(node->next != NULL){
return false;s
}
s->pTop = s->pTop->next;
free(node);
retrun false;
}
main函数中创建调用栈:
int main() {
// 创建栈
Stack s;
initStack(&s);
pushStack(&s, 1);
pushStack(&s, 2);
pushStack(&s, 3);
pushStack(&s, 4);
traverseStack(&s);
popStack(&s);
traverseStack(&s);
return 0;
}
参考:
参考更多博文: