《数据结构与算法c++版第三版》第四章习题答案 |21xrx.com

《数据结构与算法c++版第三版》第四章习题答案

2023-06-30 17:04:26 深夜i -- --

数据结构算法 C++版第三版第四章习题答案

《数据结构与算法c++版第三版》是一本很好的学习数据结构和算法的教材。第四章是关于栈和队列的内容，这里提供一些关于第四章习题的解答。

4.1 问题：

栈是一种后进先出的数据结构，请判断一个从左到右的字符串是否是回文串。

解答：

可以使用栈来解决这个问题。先遍历字符串，将所有字符依次压入栈中。接着再遍历字符串，依次弹出栈中的顶部元素，与字符串中的字符进行比较。如果所有字符都匹配成功，则该字符串是回文串。

代码实现：

bool is_palindrome(string str) {

stack s;

int len = str.size();

for (int i = 0; i < len; i++) {

s.push(str[i]);

}

for (int i = 0; i < len; i++) {

char c = s.top();

s.pop();

if (c != str[i])

return false;

}

return true;

}

4.2 问题：

队列是一种先进先出的数据结构，请设计一个队列，能够实现以下操作：

1. 插入元素

2. 删除元素

3. 获取队列中最大值

解答：

可以使用双端队列来解决这个问题。维护一个单调递减的双端队列，队列中存放的是元素的下标。在插入一个新的元素时，先判断队列中的最后一个元素是否比该元素小，如果小，就将该元素从队尾加入队列。如果大，则从队尾逐个弹出队列中比该元素大的元素，再将该元素加入队尾。在删除元素时，只需要弹出队头。获取队列中的最大值时，直接返回队头所对应的元素即可。

代码实现：

class MaxQueue {

public:

MaxQueue()

int max_value() {

return dq.empty() ? -1 : nums[dq.front()];

}

void push_back(int value) {

nums.push_back(value);

while (!dq.empty() && value > nums[dq.back()]) {

dq.pop_back();

}

dq.push_back(nums.size() - 1);

}

int pop_front() {

if (dq.empty())

return -1;

int front = dq.front();

if (front == nums.size() - 1) {

dq.pop_front();

}

nums.erase(nums.begin());

if (!dq.empty() && dq.front() <= front) {

dq.pop_front();

}

return front == nums.size() ? -1 : nums[front];

}

private:

vector nums;

deque dq;

};

上一篇: idea打包java可执行jar包

下一篇: 如何在VC++中恢复默认界面？

评论区

()

相似文章