3.1 栈（顺序栈和链栈）_顺序栈和链栈的时间复杂度

栈

1.栈的定义

1.1栈的定义

栈是限定在表尾进行插入和删除的线性表。栈又称为后进先出的线性表，简称LIFO结构。

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数元素的栈称为空栈。

栈的插入操作，也叫做进栈，也称为压栈、入栈。栈的删除操作，叫做出栈，也称作弹栈。

栈有两种实现方式，一种是由数组实现的栈称为顺序栈，另一种是由链表实现的栈，称为链栈。

1.2进栈出栈变化形式

最先进栈的元素不一定最后出栈。

如：1、2、3一次进栈，会有哪些出栈顺序？

1. 1、2、3依次进，3、2、1依次出
2. 1进，1出，2进，2出，3进，3出
3. 1、2依次进，2、1依次出，3进，3出
4. 1、2依次进，2出，3进，3出，1出
5. 1进，1出，2、3依次进，3、2依次出

由这个例子可以看出，栈是很灵活的。

2.栈的抽象数据类型

栈的常用操作如下：

• 出栈：pop（）
• 压栈：push（elem）
• 获取栈顶元素：top（）
• 判断栈是否为空：empty（）
• 返回栈的大小：size（）

2.1顺序栈

顺序栈是用数组来实现的，由于如果在数组第一个元素进行插入删除元素的时间复杂度为O(n),而在数组最后一个元素位置进行插入删除的时间复杂度只有O(1),因此，采用下标为0的一端作为栈底。我们定义一个top变量来指示栈顶元素在数组中的位置，top的值小于栈存储长度。

顺序栈的进栈、出栈操作的时间复杂度都是O(1).

顺序栈的C++实现如下：

#define SIZE 100    //创建栈默认的大小
class ArrayStack{
    public:
    ArrayStack();                //构造函数
    ArrayStack(int val);         //有参构造
    ~ArrayStack();               //析构函数
    void push(int elem);         //压栈
    void pop();                  //出栈
    int top();                   //返回栈顶元素
    bool empty();                //判断栈是否为空
    int size();                  //返回栈的大小
    private:
    int *_arr;                   //数组地址，即栈底
    int _size;                   //栈的长度，_size-1为栈顶指针
};
ArrayStack::ArrayStack(){
    _arr=new int[SIZE];
    _size=0;
}
ArrayStack::ArrayStack(int val):_arr(nullptr),_size(val){}
~ArrayStack::ArrayStack(){
    if(_arr){
        delete[]_arr;
        _arr=nullptr;
    }
}
void ArrayStack::push(int elem){
    arr[_size++]=elem;
}
void ArrayStack::pop(){
    arr[--_size]=0;
}
int ArrayStack::top(){
    return _arr[_size];
}
bool ArrayStack::empty(){
    return (_size>0)?true:false;
}
int ArrayStack::size(){
    return _size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

2.2链栈

链栈的头指针就是栈顶指针，栈顶放在单链表的头部，链栈没有虚拟头结点。并且对于链栈来说，不存在栈满的情况。

**进栈操作是在创建一个新的结点，将栈顶指针赋值给新的结点的后继，然后将新的结点的地址赋值给栈顶指针。**假设新创建的结点为s，值为elem，链栈对象为this，则操作如下：

ListNode *s=new ListNode(elem);
s->next=this->top;
this->top=s;
1
2
3

**出栈操作是先设置一个变量p存放栈顶元素，然后将top指针指向栈顶元素的下一个元素，释放掉p。**操作如下：

ListNode *p=this->top;
this->top=p->next;
delete p;
1
2
3

与顺序栈一样，链栈进栈出栈的时间复杂度都是O(1).

C++的链栈实现如下：

class ListStack {
public:
    struct ListNode {
        ListNode(int val) :val(val), next(nullptr) {}
        int val;
        ListNode* next;
    };
    ListStack();                 //链栈的默认构造函数
    ~ListStack();                //析构函数
    void push(int elem);         //压栈
    void pop();                  //出栈
    int top();                   //返回栈顶元素
    bool empty();                //判断栈是否为空
    int size();                  //返回栈的大小

private:
    ListNode* _top;              //栈顶指针
    int _size;                   //链栈的大小
};
ListStack::ListStack() {
    _top = nullptr;
    int _size = 0;
}
ListStack::~ListStack() {
    ListNode* p = nullptr;
    while (!this->_top) {
        p = this->_top;
        this->_top = p;
        delete p;
        p = nullptr;
    }
}
void ListStack::push(int elem) {
    ListNode* newNode = new ListNode(elem);
    newNode->next = this->_top;
    this->_top = newNode;
    ++_size;
}
void ListStack::pop() {
    ListNode* p = this->_top;
    this->_top = p->next;
    delete p;
    --_size;
}
int ListStack::top() {
    if (!this->_top) {
        return -1;
    }
    return this->_top->val;
}
bool ListStack::empty() {
    return (this->_top) ? true : false;
}
int ListStack::size() {
    return this->_size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

2.3链栈和顺序栈的异同

链栈和顺序栈的异同:

• 链栈和顺序栈时间复杂度相同，都是O(1).
• 顺序栈需要事先确定一个固定的长度，可能会存在内存空间的浪费问题，但它的优势是存取时定位很方便，而链栈要求每个元素都有指针域，但这也增加了内存开销。
• 如果栈的使用过程中元素变化不可预料，有时很小，有时很大，最好使用链栈；反之，如果它的变化在可控范围内，建议使用顺序栈会好一点。