栈——数据结构——day4

栈的定义

栈是限定仅在一段进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。
栈的插入操作，叫作进栈，也称压栈、入栈。类似子弹入弹夹。
栈的删除操作，叫作出栈，也有的叫作弹栈。如同弹夹中的子弹出夹。

栈的抽象数据类型

头文件

#ifndef __STACK_H__
#define __STACK_H__

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
	int data;
	struct node *pnext;
}STACK_NODE;	

typedef struct list
{
	STACK_NODE *phead;
	int clen;
}STACK_LIST;

extern STACK_LIST *CreatStackList();
extern int PushHeadSTACK(STACK_LIST *plist,int data);
extern int PopHeadSTACK(STACK_LIST *plist,int *data);
extern STACK_NODE *GetTopOfStack(STACK_LIST *plist);
extern int ClearStack(STACK_LIST *plist);
extern void DestoryStack(STACK_LIST *plist);
extern int ErgodicOfStack(STACK_LIST *plist);
extern int StackLength(STACK_LIST *plist);

#endif

栈的初始化

初始化操作，建立一个空栈

STACK_LIST *CreatStackList()
{
	STACK_LIST *p = malloc(sizeof(STACK_LIST));

	p->phead = NULL;
	p->clen = 0;

	return p;
}

销毁

若栈存在，则销毁

void DestoryStack(STACK_LIST *plist)
{
	ClearStack(plist);
	free(plist);
	return ;
}

清空

将栈清空

int ClearStack(STACK_LIST *plist)
{
	if(IsEmptyStack(plist))
	{
		return 0;
	}

	STACK_NODE *p = plist->phead;

	while(p)
	{
		PopHeadSTACK(plist,NULL);
		p = plist->phead;
	}

	return 0;
}

判断栈是否为空

int IsEmptyStack(STACK_LIST *plist)
{
	return NULL == plist->phead;
}

进栈

若栈存在，插入新元素data到栈并成为栈顶元素

int PushHeadSTACK(STACK_LIST *plist,int data)
{
	STACK_NODE *p = malloc(sizeof(STACK_NODE));

	p->pnext = plist->phead;
	p->data = data;

	plist->phead = p;
	plist->clen++;

	return 0;
}

出栈

删除栈顶元素，并用data返回其值

int PopHeadSTACK(STACK_LIST *plist,int *data)
{
	if(IsEmptyStack(plist))
	{
		return -1;
	}
	
	STACK_NODE *p = plist->phead;
	plist->phead = p->pnext;
	if(data != NULL)
	{
		*data = p->data;
	}
		free(p);
	plist->clen--;

	return 0;
}

获取栈顶元素

若栈存在且为空，返回栈顶并获取其指针

STACK_NODE *GetTopOfStack(STACK_LIST *plist)
{
	if(IsEmptyStack(plist))
	{
		return NULL;
	}
	
	STACK_NODE *p = plist->phead;

	return p;
}

栈的长度

返回栈的元素个数

int StackLength(STACK_LIST *plist)
{
	return plist->clen;
}

遍历栈

int ErgodicOfStack(STACK_LIST *plist)
{
	if(IsEmptyStack(plist))
	{
		return 0;
	}
	
	STACK_NODE *p = plist->phead;

	while(p)
	{
		printf("%d ",p->data);
		p = p->pnext;
	}
	
	putchar('\n');

	return 0;
}

栈的应用

四则运算表达式求值

头文件

#ifndef __STACK_H__
#define __STACK_H__

#include<stdio.h>
#include<stdlib.h>
#include<string.h>


typedef struct node
{
	int data;
	struct node *pnext;
}STACK_NODE;

typedef struct list
{
	STACK_NODE *phead;
	int clen;
}STACK_LIST;

extern STACK_LIST *CreatStackList();
extern int PushHeadSTACK(STACK_LIST *plist,int data);
extern int PopHeadSTACK(STACK_LIST *plist,int *data);
extern int GetTopOfStack(STACK_LIST *plist,int *num);
extern int ClearStack(STACK_LIST *plist);
extern void DestoryStack(STACK_LIST *plist);
extern int ErgodicOfStack(STACK_LIST *plist);
extern int StackLength(STACK_LIST *plist);
extern int IsEmptyStack(STACK_LIST *plist);

#endif

main.c

#include "stack.h"

int IsNumChar(char ch)
{
	if(ch >= '0' && ch <= '9')
	{
		return 1;
	}
	return 0;
}

int GetOptLevel(char opt)
{
	switch(opt)
	{
		case '+':
		case '-':
			return 1;
		case '*':
		case '/':
			return 2;
		default:
			printf("opt error\n");
			exit(1);
	}
}

int GetValue(int num1,int num2,int opt)
{
	switch(opt)
	{
	case '+':
		return num1 + num2;
	case '-':
		return num1 - num2;
	case '*':
		return num1 * num2;
	case '/':
		return num1 / num2;
	}
}

int main(void)
{
	char str[1024] = {0};
	
	STACK_LIST *pstacknum = CreatStackList();
	STACK_LIST *pstackopt = CreatStackList();
	if(NULL == pstacknum || NULL == pstackopt)
	{
		return -1;
	}


	printf("Please enter four operations:");
	fgets(str,sizeof(str),stdin);
	str[strlen(str)-1] = '\0';

	char *p = str;
	int num = 0;
	int popOpt;
	int num1,num2,opt;

	while(1)
	{
		if(*p == '\0' && IsEmptyStack(pstackopt))
		{
			break;
		}

		while(IsNumChar(*p))
		{
			num = num * 10 + (*p - '0') ;
			p++;
			if(!IsNumChar(*p))
			{
				PushHeadSTACK(pstacknum,num);
				num = 0;
			}
		}
		

		if(IsEmptyStack(pstackopt))
		{
			PushHeadSTACK(pstackopt,*p);
			p++;
			continue;
		}
		
		GetTopOfStack(pstackopt,&popOpt);
		if(*p != '\0' && GetOptLevel(*p) > GetOptLevel(popOpt))
		{
			PushHeadSTACK(pstackopt,*p);
			p++;
		}
		else
		{
			PopHeadSTACK(pstackopt,&opt);
			PopHeadSTACK(pstacknum,&num2);
			PopHeadSTACK(pstacknum,&num1);
			int res = GetValue(num1,num2,opt);
			PushHeadSTACK(pstacknum,res);
		}

	}
	
	ErgodicOfStack(pstacknum);

	DestoryStack(pstacknum);
	DestoryStack(pstackopt);

	return 0;
}

opera.c

#include "stack.h"

STACK_LIST *CreatStackList()
{
	STACK_LIST *p = malloc(sizeof(STACK_LIST));

	p->phead = NULL;
	p->clen = 0;

	return p;
}

int IsEmptyStack(STACK_LIST *plist)
{
	return NULL == plist->phead;
}

int PushHeadSTACK(STACK_LIST *plist,int data)
{
	STACK_NODE *p = malloc(sizeof(STACK_NODE));


	p->pnext = plist->phead;
	p->data = data;

	plist->phead = p;
	plist->clen++;

	return 0;
}

int PopHeadSTACK(STACK_LIST *plist,int *data)
{
	if(IsEmptyStack(plist))
	{
		return -1;
	}
	
	STACK_NODE *p = plist->phead;
	plist->phead = p->pnext;
	if(data != NULL)
	{
		*data = p->data;
	}
		free(p);
	plist->clen--;

	return 0;
}

int GetTopOfStack(STACK_LIST *plist,int *num)
{
	if(IsEmptyStack(plist))
	{
		return 0;
	}
	
	STACK_NODE *p = plist->phead;

	*num = p->data;

	return 0;
}

int ClearStack(STACK_LIST *plist)
{
	if(IsEmptyStack(plist))
	{
		return 0;
	}

	STACK_NODE *p = plist->phead;

	while(p)
	{
		PopHeadSTACK(plist,NULL);
		p = plist->phead;
	}

	return 0;
}

void DestoryStack(STACK_LIST *plist)
{
	ClearStack(plist);
		free(plist);
		return ;
}

int StackLength(STACK_LIST *plist)
{
	return plist->clen;
}

int ErgodicOfStack(STACK_LIST *plist)
{
	if(IsEmptyStack(plist))
	{
		return 0;
	}
	
	STACK_NODE *p = plist->phead;

	while(p)
	{
		printf("%d ",p->data);
		p = p->pnext;
	}
	
	putchar('\n');

	return 0;
}

###结果：

以上就是今天内容！