C语言实现栈
MT_125 人气:0一、了解栈的结构特点
栈是一种特殊的线性表，只允许从一端进出数据，称为后进先出，先进后出。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈。出数据也在栈顶
二、具体实现
由于栈实质是一种线性表，因此可以用两种方式来实现：顺序表 或 链表
这里我使用的是类似顺序表的方式来实现。
代码如下：
typedef char Stacktype;
typedef struct Stack
{
int top;
Stacktype* data;
int capacity;
}Stack;
void Stack_init(Stack* pphead); //栈的初始化
void Stack_destory(Stack* pphead); //栈的清空
void Stack_push(Stack* pphead, Stacktype data); //插入数据，压栈
void Stack_pop(Stack* pphead); //出栈（删除数据）
bool Stack_Empty(Stack* pphead); //判断栈是否为空
Stacktype Stack_Top(Stack* pphead); //调出栈顶元素
int Stack_Size(Stack* pphead); //查看数据个数
//栈的初始化
void Stack_init(Stack* pphead)
{
pphead->top = 0;
pphead->capacity = 0;
pphead->data = NULL;
}
//栈的清空
void Stack_destory(Stack* pphead)
{
pphead->top = 0;
pphead->capacity = 0;
free(pphead->data);
pphead->data = NULL;
}
//插入数据，压栈
void Stack_push(Stack* pphead, Stacktype data)
{
assert(pphead);
if (pphead->top == pphead->capacity)
{
int Newcapacity = (pphead->capacity == 0) ? 4 : ((pphead->top) * 2);
Stacktype* temp = NULL;
temp = (Stacktype*)realloc(pphead->data, sizeof(Stacktype) * Newcapacity);
if (temp == NULL)
{
printf("Stack_push");
exit(-1);
}
pphead->data = temp;
pphead->top = Newcapacity;
}
(pphead->data)[pphead->capacity] = data;
pphead->capacity++;
}
//出栈（删除数据）
void Stack_pop(Stack* pphead)
{
assert(pphead);
assert(Stack_Empty(pphead));
pphead->capacity--;
}
//判断栈是否为空
bool Stack_Empty(Stack* pphead)
{
assert(pphead);
return pphead->capacity != 0;
}
//调出栈顶元素
Stacktype Stack_Top(Stack* pphead)
{
assert(pphead);
assert(Stack_Empty(pphead));
return pphead->data[pphead->capacity - 1];
}
//查看数据个数
int Stack_Size(Stack* pphead)
{
assert(pphead);
return pphead->top;
}补充 栈的用处
我们好不容易实现了一个栈，接下来我们来做个题看看栈有什么用吧。
题目描述
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
基础框架
C语言的基础框架如下
bool isValid(char * s){
}
解题思路
左括号一定要和右括号对齐，非常满足栈的特性
我们可以将所有的左括号存入一个栈中。
然后遇到右括号，就出栈，判断是否匹配。
直到栈为空且字符串中的括号也遍历完了，那么所有括号就正确的匹配了。
代码详解
// 1.因为C语言并没有现成的栈，所以我们需要自己造轮子，先写个栈再说
typedef char STDateType; // 更改数据类型为char
typedef struct Stack
{
STDateType* a;
int top;
int capacity;
}Stack;
void StackInti(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->top = 0;
}
void StackPush(Stack* ps, STDateType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = (int*)realloc(ps->a, sizeof(int) * newCapcity);
if (ps->a == NULL)
{
printf("ralloc error");
exit(-1);
}
ps->capacity = newCapcity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
STDateType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
bool isValid(char * s){
Stack a;
StackInti(&a);
while(*s)
{
if (*s == '(' || *s == '[' || *s == '{') //入栈
{
StackPush(&a, *s);
}
else //出栈
{
if(StackEmpty(&a)) //右括号多一个的情况
{
return false;
}
char tmp = StackTop(&a);
StackPop(&a);
if ((*s == ')' && tmp != '(')
||(*s == ']' && tmp != '[')
||(*s == '}' && tmp != '{') )
{
return false;
}
}
s++;
}
return StackEmpty(&a); //防止出现多一个左括号的情况
}
加载全部内容