王道数据结构:栈顺序存储和链式存储以及基本操作的实现(C语言版)
程序员文章站
2022-06-05 14:47:26
...
栈
只允许在一端进行插入或删除操作的线性表。
对于n个不同元素进栈,出栈序列的个数为(卡特兰数)
顺序栈基本操作的实现代码如下:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MaxSize 10
//栈的顺序存储
typedef struct {
int data[MaxSize];
int top;
}SqStack;
//初始化栈
void InitStack(SqStack &s){
s.top=-1;
for(int i=0;i<10;i++){
s.data[i]=0;
}
printf("初始化完毕\n");
}
//判空
void StackEmpty(SqStack s){
if(s.top==-1){
printf("栈为空\n");
}else{
printf("栈不为空\n");
}
}
//入栈
bool Push(SqStack &s,int e){
if(s.top==MaxSize-1){
printf("栈已满\n");
return false;
}
s.data[++s.top]=e;
return true;
}
//出栈
bool Pop(SqStack &s,int &e){
if(s.top==-1){
printf("栈已空\n");
return false;
}
e=s.data[s.top--];
printf("出栈栈顶元素,值为%d\n",e);
return true;
}
//获取栈顶元素
bool GetTop(SqStack &s,int &x){
if(s.top==-1){
printf("栈为空\n");
return false;
}
x=s.data[s.top];
printf("栈顶元素为:%d\n",x);
return true;
}
//打印栈
void PrintStack(SqStack s){
if(s.top==-1){
for(int i=0;i<10;i++){
//printf("| |\n");
printf("|_ _ _ _|\n");
}
}
if(s.top!=-1){
for(int i=0;i<MaxSize-s.top;i++){
printf("|_ _ _ _|\n");
}
while(s.top!=-1){
printf("|___%d___|\n",s.data[s.top]);
s.top--;
}
}
}
int main(){
SqStack s;
InitStack(s);
StackEmpty(s);
Push(s,1);
Push(s,2);
Push(s,3);
Push(s,4);
StackEmpty(s);
PrintStack(s);
int e,x;
Pop(s,e);
PrintStack(s);
GetTop(s,x);
}
代码运行截图如下:
链式栈基本操作的实现代码如下:
#include <stdio.h>
#include <stdlib.h>
//栈的链式存储
typedef struct Linknode{
int data;
struct Linknode *next;
}Linknode,*LiStack;
//初始化栈
void InitStack(LiStack &L){
L =(Linknode*)malloc(sizeof(Linknode));//创建头节点
L->next=NULL;//初始化为空
}
//栈判空
bool StackEmpty(LiStack L){
if(L->next==NULL){
printf("栈为空\n");
return false;
}
else{
printf("栈不为空\n");
return true;
}
}
//入栈
bool Push(LiStack &L,int e){
Linknode *s=(Linknode *)malloc(sizeof(Linknode));
s->data=e;
s->next=L->next;
L->next=s;
return true;
}
//出栈
bool Pop(LiStack &L,int &e){
if(L->next==NULL){
printf("栈已空\n");
return false;
}
Linknode *p=L->next;
e=p->data;
L->next=p->next;//成链
printf("出栈元素值为%d\n",e);
free(p);
return true;
}
bool GetTop(LiStack L,int x){
if(L->next==NULL){
printf("栈已空\n");
return false;
}
Linknode *p=L->next;
x=p->data;
printf("栈顶元素值为%d\n",x);
return true;
}
void PrintStack(LiStack L){
Linknode *n=L->next;
while(n!=NULL){
printf("|___%d___|\n",n->data);
n=n->next;
}
}
int main(){
LiStack s;
InitStack(s);
StackEmpty(s);
Push(s,1);
Push(s,2);
Push(s,3);
Push(s,4);
StackEmpty(s);
PrintStack(s);
int e,x;
Pop(s,e);
PrintStack(s);
GetTop(s,x);
}
代码运行截图如下: