0205：数据结构-栈

发表信息: October 06, 2018 by

文章分类:
算法 17

本文依照学习难度，分成入门、进阶两个部分。

入门部分以直观、易于理解为主；进阶部分重点在于概念、推导等。

入门

栈是一种先进后出（或者说是后进先出）的数据结构。（Last In First Out，LIFO）

调用栈（call stack） – 其中的一种栈

用于存储多个函数的变量

调用栈的使用过程：

1
2
3
4
5
6
7
8
9
10
11
def greer(name):
	print("hello"+name+"!")
	greet2(name)
	print("getting ready to say bye")
	bye()

def greet2(name):
	print("how are you, "+name+"?")

def bye():
	print("OK bye")

接下来看这个函数的整个调用过程：

调用：greet("maggie")

那么栈和数组、链表有啥关系呢？

使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存

每个函数都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息

如果内存占用过高，可以改用循环，或者尾递归

可以很容易判断回文。比如xyzyx

判断回文的关键步骤：将当前栈中的字符依次出栈，看看是否能与mid之后的字符一一匹配。

进阶

[1] 算法图解 Aditya Bhargava (作者) 袁国忠 (译者)

目录

入门

调用栈（call stack） – 其中的一种栈

进阶