一、栈的特性(先进后出)
特点：栈只能在栈顶进行删除(pop),插入(push)操作。
栈的示意图
栈顶是顺序存储结构上第一个没有存放数据的地址。
空栈则表示为栈顶和栈底都指向同一个元素。
同时在编写代码的过程中，使用到了auto等c++11的特性，故需要编译器支持c++11的标准。(在编译器命令添加：-std=c++11)
二、栈的定义和基本操作
- 栈的定义
- 栈的初始化
- 栈的插入
- 栈的删除
- 获取栈的大小
- 获取栈顶元素值
- 清空栈
1.栈的定义(顺序存储的方式)
栈的定义，使用别名功能，方便栈适应不同的数据类型
// 定义数据类型 (方便栈选择不同的数据类型)
typedef int Elemtype;
const unsigned int StackInitSize = 100; // 初始化每个栈刚开始的容量
const unsigned int StackSizeCre = 20; // 当栈的容量不能满足使用 需要对栈进行扩容处理
// 声明和定义
typedef struct Stack{
Elemtype *base; // 栈底
Elemtype *top; // 栈顶
uunsigned int StackSize; // 栈可以容下的最大容量
}
2.栈的初始化
需要考虑在使用new分配动态内存过程中，会出现动态内存分配不成功，则会报出bad_alloc的异常，异常处理工具。
// 初始化栈
void init_stack(Stack *sta){
// 给该栈分配内存(最大容量内存)
try{
sta->base = new ElemType[StackInitSize];
// 必须要保证分配内存成功！(当使用new 分配内存不成功，会抛出异常，所以需要捕捉这个异常！)
// 当使用new 分配内存不成功时，会抛出 bad_alloc 的异常
}catch(const std::bad_alloc& e)
{
std::cout<<"can,t init stack!";
return ;
}
// 分配内存正常后
sta->top = sta->base; // 此时空栈 栈顶和栈底对应的位置相同
sta->StackSize = StackInitSize;
}
3. 栈的插入
在栈的插入之前，需要判断该栈是否已经满了，当满了需要另外开辟一个空间去存放栈的数据。
// 插入新的元素 在栈顶
void push( Stack &sta , ElemType e){
auto size = sta.top - sta.base;
// 先判断该栈是否已经满
if(size == sta.StackSize){
ElemType *newdata = new ElemType[sta.StackSize+StackSizeCre]; // 此处也需要判断是否分配正常 但是一般情况都分配内存成功，故不做异常检查
auto temp = newdata;
// 将原来的数据全部拷贝的当前数据中
for(auto i = sta.base; i!= sta.top; ++i){
*(temp++) = *I;
}
*(temp++) = e;
delete[] sta.base;
sta.base = newdata;
sta.top = temp;
sta.StackSize = sta.StackSize+StackSizeCre;
}else {
*(sta.top++) = e;
}
}
4. 栈的删除
在删除栈的过程中，需要先判断该栈是否为空栈（即栈顶和栈底的指向同一个内存空间），之后在进行删除操作，返回指针对象，因为当为空的栈的话，方便返回空指针。
// 删除栈元素(只能删除栈顶的元素)
ElemType* pop(Stack &sta){
// 先判断是否为空栈
if(sta.base != sta.top){
return &*(--sta.top);
}else{
std::cout<<"this stack is empty!\n";
return nullptr;
}
}
5. 获得栈的大小
栈的大小通过指向数据对象的指针进行相减得到，其结果的数据类型应该是size_t类型，需要进行隐式类型转换到unsigned int 类型。
// 返回栈的大小
unsigned int GetSize(Stack &sta){
return sta.top-sta.base;
}
6. 获取栈顶的元素
只取值 不进行删除操作
// 获取栈顶元素的值
ElemType GetTopVal(Stack &sta){
auto temp = sta.top;
return *(--temp);
}
7. 清空栈
void clean(Stack &sta){
sta.StackSize = 0;
delete[] sta.base;
}
三、完整栈的使用程序
#include<iostream>
#include<stdexcept>
typedef int ElemType; // 取别名 (方便给栈选择不同的数据类型)
const unsigned int StackInitSize = 100; // 初始化每个栈刚开始的容量
const unsigned int StackSizeCre = 20; // 当栈的容量不能满足使用 需要对栈进行扩容处理
// 定义栈对象
struct Stack
{
ElemType *base; // 栈底
ElemType *top; // 栈顶
unsigned int StackSize; // 栈可以容纳最大的数据量
};
// 栈的初始化
void init_stack(Stack *sta){
// 给该栈分配内存(最大容量内存)
try{
sta->base = new ElemType[StackInitSize];
// 必须要保证分配内存成功！(当使用new 分配内存不成功，会抛出异常，所以需要捕捉这个异常！)
// 当使用new 分配内存不成功时，会抛出 bad_alloc 的异常
}catch(const std::bad_alloc& e)
{
std::cout<<"can,t init stack!";
return ;
}
// 分配内存正常后
sta->top = sta->base; // 此时空栈 栈顶和栈底对应的位置相同
sta->StackSize = StackInitSize;
}
// 插入新的元素 在栈顶
void push( Stack &sta , ElemType e){
auto size = sta.top - sta.base;
// 先判断该栈是否已经满
if(size == sta.StackSize){
ElemType *newdata = new ElemType[sta.StackSize+StackSizeCre]; // 此处也需要判断是否分配正常 但是一般情况都分配内存成功，故不做异常检查
auto temp = newdata;
// 将原来的数据全部拷贝的当前数据中
for(auto i = sta.base; i!= sta.top; ++i){
*(temp++) = *I;
}
*(temp++) = e;
delete[] sta.base;
sta.base = newdata;
sta.top = temp;
sta.StackSize = sta.StackSize+StackSizeCre;
}
else{
*(sta.top++) = e;
}
}
// 删除栈元素(只能删除栈顶的元素)
ElemType* pop(Stack &sta){
// 先判断是否为空栈
if(sta.base != sta.top){
return &*(--sta.top);
}else{
std::cout<<"this stack is empty!\n";
return nullptr;
}
}
// 返回栈的大小
unsigned int GetSize(Stack &sta){
return sta.top-sta.base;
}
// 获取栈顶元素的值
ElemType GetTopVal(Stack &sta){
auto temp = sta.top;
return *(--temp);
}
// 清空栈
void clean(Stack &sta){
sta.StackSize = 0;
delete[] sta.base;
}
int main(){
Stack stack ;
// 初始化 栈对象
init_stack(&stack);
std::cout<<"after init\n";
std::cout<<"size "<<GetSize(stack)<<" capacity "<<stack.StackSize<<std::endl;
// 生成101个栈的对象
for(int i = 0;i<101;++i){
push(stack,i);
}
int size = GetSize(stack);
std::cout<<"after push\n";
std::cout<<"size "<<GetSize(stack)<<" capacity "<<stack.StackSize<<std::endl;
// 取出栈顶的数据
std::cout<<" the val : "<<GetTopVal(stack)<<std::endl;
std::cout<<"after get val\n";
std::cout<<"size "<<GetSize(stack)<<" capacity "<<stack.StackSize<<std::endl;
// 删除栈顶的数据
for(int i=0;i<size;++i){
std::cout<<*pop(stack)<<" ";
}
std::cout<<"after pop\n";
std::cout<<"size "<<GetSize(stack)<<" campacity "<<stack.StackSize<<std::endl;
// 清空栈数据
clean(stack);
std::cout<<"after clean\n";
std::cout<<"size "<<GetSize(stack)<<" campacity "<<stack.StackSize<<std::endl;
return 0;
}
输出结果
after init
size 0 capacity 100
after push
size 101 capacity 120
the val : 100
after get val
size 101 capacity 120
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 after pop
size 0 campacity 120
after clean
size 0 campacity 0
网友评论