顺序栈的实现（利用数组实现）
2016-02-29 20:20阅读：
顺序栈的实现（数组实现、C语言）
转载▼
在数据结构中，栈是一中特殊的ADT（抽象数据类型）。它的特殊性在于它的操作只能在一个位置进行，无论是入栈还是出栈。这个位置是表的末端，也叫做栈顶。栈是操作受限的线性表。栈在计算机科学中几乎无处不在，是一中非常重要的数据结构。
用数组实现栈代码简单，但是也有缺点，那就是必须提前声明一个数组的大小，并且在程序的运行过程中不能改变，这在一定程度上限制了栈的灵活性，但是却带来了更为简洁的代码。数组的下标为0我们表示栈空。
#include
#include
#define STACK_SIZE
100
//栈的节点声明
typedef struct Stack{
int
top;
int
array[STACK_SIZE];
}Stack;
Stack
S;//定义一个栈
//初始化一个空栈
int
Init_Stack(){
S.top =
0;//top为0表示空栈
return
1;
}
//测试是否为空栈
int
IsEmpty(){
if(S.top==0)return
1;
else return
0;
}
//元素e入栈
int Push(int
e){
S.top++;
S.array[S.top] =
e;
return
S.top;
}
//出栈,并返回该元素值
int
Pop(){
S.top--;
return
S.array[S.top+1];
}
void
main(){
int
i=0,j=0;
Init_Stack();
for(;i<=5;i++){
Push(i);
}
for(i=0;i<=5;i++){
j =
Pop();
printf('[%d]
',j);
}
getch();
}
栈的基本操作实现后，我们来看下利用栈的一个小题目。编写程序，识别以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和2都不含‘&’字符，且序列1和序列2互为逆序列。这其实就是利用栈的Pop()操作。代码如下：
#include
#include
#define STACK_SIZE
200
#define
EleType
char
//栈的节点声明
typedef struct
Stack{
EleType
top;
EleType
array[STACK_SIZE];
}Stack,*pStack;
//初始化一个空栈
int Init_Stack(pStack
S){
S->top =
0;//top为0表示空栈
return
1;
}
//测试是否为空栈
int IsEmpty(pStack
S){
if(S->top==0)return
1;
else return
0;
}
//元素e入栈
int Push(pStack
S,EleType e){
S->top++;
S->array[S->top] =
e;
return
S->top;
}
//出栈,并返回该元素值
EleType Pop(pStack
S){
S->top--;
return
S->array[S->top+1];
}
void
main(){
int
i=0;
pStack
S;
char
a[]='abc&cba@';
char
b[]='fgh&hgf@';
S =
(pStack)malloc(sizeof(Stack));
Init_Stack(S);
while(b[i]!='@'){
Push(S,b[i]);
i++;
}
i=0;
for(;i<=6;i++){
