程序员必备数据结构：栈
在这里插入图片描述
想当一个合格的程序员，你敢出去说你不会栈吗？
我不敢的。
栈有很多用途，也分很多种类，顺序栈、双端栈、单调栈、链栈等。让哥哥带你，深入浅出堆栈系列。坐好上车咯。
①后进先出的叫栈
栈呐，你可以叫它弹（dan）栈，就像弹夹一样。 入栈只能在栈顶，出栈也只能在栈顶，想象一下手枪弹夹。
也可以说，栈是一种仅限于在表尾进行抽插的线性表。
②API设计
类名 | stack |
|---|---|
构造方式 | stack() |
成员方法： | |
入栈（压栈） | push(void*) |
出栈（弹栈） | pop(void*) |
大小获取 | size() |
栈顶元素获取 | top() |
成员属性： | |
对于链栈 | Node pres; Node prev; Node data; |
对于线栈 | int size; top |
上面缺省的数据类型，为泛型。为了方便理解，接下来全用int类型
③顺序栈实现
#include <iostream>
#define StackSize 100 //栈长度
using namespace std;
class SeqStack {
private:
int data[StackSize]; //线性栈表
int top; //纪录栈顶
public:
SeqStack(){top=-1;}; //将项顶指针置为-1
~SeqStack(){}
void Push(int x){
if (top==StackSize-1){
cout<<"栈满"<<endl;
return;
}
top++;
data[top] = x;
}
int Pop(){
if (top==-1){
cout<<"栈空"<<endl;
return;
}
return data[top];
top--
} //版本1：取出栈顶元素
//一般是用版本1，所以版本2不看了
int GetTop(){
if (top==-1){
cout<<"栈空"<<endl;
return;
}
return data[top];
}//取栈顶元素
int Empty(){
if (top==-1)
return 1;
} //判断是否为空
};④双端栈
双栈是指两个顺序栈，是一种特殊的顺序栈。
在这里插入图片描述
- 双栈共享一个地址连续的存储单元。即程序同时需要两个栈时，可以定义一个足够大的栈空间，该空间的两端分别设为两个栈的栈底，用bottom[0]=-1和bottom[1]=maxSize指示。
- 压入数据时，让两个栈的栈顶top[0]和top[1]都向中间伸展，如果指示栈顶的指针top[0]+1等于另一个栈顶的指针top[1]时两栈已满。
- 每次进栈时top[0]加1或top[1]减1，而退栈时top[0]减1或top[1]加1。
- 如果
top[0] == -1或top[1] == maxSize，有栈为空。
实现
#include <iostream>
using namespace std;
const int defaultSize = 50; //默认栈空间大小
const int stackIncreament = 20; //栈溢出时扩展空间的增量
const int n = 2; //设置n=2个栈共有一个栈空间
class DualStack
{
public:
DualStack(int sz = defaultSize); //构造函数
~DualStack(); //析构函数
public:
bool Push(const T& x, int d) ; //新元素x进栈
bool Pop(T& x, int d); //栈顶元素出栈，并将该元素的值保存至x
bool getTop(T& x, int d) const; //读取栈顶元素，并将该元素的值保存至x
bool IsEmpty() const; //判断栈是否为空
bool IsFull() const; //判断栈是否为满
int getSize() const; //计算栈中元素个数
void MakeEmpty(); //清空栈的内容
void overflowProcess(); //栈的溢出处理
private:
int *vec; //存放栈中元素
int top[n-1]; //栈顶指针
int maxSize; //栈最大可容纳元素个数
};
//构造函数
DualStack::DualStack(int sz)
{
if (sz >= 0)
{
maxSize = sz;
top[0] = -1;
top[1] = maxSize;
vec = new int[maxSize];
}
}
//析构函数
DualStack::~DualStack()
{
delete[] vec;
vec = NULL;
}
//新元素x进栈
bool DualStack::Push(const int x, int d)
{
if (true == IsFull())
return false;
if (0 == d)
top[0]++;
else
top[1]--;
vec[top[d]] = x;
return true;
}
//栈顶元素出栈，并将该元素的值保存至x
bool DualStack::Pop(int x, int d)
{
if (true == IsEmpty())
return false;
x = vec[top[d]];
if (0 == d)
top[0]--;
else
top[1]++;
return true;
}
//读取栈顶元素，并将该元素的值保存至x
bool DualStack::getTop(int x, int d) const
{
if (true == IsEmpty())
return false;
x = vec[top[d]];
return true;
}
//判断栈是否为空
bool DualStack::IsEmpty() const
{
return ((-1 == top[0]) && (maxSize == top[1])) ? true : false;
}
//判断栈是否为满
bool DualStack::IsFull() const
{
return (top[0] + 1 == top[1]) ? true : false;
}
//计算栈中元素个数
int DualStack::getSize() const
{
return (top[0] + 1) + (maxSize - top[1]);
}
//清空栈的内容
void DualStack::MakeEmpty()
{
delete[] vec;
top[0] = -1;
top[1] = maxSize;
vec = new int[maxSize];
//如果用vector容器的话，就直接清空了
//但是为了普遍性，还是把STL收起来了
}
//栈的溢出处理
void DualStack::overflowProcess()
{
int newSize = maxSize + stackIncreament;
int *neweVector = new int[newSize];
for (int i = 0; i <= top[0]; i++)
{
neweVector[i] = vec[i];
}
for (int i = maxSize - 1; i >= top[1]; i--)
{
neweVector[i + stackIncreament] = vec[i];
}
delete[] vec;
vec= neweVector;
maxSize = newSize;
top[1] += stackIncreament;
}多端栈
多端栈推荐使用链栈实现。
⑤链栈
链栈，结合了链表和栈的优点。
链栈的实现思路同顺序栈类似，通常我们将链表的头部作为栈顶，尾部作为栈底，如图所示:
在这里插入图片描述
- 将链表头部作为栈顶的一端，可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。
链表的头部作为栈顶，意味着：
在实现数据"入栈"操作时，需要将数据从链表的头部插入；
在实现数据"出栈"操作时，需要删除链表头部的首元节点；因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表。
实现
前面都用cpp，这里搞个c换换风格
//链表中的节点结构
typedef struct lineStack{
int data;
struct lineStack * next;
}lineStack;- 压栈实现
//stack为当前的链栈，a表示入栈元素
lineStack* push(lineStack * stack,int a){
//创建存储新元素的节点
lineStack * line=(lineStack*)malloc(sizeof(lineStack));
line->data=a;
//新节点与头节点建立逻辑关系
line->next=stack;
//更新头指针的指向
stack=line;
return stack;
}- 出栈实现
//栈顶元素出链栈的实现函数
lineStack * pop(lineStack * stack){
if (stack) {
//声明一个新指针指向栈顶节点
lineStack * p=stack;
//更新头指针
stack=stack->next;
printf("出栈元素：%d ",p->data);
if (stack) {
printf("新栈顶元素：%d\n",stack->data);
}else{
printf("栈已空\n");
}
free(p);
}else{
printf("栈内没有元素");
return stack;
}
return stack;
}⑥汉诺塔
在这里插入图片描述
汉诺塔：汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 –引用维基百科
a是起始柱，c是目标柱，b起到中转作用本来我是一头雾水的，但是在力扣上被那个爬楼梯的“简单”动态规划题折磨之后，我有点茅厕顿开的感觉。
- 问题看起来并不复杂，当a柱子上只有一个盘子时只要把那个盘子直接移到c就行了。 有两个盘子的话把1号盘先移到b柱，在把2号盘移到c柱，最后把b柱上的1号盘移到c柱就行了。
- 这里我们先把上方的63个盘子看成整体，这下就等于只有两个盘子，自然很容易了，我们只要完成两个盘子的转移就行了，好了现在我们先不管第64个盘子，假设a柱只有63个盘子，与之前一样的解决方式，前62个盘子先完成移动目标。
- 嗯，就这样一步步向前找到可以直接移动的盘子，62,61,60，…，2,1，最终，最上方的盘子是可以直接移动到c柱的，那就好办了，我们的2号盘也能完成向c柱的转移，这时c柱上时已经转移成功的2个盘，于是3号盘也可以了，一直到第64号盘。
这个真的烧脑，主要配合上递归的思想
先看码： 栈部分代码，左边有目录，链栈。
void main()
{
int n = 64; //可以泛化
Stack a = init_stack();
Stack b = init_stack();
Stack c = init_stack();
while(n-->0){// 初始化栈a，代表最左边柱子和盘子
push_stack(a,i);
}
hanoi(n,a,b,c);
}
void hanoi(int n,Stack a,Stack b,Stack c)
{
if(n == 1) // 盘子数为1
pop_push(a,c);
else
{
hanoi(n-1,a,c,b); // 将栈a的n-1个盘子顺序移到栈b
pop_push(a,c); // 将栈a的第n个盘子移到栈c
hanoi(n-1,b,c,a); // 将栈b的n-1个盘子顺序移到栈c
}
}不行，我要去补脑。。。
⑦单调栈
之前在力扣刷题，用到单调栈，不过那时候还不知道它叫单调栈哈哈，那个卖股票的题目。
单调栈就是栈内元素单调递增或者单调递减的栈，单调栈只能在栈顶操作。
性质：
- 单调栈的维护是 O(n) 级的时间复杂度，因为所有元素只会进入栈一次，并且出栈后再也不会进栈了。
- 单调栈里的元素具有单调性。
- 元素加入栈前，会在栈顶端把破坏栈单调性的元素都删除
- 使用单调栈可以找到元素向左遍历第一个比他小的元素，也可以找到元素向左遍历第一个比他大的元素。
- 单调栈在用于维护区间距非常有优势。
Q：给你一串序列，要你求所有子序列的最小值之和。
E：[-2,4,5,3,6,0,-3]
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-05-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读