c语言实现链式栈
程序员文章站
2022-05-26 19:40:27
...
C语言实现链式栈
定义
定义不多说了 百度百科找了两张图片图片(侵删)
思路
代码的关键在于“先进后出”因为我们用链表实现,所以很容易想到,采用头插入办法保证“先进后出”,只需要关心第一个结点就行,入栈出栈都是针对它,毕竟找链表的尾巴很费事︿( ̄︶ ̄)︿,如果我们还要知道栈的长度什么的可以在struct中加一个len字段,出入栈的时候记录一下就行
代码也没有什么特别好解释的直接上代码吧(参考链表的实现更加简单)
代码
#include<stdio.h>
#include<stdlib.h>
typedef int dataType;
typedef struct Node
{
dataType data;
struct Node *next;
}NODE,*PNODE;
typedef struct LinkStack
{
PNODE top; //栈顶指针
}LINKSTACK,*PLINKSTACK;
PLINKSTACK createEmptyStack(); //创建一个空栈
bool isEmptyStack(PLINKSTACK s); //判断是否为空栈
bool push(PLINKSTACK s, dataType x); //入栈
bool pop(PLINKSTACK s); //出栈
void showStack(PLINKSTACK s); //打印所有
dataType getTop(PLINKSTACK s); //获取top
void setEmpty(PLINKSTACK s); //置空
void destory(PLINKSTACK s); //销毁
PLINKSTACK createEmptyStack()
{
PLINKSTACK s = (PLINKSTACK)malloc(sizeof(LINKSTACK));
if(s == NULL)
{
printf("内存分配失败\n");
}
else
{
s->top = NULL;
}
return s;
}
bool isEmptyStack(PLINKSTACK s)
{
return (s->top == NULL);
}
bool push(PLINKSTACK s,dataType x)
{
PNODE p = (PNODE)malloc(sizeof(NODE));
if(p == NULL)
{
printf("结点分配失败\n");
return false;
}
else
{
p->data = x;
p->next = s->top; //链表的下一个结点指向之前的top 第一次为NULL
s->top = p; //把top指针指向新的结点p
return true;
}
}
bool pop(PLINKSTACK s)
{
if(isEmptyStack(s))
{
printf("stack is empty\n");
return false;
}
PNODE p = s->top;
printf("pop: %d \n",p->data);
s->top = p->next;
free(p);
p = NULL;
return true;
}
void showStack(PLINKSTACK s)
{
if(isEmptyStack(s))
{
printf("stack is empty\n");
return ;
}
else
{
PNODE p = s->top;
printf("---\n");
while(p != NULL)
{
printf("%d \n",p->data);
p = p->next;
}
printf("---\n");
}
}
dataType getTop(PLINKSTACK s)
{
if(isEmptyStack(s))
{
printf("stack is empty\n");
return NULL;
}
else
{
return s->top->data;
}
}
void setEmpty(PLINKSTACK s)
{
if(isEmptyStack(s))
{
printf("stack is empty");
return ;
}
//释放掉链表 (其实就是没有头结点单链表的销毁)
PNODE p = s->top;
PNODE temp = NULL;
while(p != NULL)
{
temp = p->next;
free(p);
p = temp;
}
//置空
s->top = NULL;
}
void destory(PLINKSTACK s)
{
setEmpty(s);
free(s);
s = NULL;
}
int main()
{
PLINKSTACK stack = createEmptyStack();
push(stack,1);
push(stack,2);
push(stack,3);
showStack(stack);
pop(stack);
showStack(stack);
printf("top :%d\n", getTop(stack));
printf("setEmpty……\n");
setEmpty(stack) ;
showStack(stack);
printf("destroy…… \n");
destory(stack);
return 0;
}