【CPP】《程序员面试金典》习题(3)——栈和队列
【CPP】《程序员面试金典》习题(3)——栈和队列
ZifengHuang
发布于 2020-07-29 16:14:59
发布于 2020-07-29 16:14:59
代码可运行
运行总次数：0
代码可运行
这次的题更少了，题目的主题是栈和队列，最值得注意的是活用两个栈可以组合完成很多事情。
栈和队列这一章书中提到的有用的点有以下几个：
- 多个栈可以完成排序算法
- 可以用环状数组来制作动态大小的栈
- 利用栈的顺序性，用额外的栈来储存关键值（如最大最小）可以降低空间消耗
- 用两个栈可以模拟队列，反转元素的过程消耗很大，可以延迟元素的移动来降低消耗
- 记不清具体API的时候可以问问面试官，一般都没什么事
执行排名和时间受到LeetCode服务器的不稳定限制因而只有参考价值，重点不是题怎么写而是题目解法带来的算法启发。
这一次有的题目本身描述就很不清晰，有些遗憾。
代码保存在: https://github.com/ZFhuang/LeetCodes/tree/master/CC150
03.01 三合一【简单】
描述如何只用一个数组来实现三个栈。
你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标，value表示压入的值。
构造函数会传入一个stackSize参数，代表每个栈的大小。
示例1:
输入：
["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"]
[[1], [0, 1], [0, 2], [0], [0], [0], [0]]
输出：
[null, null, null, 1, -1, -1, true]
说明：当栈为空时`pop, peek`返回-1，当栈满时`push`不压入元素。
示例2:
输入：
["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"]
[[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]]
输出：
[null, null, null, null, 2, 1, -1, -1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/three-in-one-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法一
public:
//传统一维数组,74.2%,84ms
//一维数组实现，采用按照3来划分三个栈，长度是静态的
//这道题耗时差别很大
//数组也可以用向量vector来替代，效率接近
//可以借助循环数组的想法做成大小动态适应的栈，但是代码会复杂很多而且效率也会降低
int* stack;
int p[3];
int stackSize;
TripleInOne(int stackSize) {
stack = new int[stackSize * 3];
this->stackSize = stackSize;
p[0] = 0;
p[1] = 1;
p[2] = 2;
}
void push(int stackNum, int value) {
//栈满时跳出
if ((p[stackNum] - stackNum + 3) / 3 > stackSize) {
return;
}
stack[p[stackNum]] = value;
//入栈加数量
p[stackNum] += 3;
}
int pop(int stackNum) {
//栈空
if (p[stackNum] - 3 < 0) {
return -1;
}
int ret = stack[p[stackNum] - 3];
//出栈退数量
p[stackNum] -= 3;
return ret;
}
int peek(int stackNum) {
//栈空
if (p[stackNum] - 3 < 0) {
return -1;
}
return stack[p[stackNum] - 3];
}
bool isEmpty(int stackNum) {
//栈空
if (p[stackNum] - 3 < 0) {
return true;
}
else {
return false;
}
}03.02 栈的最小值【简单】
请设计一个栈，除了常规栈支持的pop与push函数以外，
还支持min函数，该函数返回栈元素中的最小值。
执行push、pop和min操作的时间复杂度必须为O(1)。
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法一
//使用现有的STL容器vector,6.0%,212ms
//主要问题是min操作的时间复杂度是O(n)
public:
MinStack() {
}
void push(int x) {
stack.push_back(x);
}
void pop() {
if (stack.empty()) {
return;
}
stack.pop_back();
}
int top() {
if (stack.empty()) {
return NULL;
}
return stack.back();
}
int getMin() {
//遍历一次栈
if (stack.empty()) {
return NULL;
}
int min = stack.back();
for (auto i : stack) {
if (i < min) {
min = i;
}
}
return min;
}
private:
vector<int> stack;解法二
//自定义类型使用现有的STL容器vector,93.2%,24ms
//让每个元素都记录下自己以下的栈的最小值，这样可以在O(1)中得到最小值
public:
struct StackElement {
int value;
//每个子栈的最小值保存在元素内
int min;
StackElement(int v, int m) {
value = v;
min = m;
}
};
MinStack() {
}
void push(int x) {
if (!stack.empty()) {
//push时需要判断是否需要更新当前最小值
if (x <= stack.back()->min) {
//更新
stack.push_back(new StackElement(x, x));
}
else {
stack.push_back(new StackElement(x, stack.back()->min));
}
}
else {
stack.push_back(new StackElement(x, x));
}
}
void pop() {
if (stack.empty()) {
return;
}
stack.pop_back();
}
int top() {
if (stack.empty()) {
return NULL;
}
return stack.back()->value;
}
int getMin() {
if (stack.empty()) {
return NULL;
}
//可以直接返回最小值
return stack.back()->min;
}
private:
//注意new得到的是指针，所以为了vector方便也只存放指针
vector<StackElement*> stack;解法三
//将最小值栈划分开来且直接使用容器stack，93.2%,24ms
//将最小值用一个另外的栈来保存，节省点内存也避免了新数据结构的定义
public:
stack<int> s;
stack<int> buf;//最小值栈
MinStack() {
buf.push(INT_MAX);
}
void push(int x) {
//压入时要注意是否需要刷新
if (x <= buf.top()) {
buf.push(x);
}
s.push(x);
}
void pop() {
//当当前弹出的值等于当前栈的最小值时弹出最小值栈
//由于两个栈保持着顺序的稳定所以可以这样
if (s.top() == buf.top())
buf.pop();
s.pop();
}
int top() {
return s.top();
}
int getMin() {
return buf.top();
}03.03 堆盘子【中等】
堆盘子。设想有一堆盘子，堆太高可能会倒下来。
因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。
请实现数据结构SetOfStacks，模拟这种行为。
SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。
此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同
（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。
进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。
当某个栈为空时，应当删除该栈。
当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.
示例1:
输入：
["StackOfPlates", "push", "push", "popAt", "pop", "pop"]
[[1], [1], [2], [1], [], []]
输出：
[null, null, null, 2, 1, -1]
示例2:
输入：
["StackOfPlates", "push", "push", "push", "popAt", "popAt", "popAt"]
[[2], [1], [2], [3], [0], [0], [0]]
输出：
[null, null, null, null, 2, 1, 3]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/stack-of-plates-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法一
//不使用STL，设置空闲链表，93.0%,60ms
//每个栈都是双向链表方便操作
//删除空栈时改为将空栈存入空闲链表中
//申请栈时先尝试从空闲链表分配，加速内存分配
//可以再给空闲链表增加阈值减少无用内存的占用
private:
struct PlateStack {
int* stack;
//双向链表方便操作
PlateStack* next = NULL;
PlateStack* prev = NULL;
int cur = 0;
PlateStack(int cap) {
stack = new int[cap];
}
};
//在用栈表头
PlateStack* use;
//栈表尾
PlateStack* now;
//空闲栈表
PlateStack* del;
int cap;
public:
StackOfPlates(int cap) {
this->cap = cap;
use = new PlateStack(cap);
now = use;
del = new PlateStack(cap);
}
void push(int val) {
//特殊情况跳出
if (cap == 0) {
return;
}
//当指针达到栈尾时申请新栈
if (now->cur == cap) {
newNow();
}
//存入
now->stack[now->cur] = val;
++now->cur;
}
int pop() {
//当试图出栈一个空栈时
if (now->cur == 0) {
//删除并检测是否已经没有元素了
if (!delStk(now))
return -1;
}
//出栈
--now->cur;
int ret = now->stack[now->cur];
//出栈后若栈空则删除栈
if (now->cur == 0) {
delStk(now);
}
return ret;
}
int popAt(int index) {
//从头遍历所需序号的栈
//这部分可以利用双向链表的特性，储存左右两边的栈数量进行加速搜索
PlateStack* find = use;
for (int i = 0; i < index; i++) {
if (find == NULL) {
return -1;
}
find = find->next;
}
//找不到栈时报错
if (find == NULL) {
return -1;
}
//以下类似pop
if (find->cur == 0) {
if (!delStk(find))
return -1;
}
--find->cur;
int ret = find->stack[find->cur];
if (find->cur == 0) {
delStk(find);
}
return ret;
}
//新建栈
void newNow() {
//当空闲链表非空时
if (del != NULL) {
//将空闲链表头取一个作为新栈
now->next = del;
del->prev = now;
del = del->next;
now = now->next;
now->next = NULL;
}
else {
//否则新建
now->next = new PlateStack(cap);
now->next->prev = now;
now = now->next;
now->next = NULL;
}
}
bool delStk(PlateStack* tar) {
//当目标栈是唯一栈时，表示全空
if (!tar || tar->next == NULL && tar->prev == NULL) {
return false;
}
//存在下一个栈时
if (tar->next) {
//存在上一个栈时
if (tar->prev) {
//通过指针重指跳过当前栈
tar->prev->next = tar->next;
tar->next->prev = tar->prev;
}
else {
//只有下一个栈时，此时必然是use栈，也即是栈表头
//更改链表的同时需要改变use的位置
tar->next->prev = NULL;
use = tar->next;
}
}
else {
//没有下一个栈时，此时必然是now栈，也即是栈表尾
//更改链表的同时需要改变now的位置
tar->prev->next = NULL;
now = tar->prev;
}
//重整完链表后，类似new操作将腾出来的栈放到空闲链表头
if (del != NULL) {
tar->next = del;
del->prev = tar;
del = del->prev;
del->prev = NULL;
}
else {
del = tar;
del->prev = NULL;
del->next = NULL;
}
return true;
}
解法二
//样例的使用STL的方法，94.6%,56ms
//使用已经写好的容器能简化代码
public:
StackOfPlates(int cap) {
len = cap;
}
void push(int val) {
if (len == 0) {
return;
}
//栈表空或当前到达栈尾时
if (rec.size() == 0 || rec[rec.size() - 1].size() == len) {
//新建栈并压入数据再压入链表
stack<int> s;
s.push(val);
rec.push_back(s);
}
else {
//直接压入
rec[rec.size() - 1].push(val);
}
}
int pop() {
//栈表非空时
if (rec.size() != 0) {
int r = rec[rec.size() - 1].top();
rec[rec.size() - 1].pop();
//若当前栈空，则弹出栈
if (rec[rec.size() - 1].empty()) {
rec.pop_back();
}
return r;
}
return -1;
}
int popAt(int index) {
//检测是否序号在链表中
if (index < rec.size()) {
//直接用下标访问
int r = rec[index].top();
rec[index].pop();
if (rec[index].empty()) {
rec.erase(rec.begin() + index);
}
return r;
}
return -1;
}
private:
//栈向量嵌套容器
vector<stack<int>> rec;
int len = 0;03.04 化栈为队【简单】
实现一个MyQueue类，该类用两个栈来实现一个队列。
示例：
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明：
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法一
//传统的双栈，进行了状态位优化，100%，0ms
//状态位是用来加速连续的pop和push的
private:
stack<int> stk;
stack<int> lin;
bool pushing;
public:
/** Initialize your data structure here. */
MyQueue() {
//初始是push状态
pushing = true;
}
/** Push element x to the back of queue. */
void push(int x) {
//当当前不是push状态时需要反转一次
//用状态位防止多余的反转
if (!pushing) {
pushing = true;
//将二号栈的内容全部转移到一号栈
//这样使得内容方向反转
while (!lin.empty()) {
stk.push(lin.top());
lin.pop();
}
}
//压入
stk.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
//类似push
if (pushing) {
pushing = false;
while (!stk.empty()) {
lin.push(stk.top());
stk.pop();
}
}
int ret = lin.top();
lin.pop();
return ret;
}
/** Get the front element. */
int peek() {
//类似pop
if (pushing) {
pushing = false;
while (!stk.empty()) {
lin.push(stk.top());
stk.pop();
}
}
return lin.top();
}
/** Returns whether the queue is empty. */
bool empty() {
//利用状态位来读取对应栈的信息
//虽然有两个栈但是它们只有一个会有内容
if (pushing) {
return stk.empty();
}
else {
return lin.empty();
}
}03.05 栈排序【中等】
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
示例1:
输入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
输出：
[null,null,null,1,null,2]
示例2:
输入：
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
输出：
[null,null,null,null,null,true]
说明:
栈中的元素数目在[0, 5000]范围内。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-of-stacks-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法一
//传统的缓冲栈写法,48.5%,144ms
//本质上是进行了动态的插入排序，很慢
private:
stack<int> stk;
stack<int> tmp;
public:
SortedStack() {
}
void push(int val) {
if (stk.empty()) {
stk.push(val);
}
else {
if (stk.top() >= val) {
stk.push(val);
}
else {
//找到正好可以放入新元素的位置
//遍历过的元素放入缓冲区
while (!stk.empty()) {
tmp.push(stk.top());
stk.pop();
if (!stk.empty() && stk.top() >= val) {
break;
}
}
//压入
stk.push(val);
//从缓冲区中把暂存的元素放回
while (!tmp.empty()) {
stk.push(tmp.top());
tmp.pop();
}
}
}
}
//余下操作正常
void pop() {
if (stk.empty()) {
return;
}
stk.pop();
}
int peek() {
if (stk.empty()) {
return -1;
}
return stk.top();
}
bool isEmpty() {
return stk.empty();
}解法二
//优化的写法,91.4%,20ms
//主要是利用滑动两个栈来减少出入栈的次数
public:
SortedStack() {
}
//在两个栈中互相抛接，相当于把目标排列滑动到符合val的中间值
//s2是小于val的栈，s1是大于val的栈
void push(int val) {
//将s2中所有大于val都压入s1
while (!s2.empty() && s2.top() > val) {
//emplace，C11新特性
//类似于push，但是emplace可以直接自动构造对象，功能比push多
//push只能在构造完对象后复制进去
//所以对于需要构造对象的场合用emplace更省内存
//见：https://blog.csdn.net/Kprogram/article/details/82055673
s1.emplace(s2.top());
s2.pop();
}
//将s1中所有小于val的都压入s2
while (!s1.empty() && s1.top() < val) {
s2.emplace(s1.top());
s1.pop();
}
//剩下的位置是等于val的，压入s1
//初始也是压入s1
s1.emplace(val);
}
void pop() {
//将s2(小于val)的元素全部压到s1中
while (!s2.empty()) {
s1.emplace(s2.top());
s2.pop();
}
if (!s1.empty()) s1.pop();
}
//同pop
int peek() {
while (!s2.empty()) {
s1.emplace(s2.top());
s2.pop();
}
return s1.empty() ? -1 : s1.top();
}
//两个栈都空时才空，因为完整的数据是由两个栈一起保存的
bool isEmpty() {
return s1.empty() && s2.empty();
}
private:
//双栈
stack<int> s1, s2;03.06 动物收容所【简单】
有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。
在收养该收容所的动物时，
收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，
或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。
换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，
实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。
允许使用Java内置的LinkedList数据结构。
enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。
dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。
示例1:
输入：
["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [], [], []]
输出：
[null,null,null,[0,0],[-1,-1],[1,0]]
示例2:
输入：
["AnimalShelf", "enqueue", "enqueue", "enqueue", "dequeueDog", "dequeueCat", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []]
输出：
[null,null,null,null,[2,1],[0,0],[1,0]]
说明:
收纳所的最大容量为20000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/animal-shelter-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法一
//记录了时间的队列，操作复杂因此很慢,28.9%,256ms
//加速的关键在于询问考官从而知道编号是自增的，本来就无需记录时间
public:
AnimalShelf() {
time = 0;
}
//将编号和时间一起压入
void enqueue(vector<int> animal) {
if (animal[1] == 0) {
Cat.push({ animal[0],time });
++time;
}
else {
Dog.push({ animal[0],time });
++time;
}
}
vector<int> dequeueAny() {
//要注意队列是使用front得到队列头的
if (Cat.empty() && Dog.empty()) {
return { -1,-1 };
}
if (Cat.empty() && !Dog.empty()) {
vector<int> ret = { Dog.front()[0],1 };
Dog.pop();
return ret;
}
if (Dog.empty() && !Cat.empty()) {
vector<int> ret = { Cat.front()[0],0 };
Cat.pop();
return ret;
}
if (Cat.front()[1] < Dog.front()[1]) {
vector<int> ret = { Cat.front()[0],0 };
Cat.pop();
return ret;
}
else {
vector<int> ret = { Dog.front()[0],1 };
Dog.pop();
return ret;
}
}
vector<int> dequeueDog() {
if (Dog.empty()) {
return { -1,-1 };
}
vector<int> ret = { Dog.front()[0],1 };
Dog.pop();
return ret;
}
vector<int> dequeueCat() {
if (Cat.empty()) {
return { -1,-1 };
}
vector<int> ret = { Cat.front()[0],0 };
Cat.pop();
return ret;
}
private:
queue<vector<int>> Dog;
queue<vector<int>> Cat;
int time;解法二
//由于编号自增，只保存了编号的版本,120ms
public:
AnimalShelf() {
}
void enqueue(vector<int> animal) {
int type = animal[1];
int num = animal[0];
if (type == 1)dogs.push(num);
else cats.push(num);
}
vector<int> dequeueAny() {
//写得花哨其实判断量没有变少
vector<int> res(2, -1);
if (!dogs.empty()) {
res[0] = dogs.front(), res[1] = 1;
}
if (!cats.empty() && (res[0] == -1 || cats.front() < res[0]))
res[0] = cats.front(), res[1] = 0;
if (res[1] == 0)cats.pop();
else if (res[1] == 1) dogs.pop();
return res;
}
vector<int> dequeueDog() {
vector<int> res(2, -1);
if (!dogs.empty())res[0] = dogs.front(), dogs.pop(), res[1] = 1;
return res;
}
vector<int> dequeueCat() {
vector<int> res(2, -1);
if (!cats.empty())res[0] = cats.front(), cats.pop(), res[1] = 0;
return res;
}
private:
queue<int> dogs;
queue<int> cats;本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-03-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
