Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
148 lines (127 sloc) 2.95 KB
/**
* @ProjectName:DynamicStack 动态栈的算法实现(链表栈)
* @Author: MagicDevil.Top (MagicDevil.Zhang@gmail.com)
* @Description: 实现功能:初始化栈、入栈、出栈、清空栈、取栈的大小、打印栈的内容
*/
#include <stdio.h>
#include <windows.h>
#define SUCCESS 1
#define ERROR -1
#define ElemType int
#define StatusType int
typedef struct StackNode
{
ElemType data;
struct StackNode *next;
} StackNode, *Stack;
//1.初始化栈空间
StatusType InitStack(Stack &S)
{
S = (Stack)malloc(sizeof(StackNode));
S->data = NULL;
S->next = NULL;
return SUCCESS;
}
//2.入栈
StatusType PushStack(Stack &S, ElemType content)
{
if (!S || content == ERROR)
{ //但栈未初始化或传入元素不存在返回ERROR
return ERROR;
}
if (!S->data)
{ //覆盖空链表栈
S->data = content;
return SUCCESS;
}
//新建一个新链表存放内容
Stack newstack;
InitStack(newstack);
newstack->data = content;
//将新链表设为头结点连接后续链表
newstack->next = S;
S = newstack;
return SUCCESS;
}
//3.出栈
ElemType PopStack(Stack &S)
{
if (S->next)
{ //未到栈底
Stack outstack = S;
ElemType out = outstack->data;
S = S->next;
free(outstack);
return out;
}
if (S->data)
{ //到达栈底元素时
ElemType out = S->data;
S->data = NULL;
return out;
}
return ERROR;
}
//4.清空栈
StatusType ClearStack(Stack &S)
{
if (S->next)
{
ClearStack(S->next); //遍历所有元素
}
free(S->next); //清空尾巴保留头结点
S->data = NULL;
S->next = NULL;
return SUCCESS;
}
//5.取栈的大小
int getStackNum(Stack &S)
{
if (S->data)
{
return 1 + getStackNum(S->next);
}
return 0;
}
//6.打印栈的内容
StatusType PrintStack(Stack &S)
{
int foot = 0;
int flag = 0;
int num = 0;
Stack stack;
stack = S;
printf("Stack Information\n");
while (flag == 0)
{
if (stack->next == NULL)
{ //当遍历到最后一个元素时退出
flag = 1;
}
num++;
printf(" |- Stack %d : %d\n", foot++, stack->data);
stack = stack->next;
}
printf("Num : %d\n", num);
return SUCCESS;
}
int main(int argc, char const *argv[])
{
Stack stack, q;
InitStack(stack);
InitStack(q);
PushStack(stack, 1);
PushStack(stack, 3);
PushStack(stack, 5);
PushStack(stack, 7);
PrintStack(stack);
PushStack(q, PopStack(stack));
PushStack(q, PopStack(stack));
PushStack(q, PopStack(stack));
PushStack(q, PopStack(stack));
PushStack(q, PopStack(stack));
PrintStack(q);
printf("%d\n", getStackNum(stack));
system("pause");
return 0;
}