【数据结构】栈

【数据结构】栈

Richard

April 8, 2019

613views

No comments

971 words

数据结构与算法

今天先来两个简单的数据结构——栈和队列吧。

栈 (Stack)

栈是一种线性结构，与数组相比，栈对应的操作是数组的子集。

它只能从一端添加元素，也只能从一端取出元素(这一端称之为栈顶)。

Stack这种数据结构用途很广泛，在计算机的使用中，大量的运用了栈，比如编译器中的词法分析器、Java虚拟机、软件中的撤销操作（Undo）、浏览器中的回退操作，编译器中的函数调用实现等等。

栈的实现

函数说明

函数	说明	复杂度
void push(int data)	向栈中加入元素	平均O(1)
int pop()	弹出栈顶元素	平均O(1)
int top()	查看栈顶元素	O(1)
int size()	获取栈中元素个数	O(1)
bool empty()	判断栈是否为空	O(1)

push和pop操作在最后面进行，有可能触发resize，但均摊来算是O(1)的。

栈可以用数组和链表来实现，这里我用链表写了一遍。

链表实现

#include <list>
using namespace std;
//我之前写过链表了，所以这里直接用C++里面的list吧

class Stack
{
private:
    list<int> value;

public:
    /*入栈，出栈*/
    void push(int data) { value.push_back(data); }
    int pop()
    {
        int tmp = top();
        value.pop_back();
        return tmp;
    }

    /*栈信息*/
    int top() { return value.back(); }
    int size() { return value.size(); }
    bool empty() { return value.empty(); }
};