栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。
栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
注意:数据结构中的栈和我们C语言中的栈有什么关系吗?
前者是一种数据结构,用来存储数据。后者是操作系统中内存划分的一个区域,叫做栈,用来函数调用时,建立栈帧。
问:当入栈顺序是1 2 3 4的时候,出栈顺序一定是4 3 2 1吗?
答:不一定是,因为有可能是1入栈之后接着就出栈了,2、3、4也同样如此,此时的出栈顺序是1 2 3 4。实际上是有很多种出栈方式,后进先出是相对的。
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
栈的代码实现:
第一种:数组栈的实现(推荐)
Stack.h文件代码:
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;//栈顶的位置
int capacity;//容量
}ST;
void StackInit(ST*ps);
void StackDestory(ST* ps);
void StackPush(ST* ps,STDataType x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int SizeStack(ST* ps);
STDataType StackTop(ST* ps);
Stack.c文件代码:
#include"Stack.h"
void StackInit(ST* ps)//栈的初始化
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackDestory(ST*ps)//栈的销毁
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity =ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)//满了进行扩容
{
int newCapacity = ps->capacity == 0 ? 2 : 2 * ps->capacity;
STDataType*new = (STDataType*)realloc(ps->a,sizeof(STDataType)*newCapacity);
if (new == NULL)
{
printf("fail malloc\n");
exit(-1);
}
ps->a = new;
ps->capacity = newCapacity;
}
ps->a[ps->top++] = x;
}
void StackPop(ST* ps)//出栈
{
assert(ps);
assert(ps->top > 0);
--ps->top;
}
bool StackEmpty(ST* ps)//判断栈是否为空
{
assert(ps);
return ps->top == 0;
}
STDataType StackTop(ST* ps)//取栈顶元素
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
int SizeStack(ST* ps)//求栈的元素数量
{
assert(ps);
return ps->top;
}
第二种:链表栈的实现
链表栈的实现在此处是运用了单链表(有哨兵位)作为载体,入栈的位置采取的是单链表的头部,即哨兵位的后面的位置,出栈出的也是哨兵位后面的节点。
Stack.h文件代码:
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct StackNode
{
STDataType val;
struct StackNode* next;
}StackNode;
StackNode* StackInit();
void StackDestory(StackNode* ps);
void StackPush(StackNode* ps,STDataType x);
void StackPop(StackNode* ps);
bool StackEmpty(StackNode* ps);
int SizeStack(StackNode* ps);
STDataType StackTop(StackNode* ps);
StackNode* BuyStackNode(STDataType x);
Stack.c文件代码:
#include"Stack.h"
StackNode* BuyStackNode(STDataType x)//开辟一个栈(链表的)节点
{
StackNode* newnode = (StackNode*)malloc(sizeof(StackNode));
if (newnode == NULL)
{
printf("fail malloc\n");
exit(-1);
}
newnode->next = NULL;
newnode->val = x;
return newnode;
}
StackNode* StackInit()//栈的初始化
{
StackNode* head = BuyStackNode(-1);
return head;
}
void StackDestory(StackNode* ps)//栈的销毁
{
assert(ps);
StackNode* cur = ps;
while (cur)
{
StackNode* next = cur->next;
free(cur);
cur = next;
}
}
void StackPush(StackNode* ps, STDataType x)//入栈
{
assert(ps);
StackNode* newnode = BuyStackNode(x);
StackNode* next = ps->next;
ps->next = newnode;
newnode->next = next;
}
void StackPop(StackNode* ps)//出栈
{
assert(ps);
assert(ps->next);
StackNode* pop = ps->next;
ps->next = pop->next;
free(pop);
}
bool StackEmpty(StackNode* ps)//判断栈是否为空
{
assert(ps);
return ps->next == NULL;
}
int SizeStack(StackNode* ps)//求栈中有的节点的数目
{
assert(ps);
int size = 0;
StackNode* cur = ps->next;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
STDataType StackTop(StackNode* ps)//求栈顶的节点存储的元素
{
assert(ps);
assert(ps->next);
return ps->next->val;
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/m0_57304511/article/details/123818499
内容来源于网络,如有侵权,请联系作者删除!