栈操作C语言实现

2018-02-11 14:02:38来源:http://www.52murong.com/post/stackc作者:52coder人点击

分享

栈是一种限制线性列表,该类列表的添加和删除操作只能在一端实现,称为栈顶。栈的实现可以使用数组也可以使用链表来实现。


下面的C语言部分实现了顺序栈的基本操作,包括栈的初始化、入栈、出栈、获得栈顶元素的值等。
#include <stdio.h>
#include <stdbool.h>
/*定义栈的大小*/
#define maxsize 100
typedef int ElemType;
/*顺序栈的实现*/
typedef struct SqStack
{
ElemType data[maxsize];
int top;
}SqStack;
/*栈的初始化*/
void initstack(SqStack * s)
{
if(NULL == s)
return;
s->top = -1;
}
/*判断栈空*/
bool stackempty(SqStack *s)
{
if(NULL == s)
return true;
if(-1 == s->top)
return true;
else
return false;
}
/*判断栈满*/
bool stackfull(SqStack *s)
{
if(NULL == s)
return false;
if(s->top >= maxsize-1)
return true;
else
return false;
}
/*入栈操作*/
void push(SqStack *s,ElemType x)
{
if(stackfull(s))
return;
s->top += 1;
s->data[s->top] = x;
}
/*出栈操作*/
int pop(SqStack *s,ElemType *x)
{
if(stackempty(s))
return -1;
*x = s->data[s->top];
s->top--;
return 0;
}
/*获取栈顶元素*/
int gettop(SqStack *s,ElemType *x)
{
if(stackempty(s))
return -1;
*x = s->data[s->top];
return 0;
}
/*清空栈*/
void clearstack(SqStack *s)
{
if(stackempty(s))
return;
s->top = -1;
}
int main(int argc, const char * argv[])
{
SqStack s;
ElemType x = 0;
initstack(&s);
if(s.top != -1)
printf("error");
/*入栈100个元素*/
for(int i = 0;i < 100;i++)
push(&s,i);
/*判断此时栈满*/
if(!stackfull(&s))
printf("error");
/*出栈,打印栈顶元素值*/
for(int i = 0;i < 100;i++)
{
pop(&s,&x);
printf("%d ",x);
/*每行打印10个元素*/
if(0 == (i+1)%10)
printf("/n");
}
/*判断此时栈满*/
if(!stackempty(&s))
printf("error");
return 0;
}

上面的实现是使用数组来实现栈,有一个明显的缺陷是栈的大小在开始时就已经确定,无法扩展。可以使用realloc函数对上述代码进行修改.


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/*定义栈的初始大小*/
#define STACK_INITSIZE 100
/*定义增幅*/
#define STACK_INCREMENT100
typedef int ElemType;
int realsize = STACK_INITSIZE;
/*顺序栈的实现*/
typedef struct SqStack
{
/*指向申请的内存,用于存储栈数据结构*/
ElemType *data;
int top;
}SqStack;
/*栈的初始化*/
int initstack(SqStack * s)
{
/*入参为NULL,返错*/
if(NULL == s)
return -1;
s->top = -1;
s->data = (ElemType *)malloc(STACK_INITSIZE * sizeof(ElemType));
/*申请内存失败,返错*/
if(NULL == s->data)
return -1;
return 0;
}
/*判断栈空*/
bool stackempty(SqStack *s)
{
if(NULL == s)
return true;
if(-1 == s->top)
return true;
else
return false;
}
/*入栈操作*/
int push(SqStack *s,ElemType x)
{
if(NULL == s)
return -1;
/*栈满,再分配STACK_INCREMENT个元素*/
if(realsize-1 == s->top)
{
realsize += STACK_INCREMENT;
s->data = (ElemType *)realloc(s->data,realsize*sizeof(ElemType));
/*申请内存失败,返错*/
if(NULL == s->data)
return -1;
}
s->top += 1;
s->data[s->top] = x;
return 0;
}
/*出栈操作*/
int pop(SqStack *s,ElemType *x)
{
if(NULL == s)
return false;
if(stackempty(s))
return -1;
*x = s->data[s->top];
s->top--;
return 0;
}
/*获取栈顶元素*/
int gettop(SqStack *s,ElemType *x)
{
if(stackempty(s))
return -1;
*x = s->data[s->top];
return 0;
}
/*清空栈,只是将top设置为-1,没有释放申请的内存*/
void clearstack(SqStack *s)
{
if(stackempty(s))
return;
s->top = -1;
}
void destorystack(SqStack *s)
{
if(NULL == s)
return;
if(s->data != NULL)
free(s->data);
s->top = -1;
}
int main(int argc, const char * argv[])
{
SqStack s;
ElemType x = 0;
initstack(&s);
if(s.top != -1)
printf("error");
/*入栈200个元素*/
for(int i = 0;i < 200;i++)
push(&s,i);
/*出栈,打印栈顶元素值*/
for(int i = 0;i < 200;i++)
{
pop(&s,&x);
printf("%d ",x);
/*每行打印10个元素*/
if(0 == (i+1)%10)
printf("/n");
}
/*判断此时栈空*/
if(!stackempty(&s))
printf("error");
destorystack(&s);
return 0;
}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台