数据结构DAY3--栈与队列

栈：

是一种只能从一端操作的表，规则为先进后出。

主要操作步骤为：1.建立相关结构体 2.建立栈 3.增加栈 4.获得栈顶值 5.删除 6.修改 7.销毁 

1.建立两个结构体

一个为链栈，一个为结点，链栈包括栈头（指针）和栈个数，结点包括数据和指向下一个栈的指针

typedef struct node
{
	int data;
	struct node *pnext;
}STACK_NODE;
 
typedef struct stack
{
	STACK_NODE *ptop;
	int clen;
}STACK_LIST;

2.建立栈

首先要建立一个链栈，首先用链栈结构体定义一个大小为结构体大小的指针，使其栈顶指向空，栈个数初始化为0，然后将其返回。

STACK_LIST *create_link_stack()
{
	STACK_LIST *pstack = malloc(sizeof(STACK_LIST));
	if (NULL == pstack)
	{
		perror("fail malloc");
		return NULL;
	}
	
	pstack->ptop = NULL;
	pstack->clen = 0;
 
	return pstack;
}

3.增加栈

首先建立结点，用结点结构体定义一个大小为结构体大小的指针，使其数据域为输入数据，结点的后驱指针指向空，然后将其返回，返回后，使结点的后驱等于栈链的栈顶，栈链的栈顶等于结点，栈个数加1，一个栈就建立好了。

STACK_NODE *create_node(DATA_TYPE data)
{
	STACK_NODE *pnode =  malloc(sizeof(STACK_NODE));
	if (NULL == pnode)
	{
		perror("fail malloc");
		return NULL;
	}
	
	pnode->data = data;
	pnode->pnext = NULL;
 
	return pnode;
}	
 
int push_stack(STACK_LIST *pstack, STACK_NODE *pnode)
{
	if (NULL == pstack || NULL == pnode)
	{
		return -1;
	}
	
	pnode->pnext = pstack->ptop;
	pstack->ptop = pnode;
	
	pstack->clen++;
 
	return 0;
}

4.获得栈顶值：

输入一个指针，以便能从函数中获取数据，使该指针等于链栈的顶的数据域的值即可。

5.删除（出栈）：

其与直接删除不同，其在删除时还会获得删除处的值，所以也要输入一个指针获得数据，首先用结点结构体定义一个结点，使该结点等于栈顶，再使栈顶等于结点的后驱（相当于删除了一个），此时再使指针等于此时栈顶的数据域的值。最后使用free释放结点， 栈个数减一。

int pop_stack(STACK_LIST *pstack, DATA_TYPE *pdata)
{	
	if (NULL == pstack)
	{
		return -1;
	}
	if (is_empty_stack(pstack))
	{
		return -1;
	}
	
	STACK_NODE *pnode = pstack->ptop;
	pstack->ptop = pnode->pnext;
	
	if (pdata != NULL)
	{
		*pdata = pnode->data;
	}
	free(pnode);
 
	pstack->clen--;
 
	return 0;
}

6.销毁 ：

循环出栈，直到链栈头指向空，出栈时不用获取数据。最后再释放链栈空间

void clear_stack(STACK_LIST *pstack)
{
	while (!is_empty_stack(pstack))
	{
		pop_stack(pstack, NULL);
	}
	free(pstack);
}

队列：

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

主要操作步骤为：初始化队列，入队，出队，遍历，销毁队列

初始化队列：

同链表与栈，首先建立两个结构体，一个为队列表头，包括指向对头的指针和指向对尾的指针，以及队列结点的个数。另一个为队列结点，包括数据域以及指向下个结点的指针。

typedef struct node
{
	DATA_TYPE data;
	struct node *pnext;
}QUE_NODE;
 
typedef struct que
{
	QUE_NODE *pfront;
	QUE_NODE *prear;
	int clen;
}QUE_LIST;

入队操作：

首先创建队列表头，用表头结构体定义一个大小为结构体大小的指针，使队头队尾都指向空，队列结点个数尾为0，然后将其返回：

QUE_LIST *create_link_queue()
{
	QUE_LIST *pque = malloc(sizeof(QUE_LIST));
	if (NULL == pque)
	{
		perror("fail malloc");
		return NULL;
	}
 
	pque->pfront = NULL;
	pque->prear = NULL;
	pque->clen = 0;
 
	return pque;
}

其次创建结点，用结点结构体定义一个大小为结构体大小的指针，后驱结点指向空，数据域为输入的数据，并将其返回。

QUE_NODE *create_node(DATA_TYPE data)
{
	QUE_NODE *pnode = malloc(sizeof(QUE_NODE));
	if (NULL == pnode)
	{
		perror("fail malloc");
		return NULL;
	}
	
	pnode->data = data;
	pnode->pnext = NULL;
	return pnode;
}

接着将结点与表头结合：如果是空队列，则使表头的后驱指针与前驱指针都指向结点；如果不是空队列则使表头的后驱结点的指向下一个的指针指向结点，表头的后驱结点也指向结点，最后使队列结点个数加1即可。

int push_queue(QUE_LIST *pque, QUE_NODE *pnode)
{
	if (is_empty_queue(pque))
	{
		pque->prear = pnode;
		pque->pfront = pnode;
	}
	else
	{
	
		pque->prear->pnext = pnode;
		pque->prear = pnode;
	}
	pque->clen++;
 
	return 0;
}

出队操作：

用结点结构体定义一个指针，其等于队列表头的头，队列表头的头等于指针的后驱结点，如果队列表头的头为空，则使其尾也为空，如果数据域不为空，则使传入的数据指针的值为数据域的值。最后释放结点，并使结点个数减一。

int pop_queue(QUE_LIST *pque, DATA_TYPE *pdata)
{
	if (is_empty_queue(pque))
	{
		return -1;
	}
	
	QUE_NODE *pnode = pque->pfront;
	pque->pfront = pnode->pnext;
	if (NULL == pque->pfront)
	{
		pque->prear = NULL;
	}
	if (pdata != NULL)
	{
		*pdata = pnode->data;
	}
	free(pnode);
	pque->clen--;
 
	return 0;
}

遍历：

用结点结构体定义一个指针 ，其值等于队列链表的前驱，只要该结点不为空，就打印其数据域的数据，并使该结点的值为该结点的后驱结点。

销毁：

步骤与栈类似：

void destroy_queue(QUE_LIST *pque)
{
    while (!is_empty_queue(pque))
	{
		pop_queue(pque, NULL);
	}
	free(pque);
}