數據結構–棧

• 2020 年 8 月 23 日
• 筆記
• 數據結構

include<stdio.h>

include<malloc.h>

include<stdlib.h>

typedef struct Node
{
int data;
struct Node * pNext;
}NODE, * PNODE;

typedef struct Stack
{
PNODE pTop;
PNODE pBottom;
}STACK, * PSTACK;

void init(PSTACK);//建立一個空
void push(PSTACK,int);//壓
void traverse(PSTACK);//遍歷輸出
bool empty(PSTACK pS);//判斷棧是否為空
void clear(PSTACK);//清空
bool pop(PSTACK , int *);//出棧

int main(void)
{
int val;//存放出棧元素的值

STACK s;

init(&s);//建立一個空棧

push(&s,1);//壓棧
push(&s,2);
push(&s,3);
push(&s,4);
push(&s,5);
traverse(&s);//遍歷輸出

if(pop(&s,&val))
{
	printf("出棧成功,出棧的值為:%d.\n",val);
}
else
{
	printf("出棧失敗!\n");
}

traverse(&s);//遍歷輸出

clear(&s);//清空
traverse(&s);//遍歷輸出



return 0;

}

//出棧
bool pop(PSTACK pS, int * pVal)
{
if(empty(pS))
return false;
else
{
PNODE p = pS->pTop;
*pVal = p->data;
pS->pTop = p->pNext;
free(p);
p = NULL;

	return true;
}

}

//清空
void clear(PSTACK pS)
{
if(empty(pS))
return;
else
{
PNODE p = pS->pTop ;
PNODE q = NULL;

	while(NULL != p)
	{
		q = p->pNext;
		free(p);
		p = q;
	}
	
	pS->pTop  =  pS->pBottom;
}
return;

}

//遍歷輸出
void traverse(PSTACK pS)
{
PNODE p = pS->pTop;

if(pS->pBottom == pS->pTop)
	printf("棧為空!\n");

else
{
	printf("棧的值為: ");
	
	while(pS->pBottom != p)
	{
		printf("%d,",p->data);
		p = p->pNext ;
		
	}
	
	printf("\n");
	
}

return;

}

//判斷棧是否為空
bool empty(PSTACK pS)
{
if(pS->pBottom == pS->pTop )
return true;
else
return false;
}

void push(PSTACK pS,int val)
{
PNODE pNew = (PNODE)malloc(sizeof(NODE));

if(NULL == pNew)
{
	printf("記憶體分配失敗,終止程式!\n");
	exit(-1);
}

pNew->data = val;

pNew->pNext = pS->pTop;
pS->pTop = pNew;

return;

}

//建立一個空
void init(PSTACK pS)
{
pS->pTop = (PNODE)malloc(sizeof(NODE));

if(NULL == pS->pTop)
{
	printf("記憶體分配失敗,程式終止!\n");
	exit(-1);
}

else
{
	pS->pBottom = pS->pTop;
	pS->pTop->pNext = NULL;	
}


return;

}