数据结构-栈及栈的应用

栈的概述

部分算法分析

顺序栈的表示和实现

global.h

Stack.h

StackTest.cpp

运行结果

栈的应用

数的任意进制转换

括号匹配检验

栈的概述

栈是一种重要的线性结构，属于一种操作受限的线性表
栈(stack) 是限定仅在表尾进行插入或删除操作的线性表
表尾端称为栈顶(top)，表头端称为栈底(bottom)
栈的元素遵循先进后出(后进先出)，即最先进入栈的元素最后出栈

部分算法分析

栈的初始化

//栈的初始化(构造一个空的栈)
Status InitStack(Stack& S) {//为栈开辟空间S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));if (!S.base)return ERROR;//当top指针与base指针指向地址时，栈为空栈S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;
}

顺序栈，即栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，注意：top指针所指的地址并不是存储栈顶数据元素的，而是栈顶数据元素的上一个空间地址

数据入栈操作

//数据元素data入栈操作
Status PushStack(Stack& S, SElemType data) {//判断栈内的数据是否已满，已满追加新的存储空间if (S.top - S.base >= S.stacksize) {//为栈追加新的空间SElemType* newbase;newbase = (SElemType*)realloc(S.base,(S.stacksize + STACK_INCREMENT)*sizeof(SElemType));if (newbase)return ERROR;S.base = newbase;//防止出现新开辟的空间中存储了其它程序的数据被覆盖S.top = S.base + S.stacksize;S.stacksize += STACK_INCREMENT;}if(S.top != NULL)*(S.top++) = data;return OK;
}

追加存储空间使用的是realloc(void *ptr, size_t size) 函数

ptr指针指向一个要重新分配内存的内存块，如果为空指针，则会分配一个新的内存块，且函数返回一个指向它的指针

size内存块的新的大小，以字节为单位。如果大小为 0，且 ptr 指向一个已存在的内存块，则 ptr 所指向的内存块会被释放，并返回一个空指针

情况1

情况2

在空间扩大的过程中，如果在原地址后有足够的空间追加，则直接在原空间后扩大空间，如果原地址后没有足够的空间追加，则会在新的一块地址区域直接开辟一块size大小的地址空间

顺序栈的表示和实现

global.h
Stack.h
StackTest.cpp

global.h

相关头文件的引用，以及相应全局变量、常量的声明

#pragma once#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<windows.h>using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define EQ(a,b) ((a) == (b))#define LT(a,b) ((a) < (b))#define LQ(a,b) ((a) <= (b))#define MT(a,b) ((a) > (b))#define MQ(a,b) ((a) >= (b))typedef int Status;

Stack.h

顺序栈的定义，以及顺序栈的相关操作算法

#pragma once
#include"global.h"#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
#define SElemType int//栈的定义
typedef struct {SElemType* base;  //栈底指针SElemType* top;   //栈顶指针int stacksize;    //栈的空间大小
}Stack;//栈的初始化(构造一个空的栈)
Status InitStack(Stack& S) {//为栈开辟空间S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));if (!S.base)return ERROR;//当top指针与base指针指向地址时，栈为空栈S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;
}//空栈的数据赋值操作
Status InitStackData(Stack& S) {//判断该栈是否为空栈if (S.top != S.base) {cout << "该栈不是空栈" << endl;return ERROR;}cout << "输入插入存储数据的个数:" << endl;int nums = 0;cin >> nums;cout << "输入" << nums << "个数据:" << endl;for (int i = 0; i < nums; i++) {cin >> *(S.top++);}return OK;
}//栈的数据遍历
void ShowStack(Stack S) {cout << "栈内的数据元素有:" << endl;while (S.top != S.base) {cout << *(--S.top) << " ";}cout << endl;
}//判断栈是否为空栈
Status StackEmpty(Stack S) {if (S.top == S.base)return OK;return ERROR;
}//栈的销毁
Status DestroyStack(Stack& S) {S.top = S.base;free(S.base);cout << "栈销毁成功" << endl;return OK;
}//将栈置为空栈
Status ClearStack(Stack& S) {S.top = S.base;cout << "栈置为空栈成功" << endl;return OK;
}//输出栈内的数据个数
int StackLength(Stack S) {int length = S.top - S.base;return length;
}//获取栈顶的数据
void GetTop(Stack S) {cout << "栈顶的数据为:" << *(S.top - 1) << endl;
}//数据元素data入栈操作
Status PushStack(Stack& S, SElemType data) {//判断栈内的数据是否已满，已满追加新的存储空间if (S.top - S.base >= S.stacksize) {//为栈追加新的空间SElemType* newbase;newbase = (SElemType*)realloc(S.base,(S.stacksize + STACK_INCREMENT)*sizeof(SElemType));if (newbase)return ERROR;S.base = newbase;//防止出现新开辟的空间中存储了其它程序的数据被覆盖S.top = S.base + S.stacksize;S.stacksize += STACK_INCREMENT;}if(S.top != NULL)*(S.top++) = data;return OK;
}//将栈顶数据元素出栈，并记录出栈的数据元素
Status PopStack(Stack& S, SElemType& data) {//判断栈是否为空，不为空则删除栈顶数据元素(出栈)if (S.top == S.base)return ERROR;data = *(--S.top);return OK;
}

StackTest.cpp

#include"Stack.h"int main() {Stack stack;InitStack(stack);InitStackData(stack);ShowStack(stack);int length = StackLength(stack);cout << "栈内的元素个数为:" << length << endl;SElemType data;GetTop(stack);cout << "入栈操作,请输入入栈的数据:" << endl;cin >> data;PushStack(stack,data);ShowStack(stack);cout << "------出栈操作------" << endl;PopStack(stack, data);cout << "出栈的数据是:" << data << endl;ShowStack(stack);
}

运行结果

输入插入存储数据的个数:
5
输入5个数据:
12 23 43 21 56
栈内的数据元素有:
56 21 43 23 12
栈内的元素个数为:5
栈顶的数据为:56
入栈操作,请输入入栈的数据:
87
栈内的数据元素有:
87 56 21 43 23 12
------出栈操作------
出栈的数据是:87
栈内的数据元素有:
56 21 43 23 12

F:\DataStructureForC++\Project\Debug\Project1.exe (process 5248) exited with code 0.

栈的应用

数的任意进制转换
括号匹配检验
表达式求值

数的任意进制转换

将一个十进制数N与其他d进制数转换，基于下列原理

N = (N div d) × d + N mod d (div为整除运算，mod为求余运算)

/*
* 数的任意进制转换
* 用户输入任意非负正整数，再输入一个进制数
*/
void NumberConversion(int number,int baseNumber) {//判断输入的数是否为正整数if (number < 0) {cout << "输入的数不能为负数" << endl;exit(0);}Stack stack;SElemType data;InitStack(stack);cout << number << "转化" << baseNumber << "进制后的数为:" << endl;while (number) {PushStack(stack, number % baseNumber);number = number / baseNumber;}while (!StackEmpty(stack)) {PopStack(stack, data);cout << data;}cout << endl;
}

运行结果

请输入一个非负的十进制整数
8
请输入一个进制数:
2
8转化2进制后的数为:
1000

请输入一个非负的十进制整数
89
请输入一个进制数:
8
89转化8进制后的数为:
131

括号匹配检验

假设表达式中允许包含两种括号：圆括号（）和方括号 [ ] ，其嵌套顺序随意，检验括号嵌套的格式是否正确

/*
* 括号匹配检验
* 用户输入方括号和圆括号，检验括号是否匹配
* charArray数组以'#'作为最后一个数据元素(循环终止条件)
*/
void BracketMatch(char charArray[]) {Stack stack;InitStack(stack);SElemType c;while (*charArray != '#') {switch ((*charArray)) {case ')':PopStack(stack, c);if (c != '(') {cout << ") 括号不匹配" << endl;exit(0);}break;case ']':PopStack(stack, c);if (c != '[') {cout << "] 括号不匹配" << endl;exit(0);}break;default://如果不是右括号，将该括号进栈PushStack(stack, *(charArray));}charArray++;}cout << "括号匹配成功" << endl;
}

运行结果