在数据结构中,栈是重要的一种,对于栈,我们知道它有后进先出的特。它是特殊的线性结构,具有线性表的特点:每个元素只有一个前驱元素和一个后继元素(第一个和最后一个除外),但在操作上和线性表不同,栈是一种受限制的线性表,只允许在栈的一端进行插入和删除。内存分配中的栈是操作系统根据数据结构的栈思想而在内存上封装的一种数据结构。 两者不是同一个哦!
我们看看栈的操作:
InitStack(&s):栈的初始化操作。就像建房子,打地基。
StackEmpty(s):判断栈是否为空。
GetTop(*s,&e):返回栈顶元素给元素e。
PushStack(&s,e)在栈中插入元素e。
PopStack(&s,e):弹出栈顶元素e。
StackLength(s):返回栈的长度
CleanStack:清除栈的元素。
栈,有两种存储结构-顺序存储和链表存储。其中的链表存储就需要你对链表有详细的了解了,链表的使用很频繁,因此我们最好能掌握它。我就不详细写了。
下面我们通过括号配对来理解栈的运行机制。假设给我们三种括号:圆括号,花括号,方括号。我们需要给它进行配对,便用栈来实现,这也算是经典的例子了。
我们来分析下,检验括号,我们可以设置一个栈,每读入一个括号,如果是左括号我们把它放进栈,如果读入的是右括号,而且当前的左括号是在栈顶,我们将左括号弹出出栈,进行配对。对于栈,它并不像链表是双向的,只能在一段进行操作,若为栈顶,栈中的元素才能弹出。如果我们读入的不是左括号,就不能配对。如果输入的序列已经读完了,而栈中仍然有等待配对的左括号,则该括号不能配对。
看看程序实现代码:
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#include "string.h"
typedef char DataType;//DataType为char的类型别名;
#include "LinkStack.h" //包含栈链的实现文件及操作
int Match(DataType e,DataType ch);//检验括号是否配对的函数
int main()
{
LinkStack s;
char *p;
DataType e;
DataType ch[60];
InitStack(s);//初始化栈;
gets(ch);
p=ch;
while(*p)
{
switch(*p)
{
case ‘(’:
case ‘[’:
case ‘{’:
PushStack(s,*p++);
break;
case ‘)’:
case ‘]’:
case ‘}’:
if(StackEmpty(s))//如果是右括号,说明栈已空,说明不配对
{
printf("缺少左括号\n");
return ;
}
else
{
GetTop(s,&e);//如果栈不为空,读入的是右括号,则取出栈顶的括号
if(Match(e,*p))//将栈顶的括号与读入的括号进行比较
{
PopStack(s,&e);//如果栈顶的括号与读入的括号配对,则栈顶括号出栈
}
else
{
printf("左右括号不配对\n");
return ;
}
}
default;
p++;//如果是其他字符,则不处理,直接将p指向下一个字符
}
}
}
int Match(DataType e,DataType ch)
{
if(e=‘('&&ch==‘)’)
return 1;
else if(e=‘['&&ch==‘]’)
return 1;
else if(e=‘{'&&ch==‘}’)
return 1;
else
return 0;
}