一、栈的相关知识
栈的定义：
是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶（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;
}
