【数据结构】栈的实现

栈可以看做是链表的一种特殊形式，是在链表上加不同的约束条件实现的。

# 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 pop(PSTACK,int*);

int main(void){
	STACK S;//STACK 等价于 struct Stack

	init(&S);
	push(&S,1);
	push(&S,2);
	//traverse(&S);
	system("Pause");
	return 0;
}

int 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;
	}
}

void push(PSTACK pS,int val){
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	pNew->data = val;
	pNew->pNext = pS->pTop;
	pS->pTop = pNew;
}

void traverse(PSTACK pS){
	PNODE p = pS->pTop;

	while (p!=pS->pBottom){
		printf("%d",p->data);
		p = p->pNext;
	}
	printf("n");
	
}

bool empty(PSTACK pS){
	if (pS->pTop == pS->pBottom){

		return true;
	}
	return false;
}

bool pop(PSTACK pS,int *val){
	PNODE	r;
	if (!empty(pS)){
		r = pS->pTop;
		*val = r->data;
		pS->pTop = pS->pTop->pNext;
		free(r);
		r = NULL;
		return true;
	}
	return false;
}

void clear(PSTACK pS){
	if (empty(pS)){
		return ;
	}
	else{
		PNODE p = pS->pTop;
		PNODE q = NULL;
		while ( p !=pS->pBottom){
			q = p->pNext;
			free(p);
			p = q;
		}
		pS->pTop = pS->pBottom;
	}
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!