正文之前
这几天深受《C++ Primer》困扰，昨晚看拷贝构造函数以及析构函数那一块真是看到快哭了。所以今天找点别的看看，缓解下因为看不懂Primer的书籍而带来的不快感。自然而然的，当年为了考研买的王道单科《数据结构》成了我的首要对象。所以今日继续开始看王道，从第三章开始，先讲栈的一些细节。当然，等我复活了 我又会开始追《C++ Primer》开始怼，不过今天还是先算了吧。我需要勇气，可我没有梁静茹！
正文
1、 顺序存储实现栈
出于习惯，我还是采用指针传递对象的地址的方式通过函数对实参进行操作，引用其实也可以，不过为了方便大家的阅读，还是用指针吧！
#include <iostream> using namespace std; #define maxsize 20typedef 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 个
还有一个题目懒得讲了，是概念性的错误，大家伙自个好好看书啊哈！
正文之后
差不多了，栈能讲的不多，而且那些要讲深的动辄就是几百行代码，我就偷个懒，大概把考研书籍中讲到的关于栈的一些知识点提炼出来了！ 有兴趣的慢慢看。我有点困，先撤了！
