《数据结构与算法之美》05——栈
2021-05-11 20:30
标签：链接 block 时间 数据集 als public 数组元素 其他 info 一、概念 栈：后进先出，先进后出的数据结构。栈是一种“操作受限‘的线性表，只允许在一端插入和删除数据。 当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。 二、如何实现“栈” 既可用数组（顺序栈），也可用链表（链式栈） 数组实现： 时间复杂度：O(1) 空间复杂度：O(1) 注意，这里存储数据需要一个大小为n的数组，并不是说空间复杂度就是O(n)。因为，这n个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。 链表实现： 时间复杂度：O(1) 空间复杂度：O(1) 三、栈的应用 四、如何实现浏览器的前进、后退功能 通过两个栈来实现，X栈来保存访问过的记录，Y栈保存后退后的记录。 比如依次访问了a、b、c、d三个页面，把前面三个页面压到X栈里，当点击后退时，从X栈里取出记录（c），并且把当前页面（d）压到Y栈里，此时点击前进，则把从Y栈里取出记录（d），并把当前页面（c）压到X栈里。 五、课后思考： 1. 我们在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保 存临时变量呢？用其他数据结构不行吗？ 举例说，假如有下面程序： 整个程序的函数活动时间可以表示为： 可以看到，函数的调用有完美的嵌套关系——调用者的生命期总是长于被调用者的生命期，并且后者在前者的之内。 这样，被调用者的局部信息所占空间的分配总是后于调用者的（后入），而其释放则总是先于调用者的（先出），所以正好可以满足栈的LIFO顺序，选用栈这种数据结构来实现调用栈是一种很自然的选择。 作者：RednaxelaFX 链接：https://www.zhihu.com/question/34499262/answer/59415153 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 《数据结构与算法之美》05——栈 标签：链接 block 时间 数据集 als public 数组元素 其他 info 原文地址：https://www.cnblogs.com/liang24/p/13149674.html// 基于数组实现的顺序栈
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; //栈的大小
// 初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入栈操作
public boolean push(String item) {
// 数组空间不够了，直接返回false，入栈失败。
if (count == n) return false;
// 将item放到下标为count的位置，并且count加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop() {
// 栈为空，则直接返回null
if (count == 0) return null;
// 返回下标为count-1的数组元素，并且栈中元素个数count减一
String tmp = items[count-1];
--count; return tmp;
}
}
public class LinkedListStack : StackBase
{
private MyLinkedListNode head; // 数组
private int count; // 栈中元素个数
private int n; //栈的大小
public LinkedListStack(int n)
{
this.n = n;
this.count = 0;
this.head = new MyLinkedListNode(null);
}
public override bool Push(string item)
{
if (count >= n) return false;
MyLinkedListNode node = new MyLinkedListNode(item);
node.Next = head.Next;
head.Next = node;
count++;
return true;
}
public override string Pop()
{
if (count == 0) return null;
string item = head.Next.Data;
head.Next = head.Next.Next;
count--;
return item;
}
public class MyLinkedListNode
{
public MyLinkedListNode(string data)
{
Data = data;
}
public string Data { get; set; }
public MyLinkedListNode Next { get; set; }
}
}
int main() {
a();
return 0;
}
void a() {
b();
}
void b() {
c();
}
void c() {
}
上一篇：C++11封装智能指针