type
status
date
slug
summary
tags
category
icon
password
Last edited time
Mar 22, 2025 04:46 PM
课堂总结
Stacks
linked list 实现的Stack的时间和空间复杂度：
linked list stack代码实现：
也给出用数组实现的Stack代码：
但是存在的问题是：
- Overflow和underflow问题：当调用
pop()方法时，如果栈是空的，就会underflow，同时由于capacity固定，也会有overflow问题
- 这里的设置允许空指针插入
- 所谓的Loitering问题就是在
pop()方法中，返回了数组s中的一个值，但我们没有清除数组中的该位置，这意味着s仍然持有对该对象的引用，即使N已经递减了。这样子GC不会自动回收。可以手动清空数组引用。
所以可以使用resized array 来解决，具体地，当stack 满的时候，double size。
可以使用均摊分析（amortized analysis）来分析push操作的时间复杂度。比如下图，当array的长度达到时，要次copy数组的操作。除以之后，就是3，所以一共是3N。
如果栈的长度变小，那么就要缩减，当元素的个数变成数组的长度的一半时再缩减可以吗？答案是不行，因为在临界状态如果一个元素反复push，pop，那么每次都会复制。所以当预算的个数变成数组的四分之一时再缩减一半。
代码实现：
至于内存占用：
在[8N,32N]之间，N为元素的个数。
总结：
链表实现：
• 每个操作在最坏情况下都能保证常数时间。
• 需要额外的时间和空间来处理链表中的链接（指针）。
动态数组实现：
• 每个操作的平均时间是常数时间（摊销时间）。
• 由于数组的特性，相比链表，内存空间的浪费较少。
Queues
对于链表实现：队列的dequeue操作和pop操作一样，都是把链表的第一个元素踢出去。队列的enqueue操作则需要找到链表的最后一个元素，因此需要存储last节点，然后把oldlast的next指向的新的last，注意要处理边界情况。
代码如下：
对于队列的数组实现，课上给了一个hint，留作exercise实现。
generics（范型）
下面两张图分别给了范型stack的实现：
因为java不允许创建范型数组，所以只能创建一个 Object 数组，然后进行强制类型转换。
Iterators（迭代器）
迭代器是有hasNext()和next()方法。
有了迭代器，就可以对可迭代对象写出优雅的代码。
课上还讲了，bag api 就是可以用没有pop的stack和没有dequeue的queue实现。
Stack and Queue Applications
这一节讲了栈和队列的一些应用。
Function calls 编译器实现函数的方法就是用到了stack。 比如返回地址，程序需要知道自己执行完毕后要返回到那里进行执行。
Arithmetic expression evaluation
还可以用双栈法（Dijkstra’s Two-Stack Algorithm）来求值完全括号化的算术表达式。
习题
Interview Questions
[!Q1] Queue with two stacks. Implement a queue with two stacks so that each queue operations takes a constant amortized number of stack operations.
Note: these interview questions are ungraded and purely for your own enrichment. To get a hint, submit a solution.
第一题是想要用两个栈实现一个队列，队列是fifo结构，stack时filo结构，要求均摊下来常数时间。我们可以想到enqueue和dequeue用不同的栈，enqueue插入一个栈中，如果要dequeue的时候，从第一个栈中pop出来push到另一个栈中，然后在第二个栈中pop出第一个。这样子均摊下来一定是参数时间，因为每个元素只会被移动一次栈。
代码实现
[!Q2] Stack with max. Create a data structure that efficiently supports the stack operations (push and pop) and also a return-the-maximum operation. Assume the elements are real numbers so that you can compare them.
这道题是希望从栈中返回最大的元素。一开始想到的做法是维护一个变量来存最大值，这样虽然push的时候可以比较，但是pop的时候如果pop出去的元素是最大值，那就要从剩下的元素中找最大值，就要进行遍历了。所以想到的方法是再维护一个栈，用来存最大值。返回最大值的时候返回栈中的第一个元素就可以。
代码如下：
[!Q3] Java generics. Explain why Java prohibits generic array creation.
第三道题则是问为什么java的数组不能创建范型呢。
为了与旧版 Java 代码兼容，Java 的泛型是在编译时进行检查，但在运行时并不存在泛型类型信息。编译器会将所有泛型信息“擦除”，把泛型类型转换成原始类型。如果允许直接创建泛型数组，例如 T[] array = new T[n]，由于类型擦除，在运行时无法得知数组实际存储的元素类型。而数组又是需要维护运行时类型信息的，这会导致类型安全问题。
Deques and Randomized Queues
Deque
A double-ended queue or deque (pronounced “deck”) is a generalization of a stack and a queue that supports adding and removing items from either the front or the back of the data structure. Create a generic data type
Deque that implements the following API:
这道题主要是要完成一个双向队列，用指针时间比较好，需要一个prev指针和一个next指针。也需要一个头节点firset和尾节点last。写的时候需要注意临界情况，移除的时候，需要考虑当前如果只有一个节点的问题，以及要防止loitering问题。插入的时候也要注意没有节点，插入的时候只有一个的情况。
Randomized queue
Randomized queue. A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random among items in the data structure. Create a generic data type
RandomizedQueue that implements the following API:这道题的要点是需要实现一个随机队列。要求remove的时候要uniformly随机。这道题比较适合用数组做。正常实现自动resize之后，只需要实现sample方法即可，思路是随机一个[0, size-1]的数字做数组的索引remove出来，然后把最后一个元素放到remove元素的位置。
这题的难点在于迭代器也需需要用uniformly 顺序返回。方法用的是初始化的时候要洗牌一次。
可以用Fisher-Yates 洗牌算法例如：
Fisher-Yates洗牌算法可以用归纳法证明，只要证明每次排列的总概率是 即可， 因为对应全排列，一共有这么多种可能。
第一次是,第二次是是, 相乘可以进行很容易的证明。
Client
Write a client program
Permutation.java that takes an integer k as a command-line argument; reads a sequence of strings from standard input using StdIn.readString(); and prints exactly k of them, uniformly at random. Print each item from the sequence at most once.第三题的客户端只需要用第二题的随机队列就可以。首先思路是先全部enqueue，再dequeue k个，
不过题目提到
(For an extra challenge and a small amount of extra credit, use only one
Deque or RandomizedQueue object of maximum size at most k.)如过只用最大大小为k的随机队列可以吗，这是代码实现：
这里用到的算法就是为了确保每个元素留在水池中的概率为 k/n， 相当于 module1 里面只抽取1个元素，这里是抽取k个元素。用归纳法即可证明。
- 作者:很久不是自己
- 链接:https://weibo.com/article/algorithms-part1-module4
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。