5.4.1栈实现.md

• 问题：

  • 讨论栈数据结构。使用链表或动态数组在C中实现栈，并且说出选择链表或动态数组的原因。设计的栈接口应完整、一致且易于使用。

• 考察点：

  1. 候选人对基本数据结构的了解
  2. 候选人编写程序来操作这些结构的能力
  3. 候选人为一组程序设计一致的接口的能力

• 解释利弊：

  • 无论选择哪一种，都要向面试官说明两种方法的利弊。
    • 动态数组的主要优点：
      1. 可以随机访问（尽管在栈的实现中，这一点不起作用）
      2. 良好的空间局部性。动态数组中的相邻元素在存储器中往往也是相邻的，于是实现的栈会更快。
    • 动态数组的主要缺点：
      1. 实现起来比链表更复杂。
      2. 扩容的操作费时，因为需要将旧元素从旧数组复制到新数组。
    • 链表的主要优点：
      1. 向头部插入元素的时间复杂度始终是O（1）
      2. 在头部删除元素的时间复杂度始终是O（1）
    • 链表的主要缺点：
      1. 每次插入元素时需要分配内存，分配内存的时间会比较长
      2. 不能随机访问元素
    • 两者的对比：
      1. 插入时间：链表插入元素的时间复杂度始终是O（1）；而动态数组插入元素时，申请到的内存可能会满了，这时就必须扩容，扩容的操作会比较费时。
      2. 访问时间：动态数组访问某元素的时间复杂度始终是O（1）；而链表访问某元素的时间复杂度是O（n）

  代码实现：

// 单链表实现栈
#include <iostream>
#include <forward_list>
using namespace std;

class Stack{
public:
    void push(int x);   // 入栈
    int pop();          // 出栈
    int top();          // 返回栈顶元素
    bool is_empty();    // 返回栈是否为空

private:
    std::forward_list<int>::iterator p;// 栈顶指针
    std::forward_list<int> linklist;// 单链表
};

void Stack::push(int x){
    this->linklist.push_front(x);
    this->p = this->linklist.begin();
}

int Stack::pop(){
    if (this->linklist.empty()){
        return -1;
    }
    int ans = *this->p;
    this->linklist.pop_front();
    this->p = this->linklist.begin();
    return ans;
}

int Stack::top(){
    if (this->linklist.empty()){
        return -9999;
    }
    return *this->p;
}

bool Stack::is_empty(){
    return this->linklist.empty();
}

int main(){
    Stack stack;
    std::cout<< (stack.is_empty() ? "true" : "false") << endl;// true

    stack.push(1);
    std::cout<< stack.top() << endl;// 1

    stack.push(2);
    std::cout<< stack.top() << endl;// 2

    stack.pop();
    std::cout<< stack.top() << endl;// 1
    std::cout<< (stack.is_empty() ? "true" : "false") << endl;// false

    stack.pop();
    std::cout<< stack.top() << endl;// -9999
    std::cout<< (stack.is_empty() ? "true" : "false") << endl;// true

    return 0;
}