1 栈-OOP

栈实现的是后进先出（先进后出）策略，队列实现的是先进先出策略。

1 栈

栈上的操作主要包括

1. INSERT操作称为压入（PUSH）。注意上溢问题，即往满栈里添加元素。
2. 无参数版本的DELETE操作称为弹出（POP）。注意下溢问题，即从空栈上取元素。
3. STACK-EMPTY判断栈是否为空

栈的实现思路

用一个数组s[1..n]来实现一个最多可容纳n个元素的栈。该数组有一个参数s.top用来指示要插入元素的位置，s[0]是栈底，s[s.top-1]是栈顶。

伪代码

1.判断栈是否为空：

empty()
if stack.top == 0
    return true
else 
    return false

2.插入push

if top > size
    error"upflow"
else
    stack[top] =x;
    top=top+1 

3.删除pop

if empty()
    error "underflow"
else
    pop = pop-1
    return stack[pop]   

栈的模板实现

#include <iostream>

template<class T, const int size = 100>
class Stack{
    T s[size];
    int top;
public:
    Stack():top(0){}
    bool empty(){ return top == 0;}
    T pop(){
        if(top <= 0){
            std::cerr << "下溢";
            exit(0);
        }
        return s[--top];
    }
    void push(T t){
        if(top >= size){
            std::cerr << "上溢";
            exit(0);
        }
        s[top++] = t;
    }
};
//测试代码
int main(){
    const int size = 10;
    Stack<int, size> si;
    for (int i = 0; i < size; i++){
        std::cout << i;
        si.push(i);
    }
    std::cout << std::endl;
    while(!si.empty())
        std::cout << si.pop();
}

在一个数组中实现两个栈，使当两个栈元素个数之和不为n时，都不会上溢。PUSH和POP操作的运行时间都为O(1)

要2个栈公用一个存储空间，栈顶指针从两端指针开始，当两端指针指向同一个内存时则发生上溢。

#include <iostream>

template<class T, const int size = 100>
class Stack{
    T s[size];
    int top1;
    int top2;
public:
    Stack():top1(0),top2(size-1){}
    bool empty(int index){ 
        if(index == 1)
            return top1 == 0;
        else
            return top2 == size-1;
    }
    T pop(int index){
        if(index ==1 && top1 == 0){
            std::cerr << "下溢";
            exit(0);
        }
        if(index == 2 && top2 == size-1){
            std::cerr << "下溢";
            exit(0);
        }
        if(index ==1 )
            return s[--top1];
        else
            return s[++top2];
    }
    void push(T t, int index){
        if(top1 == top2){
            std::cerr << "上溢";
            exit(0);
        }
        if(index == 1)
            s[top1++] = t;
        else
            s[top2--] = t;
    }
};

int main(){
    const int size = 10;
    Stack<int, size> si;
    for (int i = 0; i < 4; i++){
        std::cout << i;
        si.push(i,1);
    }
    std::cout << std::endl;
    for (int i = 0; i < 5; i++){
        std::cout << i;
        si.push(i,2);
    }
    std::cout << std::endl;
    while(!si.empty(1))
        std::cout << si.pop(1);
    std::cout << std::endl;
    while(!si.empty(2))
        std::cout << si.pop(2);
}