概述

栈(Stack)

规则

后入先出（Last In First Out,LIFO）

操作

  • push(X)：在栈的顶部压入元素X
  • pop(): 从栈的顶部取出元素
  • isEmpty()：检查栈是否为空
  • isFull(): 检查栈是否已满

一般情况下，栈还具有 “引用栈顶元素”和”检查栈中是否含有指定数据“的操作

队列(Queue)

规则

先入先出（First In First Out）

操作

  • enqueue(x)：在队列的末端添加元素x

  • dequeue(): 从队列开头取出元素

  • isEmpty(): 检查队列是否为空

  • isFull()：检查队列是否已满

一般情况下，队列还具有 “引用队列第一个元素”和”检查队列中是否含有指定数据“的操作

应用

逆波兰表示法(栈的应用)

逆波兰表示法是一种将操作符写在操作数后面的方法，又叫后缀表示法**，相较于我们日常使用的中缀表示法，它的优势在于不需要括号

例：$（1+2）\times (5+4) $ ==>>$1\space 2 + 5\space 4 + \times $

  1. 将 1 2 压入栈中
  2. 遇到运算符，从栈中取出两个操作数，按运算符运算，例中为+，将运算结果压入栈中，栈中数据变成了 3
  3. 将 5 4 压入栈中，栈中数据变为了 3 5 4
  4. 遇到操作符+ 取出两个操作数5 4 运算结果为9，压入栈中，栈中变为3 9
  5. 遇到操作符$\times$ 取出3 9 运算结果为27

一个并不完善的简单过程

#include<stdio.h>
#include<stdlib.h>
//本程序仅支持0-9的数字运算
int top,stack[1000];
void push(int x){
    stack[++top]=x;
}
int pop(){
    return stack[top--];
}
int main(){
    char s[1000];
    int i,a,b;
    i=0;
    top=0;
    scanf("%s",s);
    while(s[i]!='\0'){
        if(s[i]=='+'){
            a=pop();
            b=pop();
            push(a+b);
        }else if(s[i]=='-'){
            a=pop();
            b=pop();
            push(a-b);        
            
        }else if(s[i]=='*'){
            a=pop();
            b=pop();
            push(a*b);
        }else if(s[i]=='/'){//整除结果
            a=pop();
            b=pop();
            push(a/b);
        }else
        {
            push(s[i]-48);
        }
        i++;
    }
    printf("%d",pop());
    return 0;
}

运行结果：

队列

现有名称为namei且处理时间为timei的n个任务按照顺序排成一列，
CPU通过循环调度法逐一处理这些任务，每个任务最多处理q ms
(这个时间称为时间片)。如果q ms之后任务尚未处理完毕，那么该任务
将被移动至队伍最末尾，CPU随即开始处理下一个任务
    举个例子，假设q是100，然后有如下任务队列。
	A(150) -- B(80) -- C(200) -- D(200)
	首先A被处理100 ms，然后带着剩余的50 ms移动至队尾
	B(80) -- C(200) -- D(200) -- A(50)
	随后B被处理80 ms，在总计第180 ms时完成处理，从队列中消失
	C(200) -- D(200) -- A(50)
	接下来C被处理100 ms，然后带着剩余的100 ms移动至队尾。
	D(200) -- A(50) -- C(100) 
	之后同理，一直循环到处理完所有任务。
	请编写一个程序，模拟循环调度法。
输入
	输入形式如下
	n q
	name1 time1
	name2 time2
	...
	namen timen
	第一行输入表示任务数的整数n与时间片的整数q，用一个空格隔开
	接下来n行输入各任务的信息。字符串namei与timei用一个空格隔开。
输出
	按照任务完成的先后顺序输出各任务名以及结束时间，任务名与对应结束时间用空格隔开，
	每一对任务名与结束时间占一行。
限制
	1 ≤n ≤100 000
	1 ≤q ≤1000
	1 ≤timei ≤50 000
	1 ≤字符串namei的长度 ≤10
	1 ≤timei的和 ≤1 000 000 
	
	输入示例				输出示例 
	5 100					p2 180 
	p1 150					p5 400
	p2 80					p1 450
	p3 200					p3 350
	p4 350					p4 800
	p5 20 

#include<stdio.h>
#include<stdlib.h>
/*
    以数组实验队列
 */
#define MAX 100005
long tail ,head ; //头尾元素位置
typedef struct queue{
    char name[10];
    long time;

}q;
q Q[MAX];
int isEmpty(){
    if(tail==head) return 1;
    return 0;
}
int isFull(){
    if (tail+1==head) return 1;
    return 0;
}
void enqueue(q p){
    if(!isFull()){
        Q[tail]=p;
        tail=(tail+1)%MAX;
    }
}
q dequeue(){
    q p;
    if(!isEmpty()){
        p=Q[head];
        head=(head+1)%MAX;
        
    }
    return p;
}
int main(){
    tail=head=0;
    long elaps=0;
    int i=0;
    q u;
    long n,qtime;
    scanf("%ld %ld",&n,&qtime);
    while(i<n){
        scanf("%s %ld",u.name,&u.time);
        enqueue(u);
        i++;
    }
    while(!isEmpty()){
        u=dequeue();
        if (u.time-qtime<=0)
        {
            elaps+=u.time;
            printf("%s %ld\n",u.name,elaps);
            continue;
        }
        elaps+=qtime;
        u.time-=qtime;
        enqueue(u);
    }
}

运行结果:

STL(C++标准库)

C++库以提供“模板”为主，是指不必预先制定类型的函数或类。

STL为用户提供了多种名为辅容器（Container）的类，用于管理数据集合。在创建动态数组、表、栈、队列等结构时，只需要定义对应的容器。然后就可以通过调用成员函数或方法使用。

stack

函数名 功能 复杂度
size() 返回栈的元素数 O(1)
top() 返回栈顶元素 O(1)
pop() 从栈中取出并删除元素 O(1)
push(x) 向栈中添加元素x O(1)
empty() 当栈为空时返回true O(1) 
#include<iostream>
#include<stack>
using namespace std;
int main()
{
    stack<int> S;
    S.push(1);
    S.push(2);
    S.push(3);
    cout<<"栈的大小："<<S.size()<<endl;
    cout<<"栈顶元素："<<S.top()<<endl;
    S.pop();
    cout<<"栈的大小："<<S.size()<<endl;
    cout<<"栈顶元素："<<S.top()<<endl;


}

运行结果：

通过栈模板实现逆波兰表示

#include<iostream>
#include<stack>
using namespace std;
int main()
{
    int i=0,a,b;
    string s;
    stack<int> stk;
    cin>>s;
    while (s[i]!='\0')
    {

        switch(s[i]){
            case '+':
                a=stk.top();stk.pop();
                b=stk.top();stk.pop();
                stk.push(a+b);
                break;
            case '-':
                a=stk.top();stk.pop();
                b=stk.top();stk.pop();
                stk.push(a-b);
                break;
            case '*':
                a=stk.top();stk.pop();
                b=stk.top();stk.pop();
                stk.push(a*b);
                break;
            default:
                stk.push(s[i]-48);
        }
        i++;
    }
    cout<<stk.top()<<endl;
    return 0;
}

运行结果：

queue

函数名 功能 复杂度
size() 返回队列中的元素数目 O(1)
front() 返回队头的元素 O(1)
pop() 从队列中取出并删除元素 O(1)
push(x) 在队列中添加元素x O(1)
empty() 当队列为空时返回true O(1) 
#include<iostream>
#include<queue>
#include<string>
using namespace std;
int main()
{
   queue<string> que;
   que.push("red");
   que.push("yellow");
   que.push("yellow");
   que.push("blue");

   cout<<que.front()<<"\tnow size:"<<que.size()<<endl;
   que.pop();

   cout<<que.front()<<"\tnow size:"<<que.size()<<endl;
   que.pop();
   
   cout<<que.front()<<"\tnow size:"<<que.size()<<endl;
   que.pop();

   cout<<que.front()<<"\tnow size:"<<que.size()<<endl;
   que.pop();

   return 0;

}

运行结果：

用标准库模板实现上面的队列

#include<iostream>
#include<queue>
#include<string>
using namespace std;
int main()
{
    queue<pair<string,int>> que;
    string name;
    int n,q,t;
    int elaps=0;
    cin>>n>>q;
    while(n--){
        cin>>name>>t;
        que.push(make_pair(name,t));
    }
    pair<string,int> u;
    while(!que.empty())
    {
        u=que.front();
        que.pop();
        if(u.second-q<=0){
            elaps+=u.second;
            cout<<u.first<<' '<<elaps<<endl;
            continue;
        }
        u.second-=q;
        elaps+=q;
        que.push(u);
    }

   return 0;

}

运行结果：

pair是保存对数值的结构体模板，声明时需要在<>中指令两个数据结构。make_pair用于生成一对数值，第一个元素通过first访问，第二个通过second访问

vector

可以在添加元素是增加长度的数组成为动态数组或可变长数组。相对地，必须事先指定长度的是静态数组

STL中的vector（向量）实现了动态数组

函数名 功能 复杂度
size() 返回向量的元素数目 O(1)
push_back(x) 在向量的末尾添加x O(1)
pop_back() 删除向量的最后一个元素 O(1)
begin() 返回指向向量开头的迭代器 O(1)
end() 返回指向向量结尾的迭代器 O(1)
insert(p,x) 在向量中迭代器p指向的位置插入x O(n)
erase(p) 删除向量中迭代器p指向的元素 O(n)
clear() 删除向量中所有元素 O(n) 
#include<iostream>
#include<vector>
#include<string>
using namespace std;
void output(vector<double> v){
    
    for (int i = 0; i < v.size(); i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    vector<double> vec;
    vec.push_back(0.1);
    vec.push_back(0.2);
    vec.push_back(0.3);
    vec[2]=0.4;
    output(vec);
    
    vec.insert(vec.begin()+2,0.8);
    output(vec);

    vec.erase(vec.begin()+1);
    output(vec);

    return 0;

}

输出结果：

list

list是一个双向列表

函数名 功能 复杂度
size() 返回向量的元素数目 O(1)
push_back(x) 在向量的末尾添加x O(1)
push_front(x) 在向量的开头添加x O(1)
pop_back() 删除向量的最后一个元素 O(1)
pop_front() 删除向量的开头元素 O(1)
begin() 返回指向向量开头的迭代器 O(1)
end() 返回指向向量结尾的迭代器 O(1)
insert(p,x) 在向量中迭代器p指向的位置插入x O(1)
erase(p) 删除向量中迭代器p指向的元素 O(1)
clear() 删除向量中所有元素 O(n) 
#include<iostream>
#include<list>
#include<string>
using namespace std;

int main()
{
    list<char> li;
    li.push_back('b');  //[b]
    li.push_front('a'); //[ab]
    li.push_back('c');  //[abc]
    cout<<li.front();   //a
    cout<<li.back();    //c
    li.pop_front();     //[bc]
    li.push_back('d');  //[bcd]
    cout<<li.front();   //b
    cout<<li.back();    //d
    return 0;

}

运行结果：