《数据结构与算法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;

};

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政