建设班级网站过程,夫妻做网站,wordpress 缺省目录,传媒公司注册经营范围有哪些Hello#xff0c;今天我们来实现一下数组栈#xff0c;学完这个我们又更进一步了。 一、栈 栈的概念 栈是一种特殊的线性表#xff0c;它只允许在固定的一端进行插入和删除元素的操作。 进行数据的插入和删除只在栈顶实现#xff0c;另一端就是栈底。 栈的元素是后进先出。… Hello今天我们来实现一下数组栈学完这个我们又更进一步了。 一、栈 栈的概念 栈是一种特殊的线性表它只允许在固定的一端进行插入和删除元素的操作。 进行数据的插入和删除只在栈顶实现另一端就是栈底。 栈的元素是后进先出。 压栈栈的数据进入就是压栈 出栈栈的数据删除就叫出栈 我们画一个原理图让大家比较好理解一下。 这一过程叫做pop出栈
我们上述的过程都是在栈顶实现出栈入栈并不能像顺序表和单链表那样从任意位置删除和增加但这就是栈的性质我们后面会讲它的作用。
实现栈我们可以用链表产生节点的方式链接他们但是也可以用数组下标访问的方式类似顺序表这样的方法 那这两个方法哪个好呢我们来比较一下。 因为栈的性质我们不得从栈顶出栈和入栈如果我们实现的时候是链表的方式那必然会存在一个问题就是我们的时间复杂度是ON我们需要遍历一遍数组这样的话栈好像变得“土”所以用数组的方式更快的提高效率 二、栈的定义
typedef int StackDataType;
#define N 100
struct Stack
{StackDataType arry[N];StackDataType top;
};
这是静态栈在顺序表的时候我们就讲过静态栈存在缺点最大的缺点就是不能开辟空间100个最多只能存100个数据如果我只使用10个int空间就存在浪费了如果我要存储1000个数据我们的空间又不够了这就会造成一系列问题所以我们改一下变成动态栈我们来实现一下吧。
typedef int StackDataType;
typedef struct Stack
{StackDataType* arry;int top;int capacity;
}Stack;有了结构体还是老样子我们来实现一下接口函数开整 初始化栈
void StackInit(Stack* pst)
{assert(pst);pst-arry NULL;pst-capacity pst-top 0;
}初始化栈这个大家肯定会了。 销毁 void StackDestory(Stack* pst)
{assert(pst);free(pst-arry);pst-capacity pst-top 0;}判断栈是否为空 bool StackEmpty(Stack* pst)
{assert(pst);return pst-top 0;
}现在我们要实现一个入栈的方法入栈的时候我们需要检查一下我们的内存空间是不是满了和顺序表一样的道理如果满了我们就需要扩容。所以在入栈的时候需要判断一下它空间有没有满。
void StackPush(Stack* pst, StackDataType x)
{assert(pst);if (pst-capacity pst-top){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;StackDataType* tmp (StackDataType*)realloc(pst-arry, sizeof(int) * newcapacity);if (tmp NULL){printf(realloc fail\n);exit(-1);}pst-arry tmp;pst-capacity newcapacity;}pst-arry[pst-top - 1] x;pst-top;}这和我们顺序表的尾插一摸一样现在看大家肯定觉得简单很多了。 有了入栈那就有出栈。
void StackPop(Stack* pst)
{assert(pst);if (pst-top 0){pst-top--;}
}因为我们上面写了一个判断该数是不是为空我们也可以写成
void StackPop(Stack* pst)
{assert(pst);if (!StackEmpty(pst)){pst-top--;}
}返回栈顶数据
StackDataType StackTop(Stack* pst)
{assert(pst);return pst-arry[pst-top - 1];
}统计栈里有多少数
int StackSize(Stack* pst)
{assert(pst);return pst-top;
}完整代码
#pragma once#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h
//typedef int StackDataType;
//#define N 100
//struct Stack
//{
// StackDataType arry[N];
// StackDataType top;
//};typedef int StackDataType;
typedef struct Stack
{StackDataType* arry;int top;int capacity;
}Stack;void StackInit(Stack* pst);void StackDestory(Stack* pst);bool StackEmpty(Stack* pst);void StackPush(Stack* pst, StackDataType x);void StackPop(Stack* pst);StackDataType StackTop(Stack* pst);int StackSize(Stack* pst);#includeStack.hvoid StackInit(Stack* pst)
{assert(pst);pst-arry NULL;pst-capacity pst-top 0;
}void StackDestory(Stack* pst)
{assert(pst);free(pst-arry);pst-capacity pst-top 0;}bool StackEmpty(Stack* pst)
{assert(pst);return pst-top 0;
}void StackPush(Stack* pst, StackDataType x)
{assert(pst);if (pst-capacity pst-top){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;StackDataType* tmp (StackDataType*)realloc(pst-arry, sizeof(int) * newcapacity);if (tmp NULL){printf(realloc fail\n);exit(-1);}pst-arry tmp;pst-capacity newcapacity;}pst-arry[pst-top - 1] x;pst-top;}void StackPop(Stack* pst)
{assert(pst);if (pst-top 0){pst-top--;}
}void StackPop(Stack* pst)
{assert(pst);if (!StackEmpty(pst)){pst-top--;}
}StackDataType StackTop(Stack* pst)
{assert(pst);return pst-arry[pst-top - 1];
}int StackSize(Stack* pst)
{assert(pst);return pst-top;
}栈的应用也有很多后面会分享给大家我们下次再见
