栈属于数据结构,它本质上属于线性表,只是受限的线性表。
# include <stdio.h>
# include <stdlib.h>
# include <malloc.h>
typedef struct Node
{
int data;
struct Node* pNext;
}NODE, *PNODE;
typedef struct Stack
{
PNODE pTop; //栈顶
PNODE pBottom; //栈底
}STACK, *PSTACK;
//初始化空栈
void InitStack(PSTACK pS)
{
pS->pTop = (PNODE)malloc(sizeof(NODE));
if(NULL == pS->pTop)
{
printf("ERROR \n");
exit(-1);
}
else
{
pS->pBottom = pS->pTop;
pS->pBottom->pNext = NULL;
//pS->pTop->pNext = NULL;
}
}
//遍历栈
void TraverseStack(PSTACK pS)
{
printf("Now start traverse the stack elem : ");
PNODE p = pS->pTop;
while(p != pS->pBottom)
{
printf("%d ", p->data);
p = p->pNext;
}
printf("\n");
}
//压栈
void PushStack(PSTACK pS, int Val)
{
PNODE pNew = (PNODE)malloc(sizeof(NODE));
pNew->data = Val;
pNew->pNext = pS->pTop;
pS->pTop = pNew;
}
//判断栈空
bool IsEmptyStack(PSTACK pS)
{
if(pS->pTop == pS->pBottom)
{
return true;
}
else
{
return false;
}
}
//出栈
int PopStack(PSTACK pS, int * pVal)
{
if(IsEmptyStack(pS))
{
printf("ERROR stack is empty \n");
exit(-1);
}
else
{
PNODE r = pS->pTop;
*pVal = r->data;
pS->pTop = r->pNext;
free(r);
r = NULL;
}
return true;
}
//清空栈
void ClearStack(PSTACK pS)
{
printf("Now start clear the stack ... ");
if(IsEmptyStack(pS))
{
return ;
}
PNODE p = pS->pTop;
PNODE q = NULL;
while(p != pS->pBottom)
{
q = p->pNext;
free(p);
p = q;
}
pS->pTop = pS->pBottom;
puts("\n");
}
//主程序
int main(void)
{
STACK S;
InitStack(&S);//造成一个空栈
//压栈
PushStack(&S, 1);
PushStack(&S, 2);
PushStack(&S, 3);
PushStack(&S, 4);
//遍历
TraverseStack(&S);
//弹出栈顶元素
int val = 0;
if(PopStack(&S, &val))
{
printf("pop stack top elem is %d \n\n", val);
}
//遍历
TraverseStack(&S);
//清空栈
ClearStack(&S);
//遍历
TraverseStack(&S);
return 0;
}