概念
栈 里面的内容可以是任意数据类型
遵循先入后出、FILO (firts input last ouput)
只能访问最顶层的数据，进行“入栈”和“出栈”
栈操作： 入栈 出栈 判断栈是否为空
需要一个指针，一直指向栈顶
代码实现：
#include <stdio.h>
char stack[512]; //定义一个栈
int top = 0; //栈顶的位置
void push(char c);
char pop(void);
int is_empty(void);
int main(void)
{
char ss;
push('a');
push('b');
push('c');
while(!is_empty())
{
putchar(pop()); //输出c\n b\n a\n
printf("\n");
}
return 0;
}
//入栈
void push(char c)
{
stack[top++] = c;
}
//出栈
char pop (void)
{
return stack[--top];
}
//判断是否为空 空为1 非空0
int is_empty(void)
{
return top == 0;
}
栈的应用
1.逆波兰表示法：
12+ 34- *
中缀表示：（1+2）*（3-4） 处理步骤：
1入栈；
2入栈；
+连续两次出栈 相加结果入栈；
3入栈；
4入栈；
-连续两次出栈 相减结果入栈；
*连续两次出栈 相乘结果入栈 就是最终结果了（完美）
5*（（（9+8）*（4*6））+7）人脑可以处理这样的括号，从而判断数据，但电脑就难了
所以用逆波兰表示法，
5（（（9+8）*（4*6））+7）*
5（（9+8）*（4*6））7+*
5（9+8）（4*6）*7+*
598+46**7+*
处理步骤：
5入栈；9入栈；8入栈；+连续两次出栈8 9 相加结果17入栈；
4入栈；6入栈；*连续两次出栈4 6 相乘24结果入栈；
*连续两次出栈17 24 相乘结果408入栈；
7入栈；+连续两次出栈408 7 相加结果415入栈；
*连续两次出栈5 415 相乘结果2075入栈 就是最终结果了；
代码实现：
#include <stdio.h>
#include <string.h>
int stack[512]; //定义一个栈
int top = 0; //栈顶的位置
void push(int c);
int pop(void);
int is_empty(void);
int main(void)
{
char a[100];
int n,i,n1,n2;
printf("please enter a reverse olish expression:\n");
gets(a);
n = strlen(a);
for(i = 0;i < n; i++)
{
//0-9的数字入栈
if((a[i] >= '0') && (a[i]<= '9'))
{
push(a[i] - '0');
}//符号的话 开始计算
else
{
n2 = pop();
n1 = pop();
switch (a[i])
{
case '+': push(n1+n2);
break;
case '-': push(n1-n2);
break;
case '*': push(n1*n2);
break;
}
}
}
printf("result = %d",pop());
return 0;
}
//入栈
void push(int c)
{
stack[top++] = c;
}
//出栈
int pop (void)
{
return stack[--top];
}
//判断是否为空 空为1 非空0
int is_empty(void)
{
return top == 0;
}
2.中缀表示法 转 后缀表示法
- 仍然从左到右处理数据
- 当遇到左括号时，忽略它
- 当遇到数值时，直接输出
- 当遇到操作符时，将操作符入栈
- 当遇到右括号时，出栈栈顶的操作符
中缀表示：（（1+2）*（3-4）） 需要补充一对括号
后缀表示： 12+ 34- *
（左括号忽略；（左括号忽略；
1直接输出 1；
+入栈； 1；
2直接输出 12；
）右括号，栈顶出栈 12+；*入栈；
（左括号忽略；3输出 12+3；-入栈;4出栈 12+34；）右括号栈顶出栈 12+34-；右括号栈顶出栈 12+34-*；
代码实现：
#include <stdio.h>
#include <string.h>
int stack[512]; //定义一个栈
int top = 0; //栈顶的位置
void push(int c);
int pop(void);
int is_empty(void);
int main(void)
{
char a[100];
int n,i,n1,n2;
printf("please enter a reverse olish expression:\n");
gets(a);
n = strlen(a);
for(i = 0;i < n; i++)
{
//0-9的数字入栈
if((a[i] >= '0') && (a[i]<= '9'))
{
push(a[i] - '0');
}//符号的话 开始计算
else
{
n2 = pop();
n1 = pop();
switch (a[i])
{
case '+': push(n1+n2);
break;
case '-': push(n1-n2);
break;
case '*': push(n1*n2);
break;
}
}
}
printf("result = %d",pop());
return 0;
}
//入栈
void push(int c)
{
stack[top++] = c;
}
//出栈
int pop (void)
{
return stack[--top];
}
//判断是否为空 空为1 非空0
int is_empty(void)
{
return top == 0;
}
3.括号匹配
((1+2)*(3-4)) 左右括号的匹配
1 5
7 11
0 12
代码实现
#include <stdio.h>
#include <string.h>
int stack[512]; //定义一个栈
int top = 0; //栈顶的位置
void push(int c);
int pop(void);
int is_empty(void);
int main(void)
{
char str[100];
int i,len;
printf("please enter a calculate expression:");
gets(str);
len = strlen(str);
for (i = 0; i < len; i++)
{
if (str[i] == '(')
{
push(i);
}
else if(str[i] == ')')
{
printf("%d %d\n",pop(),i);
}
}
return 0;
}
//入栈
void push(int c)
{
stack[top++] = c;
}
//出栈
int pop (void)
{
return stack[--top];
}
//判断是否为空 空为1 非空0
int is_empty(void)
{
return top == 0;
}
4.十进制转换二进制
13 ——》1101 转换步骤
- 判断n是不是为0（n!=0），n%2，更新n的值（n=n/2）
- 重复第一步操作，知道运行到n=0时为止
- 只有栈不为空，就弹出栈顶内容
13不为0，13%2=1，13/2=6;
6不为0，6%2=0，6/2=3;
3不为0，3%2=1，3/2=1;
1不为0，1%2=1，1/2=0;
0终止；倒取余数1101，正好符合压栈的顺序
代码实现
#include <stdio.h>
#include <string.h>
int stack[512]; //定义一个栈
int top = 0; //栈顶的位置
void push(int c);
int pop(void);
int is_empty(void);
int main(void)
{
int num;
int i;
printf("please enter an integer in decimal:");
scanf("%d",&num);
while(num)
{ //1.判断n是不是为0（n!=0），n%2，更新n的值（n=n/2）
push(num%2);
num /= 2;
} //2.重复第一步操作，知道运行到n=0时为止
while (!is_empty())
{ //3.只有栈不为空，就弹出栈顶内容
printf("%d",pop());
}
printf("\n");
return 0;
}
//入栈
void push(int c)
{
stack[top++] = c;
}
//出栈
int pop (void)
{
return stack[--top];
}
//判断是否为空 空为1 非空0
int is_empty(void)
{
return top == 0;
}
5. 回文判定
abba ab ba
abcdcda aba d cba
算法流程
-
求出字符串的长度，将前一半的字符依次入栈
-
如果栈不为空，就出栈栈顶元素，将其与后半部分的字符串进行比较
-
如果字符串的长度是奇数，要跳过中心点的元素，比较中心点后面的元素
如果比较的元素是相等的，就一直比较，直到栈为空
如果比较不等，立刻停止比较，返回"非回文"
代码实现
#include <stdio.h>
#include <string.h>
char stack[512]; //定义一个栈
int top = 0; //栈顶的位置
int is_palindrom(char* pt);
void push(char c);
char pop(void);
int is_empty(void);
int main(void)
{
char str[100];
printf("please enter a string:");
gets(str);
if (is_palindrom(str))
{
printf("str is apalindrom.\n");
}
else
{
printf("str is not apalindrom.\n");
}
return 0;
}
//入栈
void push(char c)
{
stack[top++] = c;
}
//出栈
char pop (void)
{
return stack[--top];
}
//判断是否为空 空为1 非空0
int is_empty(void)
{
return top == 0;
}
int is_palindrom(char* pt)
{
int i,len;
//1.将求出字符串的长度,将前一半的字符依次入栈
len = strlen(pt);
for (i = 0; i < (len/2); i++)
{
push(pt[i]);
}
//2.如果栈不为空，就出栈栈顶元素，将其与后半部分的字符串进行比较
//3.如果字符串的长度是奇数，要跳过中心点的元素，比较中心点后面的元素
if (len % 2 == 1)
{ //此时i是字符串前一半最后一个元素的序号
i++;
}
while (!is_empty())
{ //如果比较的元素是相等的，就一直比较，直到栈为空
if(pop() == pt[i])
{
i++;
}
else
{ //如果比较不等，立刻停止比较，返回"非回文"
return 0;
}
return 1;
}
}