栈——栈的实现和应用

1、采用严版数据结构书上第46页定义的栈的顺序存储表示，编程实现栈的下列基本操作。

（1）初始化顺序栈     （2）创建顺序栈     （3）判断栈空     （4）输出顺序栈

（5）取栈顶元素       （6）入栈           （7）出栈

 

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef int SElemType;

using namespace std;
typedef struct
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

Status InitStack(SqStack &S)
{
	S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S.base)
		exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}

Status StackEmpty(SqStack &S)
{
	if (S.top == S.base)
	{
		return TRUE;
	}
	else
		return FALSE;
}

Status GetTop(SqStack &S, SElemType &e)
{
	if (S.top == S.base)
		return ERROR;
	 e=  *(S.top-1);
	 return OK;
}

Status Push(SqStack &S, SElemType e)
{
	if (S.top - S.base >= S.stacksize)
	{
		S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
		if (!S.base)
			exit(OVERFLOW);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return OK;
}

Status Pop(SqStack &S, SElemType &e)
{
	if (S.top == S.base)
		return ERROR;
	e = *--S.top;
	return OK;
}

Status Stackoutput(SqStack &S)
{
	SElemType *p;
	if (S.top == S.base)
		return ERROR;
	p = S.base;
	while (p != S.top)
	{
		printf("%d ", *p);
		p++;
	}
	return OK;
}

Status StackTraverse(SqStack &S)
{
	SElemType *p;
	if (S.top == S.base)
		return ERROR;
	p = S.top - 1;
	while (p != S.base - 1)
	{
		printf("%d ", *p);
		p--;
	}
	return OK;
}

void main()
{
	int i, n, k, h, a, b;
	SqStack S;
	printf("创建一个空栈!\n");
	InitStack(S);
	printf("判断栈是否为空！\n");
	printf("StackEmpty(S)=%d\n", StackEmpty(S));
	printf("创建栈的元素个数：\n");
	cin >> n;
	printf("输入%d个入栈元素的值：\n", n);
	for (i = 0; i < n; i++)
	{
		cin >> k;
		Push(S, k);
	}
	printf("逆序输出顺序栈元素值：\n");
	Stackoutput(S);
	printf("输出顺序栈元素值：\n");
	StackTraverse(S);
	printf("输入入栈元素值：");
	cin >> h;
	Push(S, h);
	printf("输出入栈后的顺序栈元素值：\n");
	StackTraverse(S);
	Pop(S, a);
	printf("输出第一个出栈元素值：%d\n", a);
	Pop(S, a);
	printf("输出第二个出栈元素值：%d\n", a);
	printf("输出两次出栈后顺序栈元素值：");
	StackTraverse(S);
	GetTop(S, b);
	printf("输出栈顶元素值：%d\n", b);
	system("pause");
}

2、采用栈的顺序存储表示，编程实现表达式中圆括号“( )”和方括号“[ ]”匹配的检验。

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef char SElemType;

using namespace std;
typedef struct
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

Status InitStack(SqStack &S)
{
	S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S.base)
		exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}

Status StackEmpty(SqStack &S)
{
	if (S.top == S.base)
	{
		return TRUE;
	}
	else
		return FALSE;
}

Status GetTop(SqStack &S, SElemType &e)
{
	if (S.top == S.base)
		return ERROR;
	e = *(S.top - 1);
	return OK;
}

Status Push(SqStack &S, SElemType e)
{
	if (S.top - S.base >= S.stacksize)
	{
		S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
		if (!S.base)
			exit(OVERFLOW);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return OK;
}

Status Pop(SqStack &S, SElemType &e)
{
	if (S.top == S.base)
		return ERROR;
	e = *--S.top;
	return OK;
}

Status Correct(SElemType str[])
{
	SqStack S;
	InitStack(S);
	int i, state = 1;
	SElemType e;
	for (i = 0; str[i] != '\0'; i++)
	{
		switch (str[i])
		{
		case '(':
			Push(S,str[i]);
			break;
		case '[':
			Push(S, str[i]);
			break;
		case ')':
				Pop(S, e);
				if (e != '(')
					state = 0;
			break;
		case ']':
			Pop(S, e);
			if (e != '[')
				state = 0;
			break;
		}
		if (!state)
			break;
	}
	if (StackEmpty(S) && state == 1)
		return OK;
	else
		return ERROR;
}

void main()
{
	SElemType str[100];
	printf("请输入带括号的表达式：\n");
	cin >> str;
	if (Correct(str) == OK)
		printf("括号匹配正确！\n");
	else
		printf("括号匹配不正确！\n");
	system("pause");
}