数据结构（数组模拟与STL）

通过数组模拟

栈

int stk[N], top;

void init() { // 初始化
	top = 0;
}

bool isEmpty() { // 判断是否为空
	return top == 0;
}

bool isFull() {
	return top >= MAX - 1;
}

void push(int x) {
    if (isFull()) // 错误（上溢）
    stk[++top] = x;
}

int pop() {
    if (isEmpty()) // 错误 （下溢）
    top--;
    return stk[top + 1];
}

队列（循环队列）

为了区分队列的空与满，规定 tail -> head 之间至少要有一个空位

int Q[N], head, tail;

void init() {
	head = tail = 0;
}

bool isEmpty() {
	return head == tail;
}

bool isFull() {
	return head == (tail + 1) % MAX;
}

void enqueue(int x) {
	if (isFull()) // 错误（上溢）
    Q[tail] = x;
    tail = (tail + 1) % MAX;
}

int dequeue() {
	if (isEmpty()) // 错误（下溢）
	x = Q[head];
    head = (head + 1) % MAX;
    return x;
}

链表

使用结构体更快

STL

stack

头文件：#include <stack>

#include <iostream>
#include <stack>
using namespace std;


int main() {
    stack<int> S;

    S.push(3);  // 向栈中压入
    S.push(7);
    S.push(1);
    cout << S.size() << endl; // 栈的大小

    cout << S.top() << endl; // 1
    S.pop(); // 从栈顶删除元素

    cout << S.top() << endl; // 7
    S.pop();

    cout << S.top() << endl; // 3
    S.pop();

    cout << S.empty() << endl; // 判断栈是否为空
    return 0;
}

queue

头文件：#include <queue>

#include <iostream>
#include <string>
#include <queue>
using namespace std;


int main() {
    queue<string> Q;

    Q.push("red"); // 添加
    Q.push("yellow");
    Q.push("bule");

    cout << Q.front() << endl; // red
    Q.pop(); // 删除

    cout << Q.front() << endl; // yellow
    Q.pop();

    cout << Q.front() << endl; // bule
    Q.pop();

    cout << Q.size() << endl;

    cout << Q.empty() << endl;
    return 0;
}

vector

头文件：#include <vector>

#include <iostream>
#include <vector>
using namespace std;

void print(vector<double> V) {
    for (int i = 0; i < V.size(); i++) {
        cout << V[i] << " ";
    }
    cout << endl;
}

int main() {
    vector<double> V;

    V.push_back(0.1);
    V.push_back(0.2);
    V.push_back(0.3);
    V[2] = 0.4; // 可以通过下标法修改，但不能通过下标法创建
    print(V); // 0.1 0.2 0.4

    V.insert(V.begin() + 2, 0.8);
    print(V); // 0.1 0.2 0.8 0.4

    V.erase(V.begin() + 1);
    print(V); // 0.1 0.8 0.4

    cout << V.size() << endl;

    V.clear();
    cout << V.size() << endl;
    return 0;
}

list

头文件：#include <list>

双向链表

#include <iostream>
#include <list>
using namespace std;


int main() {
    list<char> L;

    L.push_front('b'); // [b]
    L.push_back('c'); // [bc]
    L.push_front('a'); // [abc]

    cout << L.front() << endl; // a
    cout << L.back() << endl; // c

    L.pop_front(); // [bc]
    
    return 0;
}

list也可以使用下标表示法访问[],与vector相比元素的插入和删除操作的时间复杂度为O(1)