【计算机本科补全计划】王道单科--栈的实现以及一些性质

正文之前

这几天深受《C++ Primer》困扰，昨晚看拷贝构造函数以及析构函数那一块真是看到快哭了。所以今天找点别的看看，缓解下因为看不懂Primer的书籍而带来的不快感。自然而然的，当年为了考研买的王道单科《数据结构》成了我的首要对象。所以今日继续开始看王道，从第三章开始，先讲栈的一些细节。当然，等我复活了 我又会开始追《C++ Primer》开始怼，不过今天还是先算了吧。我需要勇气，可我没有梁静茹！

正文

1、 顺序存储实现栈

出于习惯，我还是采用指针传递对象的地址的方式通过函数对实参进行操作，引用其实也可以，不过为了方便大家的阅读，还是用指针吧！

#include <iostream>
using namespace std;
#define maxsize 20

typedef struct Stack
{
    int a[maxsize];
    int top;
} *pts;

void InitStack(pts ptrs)
{
    ptrs->top=-1;
    for(int i=0;i<20;++i)
        ptrs->a[i]=0;
}

void Push(pts ptrs,int item)
{
    //be care of the maxsize-1 because if top = maxsize - 1, it means that the stack is full,so that we cannot push any item into it .
    if(ptrs->top<maxsize-1)   
        ptrs->a[++ptrs->top]=item;
    else 
        {cout<<"The Stack is Full! Get out!"<<endl;return;};
}

int Pop(pts ptrs)
{
    if(ptrs->top!=-1)
        return ptrs->a[ptrs->top--];
    else 
    {
        cout<<"False ,the stack is empty！"<<endl;
        return 0;
    }
}


bool IsEmpty(pts ptrs)
{
    if(ptrs->top==-1)
    {
        cout<<"The Stack is Empty!!"<<endl;
        return false;
    }
    return true;
}

int main()
{
    pts test = new Stack;
    InitStack(test);
    bool emp=IsEmpty(test);
    if(!emp)
        cout<<"Please fill this Stack"<<endl;
    // but here we can use maxsize because we won't push any item into it,we just query the item of it . 
    for(int i=0;i<maxsize;++i)
        Push(test,i*(i/4)+i%3+3);
    // here the condition to stop is the ptes->top = -1, it means that the stack is empty.
    for(;test->top!=-1;)
        cout<<Pop(test)<<endl;
    delete(test);  // please remind this code because we don't use the shared_ptr,  so we should delete it by ourselves. 
    return 0;
}

上面是用顺序存储实现的，也就是数组，然后我搭配了指针用于传递地址，通过函数改变对象内容。如果要用引用的话，那也是可以的！都差不多，反正就是把具体的对象输入到函数中去，而不是用拷贝的局部变量来进行操作！至于链式存储，我猜大概就是在main函数中定义一个头指针，然后每一次push都会申请一个结构体的动态内存，然后再结合一系列的指针操作（头插法吧，直接把头结点当做栈顶指针好了），最后达到每次push进来的元素都在head指针下，至于另外的栈底，需要在第一次push的时候就准备好一个指针（或者就是判断next指针是否为空应该也行），以备后来pop到empty的用处。pop的话肯定就是head指针下移，然后注意要delete那个元素，不然就是野内存了！！

2、 我做王道的题目，有如下几个地方错了，给大家分享下：

1） 设链表不带头结点，且所有的的操作都在表头进行，则下列最不适合用来做链栈的是__?

A．只有表头结点指针，没有表尾指针的双向循环链表 B．只有表尾结点指针，没有表头指针的双向循环链表 C．只有表头结点指针，没有表尾指针的单向循环链表 D．只有表尾结点指针，没有表头指针的单向循环链表

【正确答案：C】 解析：我真是傻了！！！傻子！！ 循环列表的话，要什么都不能只要表头，从表尾到表头只需要一步，而从表头到表尾则需要整个链表的长度，而在插入的操作中，我们不仅仅要在表头插入一个元素，还要把表尾的next指针指向新的元素！所以如果是表尾指针有的话，那就是O(1),如果是只有表头，那就是O(n)了！！傻逼啊我啊！！！

2） 向一个栈顶指针为top的链栈中插入一个x节点，那么下列语句是正确的是__?

A．top->next=x B．x->next=top->next，top->next=x C．x->next=top，top=x D．x->next=top，top=top->next

【正确答案：C】 解析：我这个地方无语问苍天，我到底脑子烧了还是啥的？幸亏是不考研了？不然这样我自己都得哭死吧？？？?！！！这种超low的错误！？？好歹我的正确率也有21/25吧，居然把分丢在这种地方？？？蓝色part为实际操作过程，粉红色箭头代表着两个指针指向的对象。红色的箭头代表原有的指向！

3） 栈的初始状态为空，当字符序列“ n 1 ”作为对栈的输入序列的话，输出长度为3，可以作为C语言的标识符的输出序列有_?

A．4 B．5 C．3 D．6

【正确答案：C】 解析：好吧，这个地方，我要宣扬一个普世思想，那就是，加入我们按照升序输入某个序列，那么在输出序列的第一个元素之前的元素（比输出序列第一个元素小的）在后面输出的时候一定要按照输入顺序的逆序！！这个铁律，因为你的第一个元素都pop了，那么在此之前是没有pop操作的，所以这个item之前的元素肯定已经push 而且 没有pop了，那么按照先进后出的原则，一定有这个顺序的，只是这些元素输出的过程中是可以掺杂着其他元素的push 与 pop的，所以会有很多种可能，但是如果把这些元素剔除掉的话，一定还是按照逆序。所以，题目中有几种可能的输出： 1、 ## n 1 _ ## 2、 ## n _ 1 ## 3、 ## _ 1 n ## 4、 ## 1 n _ ## 5、 ## 1 _ n ## 五个，没错，不是排列组合的6个，因为 _ n 1 这个序列是不存在的。然后剔除掉数开头的，剩下三个可以作为C语言的标识符！！！答案是C： 3 个

还有一个题目懒得讲了，是概念性的错误，大家伙自个好好看书啊哈！

正文之后

差不多了，栈能讲的不多，而且那些要讲深的动辄就是几百行代码，我就偷个懒，大概把考研书籍中讲到的关于栈的一些知识点提炼出来了！ 有兴趣的慢慢看。我有点困，先撤了！