栈 (stack)
是限定仅在表尾进行插入与删除的线性表，栈中允许插入和删除的一端叫做栈顶 (top)，另一端叫做栈底 (bottom)。不含任何数据元素的栈称为空栈。栈中元素的个数称为栈的高度或长度。
将元素插入到栈的操作称为入栈（或进栈）操作，元素入栈后就变成新的栈顶。将元素从栈中删除的操作称为出栈（或退栈）操作，出栈时被删除的总是原来的栈顶元素。因此每次出栈的元素总是当前栈中“最新”的元素，即最后入栈的元素，而最先插入的元素被放到了栈底，待其他元素都已经出栈，栈底元素才能被删除。
栈的操作是按照先进先出（LIFO,Last In First Out) 原则进行的。
定义
给出栈类的定义（基本方法一致）：
const int StackSize = 1024;
template<class T>
class SeqStack {
public:
SeqStack() { top = -1; } // 构造函数
void Push(T); // 压栈
T Pop(); // 出栈
T GetTop() ; // 获取栈顶元素
bool Empty(); // 判断空栈
int Size() { // 栈大小
return top+1;
}
private:
T data[StackSize];
int top;
};
顺序栈
栈的顺序储存结构称作顺序栈，类似于顺序表，顺序栈也可以用数组来实现，由于栈底位置固定不变，因此可以将栈底设置在数组两端的任一端，通常把下标为 0 的一端作为栈底。同时设置 top 顶指针作为栈顶位置。当进行入栈操作时，top++，当出栈时，top–。当栈为空时，top=-1。设置数组大小为 StackSize，当栈满时，top=StackSize-1。
下面是顺序栈程序：
/*************************************************************************
> File Name: SeqStack.cpp
> Author: Netcan
> Mail: 1469709759@qq.com
> Created Time: Thu 23 Apr 2015 22:18:19 CST
************************************************************************/
#include<iostream>
using namespace std;
const int StackSize = 1024;
template<class T>
class SeqStack {
public:
SeqStack() { top = -1; }
void Push(T);
T Pop();
T GetTop() ;
bool Empty();
int Size() {
return top+1;
}
private:
T data[StackSize];
int top;
};
template<class T>
void SeqStack<T>::Push(T x) {
if(++top >= StackSize) throw "上溢";
data[top] = x;
}
template<class T>
bool SeqStack<T>::Empty() {
if(top == -1)
return true;
return false;
}
template<class T>
T SeqStack<T>::Pop() {
if(Empty()) throw "下溢";
return data[top--];
}
template<class T>
T SeqStack<T>::GetTop() {
if(Empty()) throw "下溢";
return data[top];
}
int main() {
SeqStack<int> stack;
for(int i=1; i<=10; ++i)
stack.Push(i);
for(int i=1; i<=10; ++i) {
cout << "stack 顶元素：" << stack.GetTop() << "大小：" << stack.Size() << endl;
stack.Pop();
}
return 0;
}链栈
栈的链式储存结构称为链栈，其实现原理类似于单链表，结点结构和单链表相同。由于插入和删除操作都在表头进行，因此链栈在实现时直接采用栈顶指针指向栈顶元素，无需像单链表一样增加表头结点。
下面给出链栈实现。
/*************************************************************************
> File Name: LinkStack.cpp
> Author: Netcan
> Mail: 1469709759@qq.com
> Created Time: Thu 23 Apr 2015 22:51:37 CST
************************************************************************/
#include<iostream>
using namespace std;
template <class T>
struct Node {
T data;
Node * next;
};
template <class T>
class LinkStack {
public:
LinkStack() {top = NULL;}
~LinkStack();
void Push(T x);
T Pop();
T GetTop() const;
int Size() const;
bool Empty() const{ return (NULL == top)?true:false;}
private:
struct Node<T> * top;
};
template <class T>
void LinkStack<T>::Push(T x) {
Node<T> * s = new Node<T>;
s->data = x;
s->next = top;
top = s;
}
template <class T>
T LinkStack<T>::Pop() {
if(Empty()) throw "下溢！";
T x = top->data;
Node<T> *p = top;
top = top->next;
return x;
}
template <class T>
LinkStack<T>::~LinkStack() {
Node<T> *p = top;
while(top) {
p = top->next;
delete top;
top = p;
}
}
template<class T>
T LinkStack<T>::GetTop() const {
if(Empty()) throw "下溢！";
return top->data;
}
template<class T>
int LinkStack<T>::Size() const {
Node<T> * p = top;
int count=0;
while(p) {
++count;
p = p->next;
}
return count;
}
int main() {
LinkStack<int> stack;
for(int i=1; i<=10; ++i)
stack.Push(i);
for(int i=1; i<=10; ++i) {
cout << "stack 顶元素：" << stack.GetTop() << "大小：" << stack.Size() << endl;
stack.Pop();
}
return 0;
}运行结果如下：
stack 顶元素：10 大小：10
stack 顶元素：9 大小：9
stack 顶元素：8 大小：8
stack 顶元素：7 大小：7
stack 顶元素：6 大小：6
stack 顶元素：5 大小：5
stack 顶元素：4 大小：4
stack 顶元素：3 大小：3
stack 顶元素：2 大小：2
stack 顶元素：1 大小：1
