介绍

栈

栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：

栈

结论：先进后出 && 后进先出（Last In First Out），简称为LIFO线性表。

例子：手机任务的返回栈、食堂餐盘从下到上叠起来，送给洗盘子的人，从上到下洗

队列

队列(Queue)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头 (Front),如图所示：

队列

结论：队列的操作原则是先进先出的，所以队列又称作FIFO表(First In First Out)

例子：各种排队

纯 C 用法（函数）

栈

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
#include <stdio.h>

#define MAX_SIZE 1000

int _data[MAX_SIZE], _size = 0;

bool empty() {
    return _size != 0;
}

void push(int x) {
    if (_size < MAX_SIZE-1) {
        _data[_size++] = x;
    }
}

void pop() {
    if (_size) {
        _data[--_size] = 0;
    }
}

int size() {
    return _size;
}

int front() {
    return _size ? _data[0] : 0;
}

int back() {
    return _size ? _data[_size-1] : 0;
}

int main()
{

    push(100);
    printf("%d\n", back());
    push(20);
    printf("%d\n", back());
}

数组转指针：

_data\[([^M].*)\]替换*(_data + \1)

纯C用法（结构体）

栈

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
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>

struct Stack {
    int _data[1000];
    int _size;

    Stack() {          // 初始化
        _size = 0;
    }

    Stack(Stack& q) {  // 拷贝（引用）
        _size = q.size();
        for (int i = 0; i < _size; i++)
            _data[i] = q.at(i);
    }

    bool empty() {     // 是否为空
        return !_size;
    }

    int size() {       // 尺寸
        return _size;
    }

    int at(int x) {    // 数据
        return (x>=0 && x < _size) ? _data[x] : 0;
    }

    void push(int x) { // 放入一个
        if (_size < 1000)
            _data[_size++] = x;
    }

    void pop() {       // 取出一个
        if (_size) {
            for (int i = 0; i < _size-1; i++)
                _data[i] = _data[i+1];
            --_size;
        }
    }

    int front() {      // 获取最新进入的
        return _size?_data[0] : 0;
    }

    int back() {       // 获取最后进入的
        return _size?_data[_size-1] : 0;
    }

    void clear() {
        _size = 0;
    }
};

int main()
{
    Stack s;

    s.push(100);
    printf("%d\n", s.back());
    s.push(20);
    printf("%d\n", s.back());

    Stack s2(s);
    printf("%d\n", s.back());
    s2.clear();
}

C++ 用法

头文件

1
2
#include <queue>
#include <stack>

定义方式

1
2
queue<int> q;
statck<int> q;

常用操作

栈

1
2
3
4
5
s.empty() //如果栈为空返回true，否则返回false  
s.size()  //返回栈中元素的个数  
s.pop()   //删除栈顶元素但不返回其值  
s.top()   //返回栈顶的元素，但不删除该元素  
s.push(x) //在栈顶压入新元素 ，参数X为要压入的元素

队列

1
2
3
4
5
6
q.empty() // 如果队列为空返回true，否则返回false  
q.size()  // 返回队列中元素的个数  
q.pop()   //删除队列首元素但不返回其值  
q.front() // 返回队首元素的值，但不删除该元素  
q.push(x) //在队尾压入新元素 ，X为要压入的元素
q.back()  //返回队列尾元素的值，但不删除该元素

智能指针

迭代器 iterator

1
2
3
stack<int>::iterator i;
for (i = s.begin(); i != s.end(); ++i)
    cout << *i << endl;

例子

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
int main()
{
    queue<int> q;
    stack<char> s;
    char a = 'a', b = 'b';
    
    q.push(1);
    cout << "push 1" << endl;
    cout << "empty:" << q.empty() << endl;
    cout << "push 2" << endl;
    q.push(2);
    cout << "front:" << q.front() << endl;
    q.pop();
    cout << "pop" << endl;
    cout << "front:" << q.front() << endl;
    q.pop();
    cout << "pop" << endl;
    cout << "empty:" << q.empty() <<endl;

    cout << "-----" << endl;
    
    s.push(a);
    cout << "push " << a << endl;
    cout << "size:" << s.size() << endl;
    cout << "top:" << s.top() << endl;
    s.push(b);
    cout << "push " << b << endl;
    cout << "top:" << s.top() << endl;
    s.pop();
    cout << "pop" << endl;
    cout << "top:" << s.top() << endl;
}