玩转数据结构（3）

思维导图是依旧还没有的啊

栈

想当一个合格的程序员，你敢出去说你不会栈吗？

我不敢的。

栈有很多用途，也分很多种类，顺序栈、双端栈、单调栈、链栈等。让我们一起带你，深入浅出栈结构。坐好上车咯。

①后进先出的叫栈

栈呐，你可以叫它弹（dan）栈，就像弹夹一样。
入栈只能在栈顶，出栈也只能在栈顶，想象一下手枪弹夹。

也可以说，栈是一种仅限于在表尾进行抽插的线性表。

②API设计

上面缺省的数据类型，为泛型。为了方便理解，接下来全用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;
	} //判断是否为空	
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
 

④双端栈

双栈是指两个顺序栈，是一种特殊的顺序栈。

• 双栈共享一个地址连续的存储单元。即程序同时需要两个栈时，可以定义一个足够大的栈空间，该空间的两端分别设为两个栈的栈底，用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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
 

多端栈

多端栈推荐使用链栈实现。

⑤动态栈

前面讨论的栈基本由静态数组实现，栈大小必须固定，这种实现显然有局限，为了克服这种局限，我们可以采用动态栈的方式。
先为栈分配存储空间，之后还需要动态调整栈的大小。

如何去实现呢？大家可还记得vector的特性吗？
如果声明一个vector数组时不给定大小，它将会是多大？
如果存入的内容超出了它原有的大小，它会作何反应？
如果不知道，可以动手试试。

⑥汉诺塔

汉诺塔：汉诺塔(Tower of
Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
–引用维基百科

a是起始柱，c是目标柱，b起到中转作用

  

 

  
1
 

本来我是一头雾水的，但是在力扣上被那个爬楼梯的“简单”动态规划题折磨之后，我有点茅厕顿开的感觉。

• 问题看起来并不复杂，当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
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

不行，我要去补脑。。。

⑦单调栈

之前在力扣刷题，用到单调栈，不过那时候还不知道它叫单调栈哈哈，那个卖股票的题目。

单调栈就是栈内元素单调递增或者单调递减的栈，单调栈只能在栈顶操作。

性质：

• 单调栈的维护是 O(n) 级的时间复杂度，因为所有元素只会进入栈一次，并且出栈后再也不会进栈了。
• 单调栈里的元素具有单调性。
• 元素加入栈前，会在栈顶端把破坏栈单调性的元素都删除
• 使用单调栈可以找到元素向左遍历第一个比他小的元素，也可以找到元素向左遍历第一个比他大的元素。
• 单调栈在用于维护区间距非常有优势。

波兰式与逆波兰式

什么是波兰表达式

人类最熟悉的一种表达式1+2，(1+2)*3，3+4 *2+4等等都是中缀表示法。对于人们来说，也是最直观的一种求值方式，先算括号里的，然后算乘除，最后算加减，但是，计算机处理中缀表达式却并不方便，因为没有一种简单的数据结构可以方便从一个表达式中间抽出一部分算完结果，再放进去，然后继续后面的计算（链表也许可以，但是，代价也是不菲）。

因此，1920年，波兰科学家扬·武卡谢维奇（Jan ukasiewicz）发明了一种不需要括号的计算表达式的表示法将操作符号写在操作数之前，也就是前缀表达式，即波兰式（Polish Notation, PN）。

中缀表达式转逆波兰表达式

这里使用栗子：（1 + 2 * (4 - 3) + 6/2）

算法伪代码（如果不清楚流程的话，务必要先看一下）

输入：中缀表达式串

输出：后缀表达式串

PROCESS BEGIN: 1.从左往右扫描中缀表达式串s，对于每一个操作数或操作符，执行以下操作; 2.IF (扫描到的s[i]是操作数DATA) 将s[i]添加到输出队列中; 3.IF (扫描到的s[i]是开括号'(') 将s[i]压栈; 4.WHILE (扫描到的s[i]是操作符OP) IF (栈为空 或 栈顶为'(' 或 扫描到的操作符优先级比栈顶操作符高) 将s[i]压栈; BREAK; ELSE 出栈至输出队列中 5.IF (扫描到的s[i]是闭括号')') 栈中运算符逐个出栈并输出，直到遇到开括号'('; 开括号'('出栈并丢弃; 6.返回第1.步 7.WHILE (扫描结束而栈中还有操作符) 操作符出栈并加到输出队列中

PROCESS END

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
 

所以将上面的栗子放进去走一圈出来会怎样？

in>>（1 + 2 * (4 - 3) + 6/2）
out<<1 2 4 3 -*+ 6 2 / +

了解流程之后，我们来看个表：对于上面的栗子的转换

后缀表达式运算流程

逆波兰表达式的计算就比较简单了。以上面结果中的队列为输入，同时再准备一个栈用于运算。具体流程如下：

• 将队列中的数据依次出队，然后压栈；
• 在出队的过程中如果遇到运算符，则从栈中弹出2个运算数，分别作为右运算数和左运算数，进行运算；
• 将步骤2的运算结果入栈；
• 跳入步骤1，继续进行出队操作。

对上面栗子进行流程化：

①

②

③

我讲清楚了吗？

放码过去

这是一个多项式计算器的代码，注释我就没放（危险动作，请勿模仿）。

#ifndef _STACK_H_
#define _STACK_H_

#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

typedef struct node
{ int data; struct node *next;
}Node;

typedef struct stack
{ Node *top;
}Stack;

void Init(Stack *s);

int Empty(Stack *s);

void Push(Stack *s, int data);

void Pop(Stack *s);

int GetTop(Stack *s);

#endif 


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
 

#include "stack.h"


void Init(Stack *s)
{ if (NULL == s) return; s->top = NULL;
}

int Empty(Stack *s)
{ if (NULL == s) return 0; if (NULL == s->top) return 1; return 0;
}

void Push(Stack *s,int data)
{ if (NULL == s) return; Node *node = (Node *)malloc(sizeof(Node)/sizeof(char)); if (NULL == node) return; node->data = data; node->next = s->top; s->top = node;
}

void Pop(Stack *s)
{ if (NULL == s) return; if (Empty(s) == 1) return; Node *tmp = s->top; s->top = tmp->next; free(tmp);
}

int GetTop(Stack *s)
{ if (NULL == s) return; if (Empty(s) == 1) { printf ("无栈顶元素\n"); exit(-1); } return s->top->data;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
 

#include <stdio.h>
#include "stack.h"
#include <string.h>

int Ope_judge(Stack *s_ope,int ope)
{ if(Empty(s_ope)) return 1; int top = GetTop(s_ope); switch(top) { case '+': case '-': if(ope == '*' || ope == '/' || ope == '(') return 1; break; case '*': case '/': if( ope == '(') return 1; break; case '(': if(ope == ')') { Pop(s_ope); } return 1; default : break; } return 0;
}

void Calc(Stack *s_ope,Stack *s_num)
{ int num1 = GetTop(s_num); Pop(s_num); int num2 = GetTop(s_num); Pop(s_num); int ope = GetTop(s_ope); Pop(s_ope); int res; switch(ope) { case '+': res = num2 + num1; break; case '-': res = num2 - num1; break; case '*': res = num2 * num1; break; case '/': res = num2 / num1; break; default: break; } Push(s_num,res);
}


void Ope_deal(Stack *s_ope,Stack *s_num,int ope)
{ if(Ope_judge(s_ope,ope) == 1) { Push(s_ope,ope); } else { while(Ope_judge(s_ope,ope) == 0) { Calc(s_ope,s_num); } if(ope != ')') Push(s_ope,ope); }

}

int main()
{ char buf[100]; fgets(buf,100,stdin); buf[strlen(buf)-1] = '\0'; Stack s_num; Stack s_ope; Init (&s_num); Init (&s_ope); char *p = buf; while(*p) { if(*p >= '0' && *p <= '9') { int num = 0; while(*p >= '0' && *p <= '9') { num = num *10 + *p - '0'; p++; } Push(&s_num , num); continue; } Ope_deal(&s_ope,&s_num,*p); p++; } while(!Empty(&s_ope)) { Calc(&s_ope,&s_num); } int res = GetTop(&s_num); printf ("计算结果为：%d\n", res); return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
  
132
 

队列

关于队列，就真的不知道该再说啥了。上边的栈已经说得天花乱坠了。
但是队列在后端开发又占有不低的地位，为啥，消息队列如果没听过，卡夫卡听过吗？
RocketMQ没听过，双十一剁手剁过吗？没有消息队列，各位怎么能愉快的双十一抢购呢。

队列是一种先进先出(FIFO) 的线性表。在表一端插入，在另一端删除。

消息队列

想要进一步了解队列的小伙伴请移步：
消息队列：解耦、异步、削峰，现有MQ对比以及新手入门该如何选择MQ?

又有点长了，链表只能往后推了。链栈想了想也放后面吧。。

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/111463865