struct Stack{
    Stack();
    ~Stack();
    void push( int n );
    int  top_element() const;
    void pop();
    bool empty() const;
    bool full() const;
};

我们增加了一个top函数，用来获取栈顶的元素，也就是说把pop这个函数分成两步来做。这么做有两个原因：

为什么函数功能要单一化

设想一下这种可能性，你成功地将元素弹出，但元素赋值失败，无法返回。虽然本例中这种情况不会出现，但对于复杂一点的数据类型这完全可能。

反之的可能性也是有的，即你成功地取出了元素，但弹出这个操作失败了。

此时你处于一个非常尴尬的薛定谔状态——既对，又不对。

pop这个操作本来应该是要么全成功呢，要么全失败的。我们把这种操作叫原子操作。而成功一半，对函数来说就处于两难的境地。

所以函数功能单一化的一个很重要的原因在于：保证函数操作的原子性。

当然除了这个之外还有其他好处，你们现在不一定能体会。记住一点：大多数情况下单一功能的函数比复合功能的函数要好。所以要好好地规划你的函数设计。

# 栈的顺序实现

线性表有两种实现方式：连续的顺序表和不连续的链表，对应到栈，当然也可以有两种（事实上不止）不同的实现方式，即顺序实现方式和链式实现方式。我们先看顺序实现方式。

显然我们用一个数组（顺序表）来存放元素，并且元素与元素之间连续存放。

我们将0号元素固定作为栈底，通过调整栈顶指针来实现栈元素的压栈和弹出：

要注意，我们将栈顶指针放在已有元素的下一位，即下一个空格处。这是为了避免栈空时，栈顶指针为负数，与多数人的直觉不符。

由此我们可以很容易写出对应的代码：

struct Stack{
    int  capacity;
    int  top;
    int* base;
    Stack( int capacity );
    ~Stack();
    void push( int n );
    int  top_element() const;
    void pop();

    bool empty() const;
    bool full() const;
};

这里我们用capacity表示预留的尺寸，top表示栈顶指针，这里简单用下标来表示，base指向预留的内存空间。由于栈底在整个过程中是不会变动的，所以不需要记录栈底，或者说栈底就是base。

Stack::Stack(int capacity){
    this->capacity = capacity;
    base = new int[capacity];
    top = 0;
}

Stack::~Stack(){
    delete[] base;
    top = 0;
    capacity = 0;
}

初始化和销毁很容易理解，不解释。

void Stack::push( int n ){
    assert(top!=capacity);  // 栈不能满
    base[top++] = n;
}

int Stack::top_element() const{
    assert(top!=0); // 栈不能为空
    return base[top-1];
}

void Stack::pop(){
    assert(top!=0);
    top--;  // 简单将指针下移
}

请注意这里压栈和出栈的下标如何变动，自己在纸上画一下，就很容易理解操作的次序、如何判空和如何判满。

你可能还会需要empty和full这两个函数用来判定栈是否为空，或者是否已满，请自行编写。

函数后面的const是什么？

你会注意到

int Stack::top_element() const;

的定义。

我们已经知道const int*表示指针指向的空间不能被修改。函数后的const与此非常类似，表示这个函数不会修改调用他的对象的内部属性。在上一个例子中，这就意味着在top_element这个函数内部，不会去修改top，base和capacity这三个成员。也即函数本身是只读的。

const函数除了申明函数只读之外，还有一个很重要的功能，就是提供给const对象调用。假如有这么一个函数：

void f( const Stack& s); // 传入const的Stack引用

那么在这个函数内部，pop、push都是不能调用的。这非常容易理解，因为这两个函数都会修改s的内部状态，如果可以调用，那么s的const就形同虚设了。

但这个函数可以调用top_element函数，因为他已经申明自己不会修改s的属性了。

我们可以通过代码来验证一下栈的LIFO性质：

int main()
{
    Stack s(10);
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
    for( int i=0; i<5; ++i ){
        cout << s.top_element() << " ";
        s.pop();
    }
    cout << endl;
    return 0;
}

你会得到

5 4 3 2 1

出栈的顺序与进栈的顺序正好相反。

很显然，顺序表示的栈所有操作复杂度都是 $O (1) O(1)$

struct LinkStack{
    Node* head{};
    LinkStack();
    ~LinkStack();
    void push( int value );
    int  top_element() const;
    void pop();
    bool empty();
};

struct Queue{
    Queue();
    ~Queue();
    void in( int n );
    void front_element() const;
    void out();
    bool empty() const;
    bool full() const;
};

struct Queue{
    int* data{nullptr};
    int  front;
    int  rear;
    int  capacity;
    // ...
};

void Queue::in( int n ){
    data[rear] = n;
    rear = (rear+1)%capacity;
}

void Queue::out(){
    front = (front+1)%capacity;
}

void LinkQueue::in( int n ){
    rear->next = new Node;
    rear->next->value = n;
    rear = rear->nxt;
}

void LinkQueue::out(){
    Node* node = front->next;
    front->next = node->next;
    if( node == rear ){
        // 思考下，这里要怎么处理？
    }
    delete node;
}

栈和队列 - 概念与实现

# 栈和队列 - 概念与实现

# 栈

# 栈的概念

# 栈的操作

# 栈的顺序实现