一、栈的相关知识

栈的定义：

是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out，LIFO）的线性表。

理解栈的定义需要注意：

• 首先他是一个线性表，元素具有线性关系，即前驱后继关系。
• 这里的表尾指的是栈定而不是栈底。
• 栈的插入操作叫做进栈，或者压栈，入栈。栈的删除动作叫做出栈，也叫弹栈。

进栈出栈变化形式：

问题：最先进栈的元素，是不是就只能最后出栈呢？
答：不一定。因为没有对栈内元素出入时间做限制。在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素即可。
举例：有三个数字1,2,3依次进栈，有哪些出栈次序呢？

• 第一种：1,2,3进，3,2,1出。
• 第二种：1进，1出，2进，2出，3进，3出。即1，2，3出。
• 第三种：1,2进，2出，1出，3进，3出。即2,1,3出。
• 第四种：1进，1，2，3进，3出，2出。即1,3,2出。
• 第五种：1，2进，2出，3进，3出，1出。即2,3,1出。
• 不可能为3,1,2出。因为3进，1,2必然进。2在1上面，因此如果3出了，必先出2。

栈的顺序存储结构

• 顺序线性表用数组可以实现，下标为0作为栈底。
• 定义一个top变量来指示栈顶元素在数组中的位置。StackSize为存储栈的长度。因此栈顶位置top必须小徐StackSize。
• 当栈存在一个元素时，top等于0，空栈时top=-1。

两栈共享空间

提出思路：因为有的时候对于两个栈，类型相同，而其中一个利用率不高，另一个却有快溢出迹象的时候，可以将两个栈共享使用，使得利用率提高。
做法：数组有两个端点，两个栈有两个栈底，让一个栈底下标为0，另一个栈底为数组的末端，即下标为n-1。这样两个栈增加元素就是两端点向中间延伸。
由此可见，top1和top2是栈1和栈2的栈顶指针，只要它们俩不见面，两个栈就可以一直使用。
栈1为空时，top1=-1，栈2位空时，top2=n。
问题：什么时候栈满？
答：想想极端情况。

• 若栈2是空栈，栈1的top1=n-1时，栈1满了。反之，当栈1为空栈，top2=0时，为栈2满。
• 但更多的情况，其实就是两个栈见面之时，也就是两个指针相差为1——top1+1=top2为栈满。

使用条件：通常是两个栈的空间需求有相反关系，也即一个栈增长另一个栈缩短。像买股票一样，一个人买入一定有一个你不知道的人在卖出。有人赚钱，另一个人就赔钱。

栈的链式存储结构

• 规定栈顶放在单链表的头部。
• 链栈的好处是不用过多考虑栈满的情况，除非内存已经没有可以使用的空间。如果真的发生，那此时计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题了。
• 对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top==NULL的时候。

二、代码实现

顺序栈的代码实现

//SeqStack.h
#ifndef SEQSTACK_H_
#define SEQSTACK_H_
const int StackSize = 40;
class SeqStack
{
private:
    int top;
    int num[StackSize];
public:
    SeqStack();
    ~SeqStack();
    void Push(int e);
    void Pop();
    bool isempty();
    bool isfull();
    void clear();
    void Print();
};
#endif

头文件SeqStack.h，包含了入栈出栈判断里面是否是满的以及清空等功能。
这个栈存储了一个int数组。

#include<iostream>
#include"SeqStack.h"
using std::cout;
using std::endl;
SeqStack::SeqStack():top(-1){}
SeqStack::~SeqStack(){}
void SeqStack::Push(int e)
{
    if(isfull())
    {
        cout << "Stack is Full!Push failed." << endl;
        return;
    }
    num[++top] = e;
}
void SeqStack::Pop()
{
    if(isempty())
    {
        cout << "Stack is Empty!Pop failed." << endl;
        return;
    }
    top--;
}
bool SeqStack::isempty()
{
    if(top == -1)
    {
        cout << "Stack is empty!" << endl;
        return true;
    }
    return false;
}
bool SeqStack::isfull()
{
    if(top == StackSize - 1)
    {
        cout << "Stack is full!" << endl;
        return true;
    }
    return false;
}
void SeqStack::clear()
{
    if(isempty())
        cout << "SeqStack is already empty!" << endl;
    while(top!=-1)
    {
        Pop();
        top--;
    }
}
void SeqStack::Print()
{
    if(isempty())
        cout << "No elements printed." << endl;
    for(int i=0;i<top;i++)
        cout << num[i] << " ";
    cout << endl;
}

函数实现SeqStack.cpp，可以自己建立一个简单的程序验证一下，这里不再赘述。

链栈的代码实现

//LinkStack.h
#ifndef LINKSTACK_H_
#define LINKSTACK_H_
class LinkStack
{
private:
    struct StackNode
    {
        int num;//存储数据
        StackNode * next;//next指针
    };
    StackNode * top;
    int length;
public:
    LinkStack();
    ~LinkStack();
    void Push(int e);
    void Pop();
    bool isempty();
    void clear();
    void Print();
};
#endif

链栈头文件，存储变量和方法。

//LinkStack.cpp
#include<iostream>
#include"LinkStack.h"
using std::cout;
using std::endl;
LinkStack::LinkStack()
{
    top = NULL;
    length = 0;
}
LinkStack::~LinkStack()
{
}
void LinkStack::Push(int e)
{
    StackNode * p = new StackNode;
    p->num=e;
    p->next=top;
    top=p;
    length++;
}
void LinkStack::Pop()
{
    StackNode * p = new StackNode;
    if(top == NULL)
    {
        cout << "The LinkStack is empty!Cannot pop!" << endl;
        return;
    }
    p=top;
    top=top->next;
    delete p;
    length--;
}
void LinkStack::clear()
{
    while(top)
    {
        StackNode * temp = top;
        top = top->next;
        delete temp;
        length--;
    }
}
void LinkStack::Print()
{
    if(top == NULL)
    {
        cout << "No elements!" << endl;
        return;
    }
    StackNode * temp = top;
    while(temp)
    {
        cout << temp->num << " ";
        temp = temp->next;
    }
    cout << endl;
}