想当一个合格的程序员,你敢出去说你不会栈吗?
我不敢的。
栈有很多用途,也分很多种类,顺序栈、双端栈、单调栈、链栈等。让哥哥带你,深入浅出堆栈系列。坐好上车咯。
栈呐,你可以叫它弹(dan)栈,就像弹夹一样。 入栈只能在栈顶,出栈也只能在栈顶,想象一下手枪弹夹。
也可以说,栈是一种仅限于在表尾进行抽插的线性表。
类名 | 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;
} //判断是否为空
};
双栈是指两个顺序栈,是一种特殊的顺序栈。
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起到中转作用
本来我是一头雾水的,但是在力扣上被那个爬楼梯的“简单”动态规划题折磨之后,我有点茅厕顿开的感觉。
这个真的烧脑,主要配合上递归的思想
先看码: 栈部分代码,左边有目录,链栈。
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
}
}
不行,我要去补脑。。。
之前在力扣刷题,用到单调栈,不过那时候还不知道它叫单调栈哈哈,那个卖股票的题目。
单调栈就是栈内元素单调递增或者单调递减的栈,单调栈只能在栈顶操作。
Q:给你一串序列,要你求所有子序列的最小值之和。
E:[-2,4,5,3,6,0,-3]