线性结构，顺序表，链表，栈，队列，后缀表达式求值，简单模拟单队列排队
线性结构
表
顺序表
#include<iostream>
#include<list>
#include<vector>
#include<stack>
using namespace std;
int main() {
vector<int> v;
v.push_back(11);//放入11到末尾,括号内就是要放入的元素，发生一次值传递
v.push_back(22);
v.insert(v.begin() + 2, 666);//迭代器是顺序实现，所以可以有++也可以有+2
v.erase(v.begin() + 1);//删除第二个元素
vector<int>::iterator it;
for (it = v.begin(); it != v.end(); it++) {//it=v.end表示表已经结束了
cout << *it << ",";
}
cout << endl;
//v.emplace_back();当拿一个类的对象作为元素加进v里面，会把对象拷贝一遍，产生一次拷贝构造，emplace_back只需要在v向量内部直接去构造
for (int i : v) {
cout << i << ",";
}
cout << endl;
return 0;
}
链表
#include<iostream>
#include<list>
#include<vector>
#include<stack>
using namespace std;
int main() {
list<int> a;
a.push_back(11);
a.push_back(22);
a.insert(a.begin(), 666);//地址不连续，不能a.begin+k
a.remove(11);//remove一个值
list<int>::iterator it;
//在这里迭代器的++是运算符的重载，迭代器的++不是一定会加值，向量的迭代器++是往后一个元素，链表的迭代器++相当于p=p->next
for (it = a.begin(); it != a.end(); it++) {
cout << *it << ",";
}
cout << endl;
}
栈
#include<iostream>
#include<stack>
using namespace std;
int main() {
stack<int> st;
st.push(11);
st.push(22);
//st.pop();//弹栈，不获取值
int x;
x = st.top();
st.top();
cout << x << endl;
st.empty();//C++栈的容量可以根据需求动态地扩充增加
cout << st.size() << endl;
return 0;
}
例：后缀式求值
我们人类习惯于书写“中缀式”，如 3 + 5 * 2 ，其值为13。 (p.s. 为什么人类习惯中缀式呢？是因为中缀式比后缀式好用么？）
而计算机更加习惯“后缀式”（也叫“逆波兰式”，Reverse Polish Notation）。上述中缀式对应的后缀式是： 3 5 2 * +
现在，请对输入的后缀式进行求值。
输入格式:
在一行中输入一个后缀式，运算数和运算符之间用空格分隔，运算数长度不超过6位，运算符仅有+ - * / 四种。
输出格式:
在一行中输出后缀式的值，保留一位小数。
输入样例:
3 5.4 2.2 * +
输出样例:
14.9
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main()
{
double a, b;
string str;
stack<double> num;
while (cin >> str) {
char c = getchar();
if ((str[0] >= '0' && str[0] <= '9') || isdigit(str[0]))
num.push(stod(str));
}
else {
switch (str[0])
{
case '+': a = num.top();
num.pop();
b = num.top();
num.pop();
num.push(a + b);
break;
case '-': a = num.top();
num.pop();
b = num.top();
num.pop();
num.push(b - a);
break;
case '*': a = num.top();
num.pop();
b = num.top();
num.pop();
num.push(b * a);
break;
case '/':a = num.top();
num.pop();
b = num.top();
num.pop();
num.push(b / a);
break;
}
}
if (c == '\n') {
break;
}
}
printf("%.1f\n", num.top());
return 0;
}
链式队列
不使用STL
#include<iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int x) {
data = x;
next = NULL;
}
};
class Queue {
private:
Node* front;
Node* rear;
public:
Queue() {
front = rear = NULL;
}
~Queue(){
Node* temp;
while (front) {
front = front->next;
delete temp;
}
}
bool isEmpty() {
return front == NULL;
}
void enQueue(int x){
Node* temp;
temp = new Node(x);
if (isEmpty()) {
front = rear = temp;
}
else {
rear->next = temp;
rear = temp;
}
}
bool deQueue(int *px) {
if (isEmpty())
return false;
else {
*px = front->data;
Node* temp;
temp = front;
front = front->next;
delete temp;
if (isEmpty())
rear = NULL;
return true;
}
}
};
int main(){
Queue q;
q.enQueue(11);
q.enQueue(22);
q.enQueue(33);
q.enQueue(44);
int x;
x = 0;
q.deQueue(&x);
cout << x << endl;
x = 0;
q.deQueue(&x);
cout << x << endl;
x = 0;
q.deQueue(&x);
cout << x << endl;
x = 0;
q.deQueue(&x);
cout << x << endl;
x = 0;
q.deQueue(&x);
cout << x << endl;
return 0;
}
使用STL
#include<iostream>
#include<queue>
using namespace std;
int main() {
queue<int> q;
q.push(11);
q.push(22);
q.emplace(33);
cout << q.front() << endl;
q.pop();
cout << q.front() <<endl;
q.pop();
cout << q.front() << endl;
}
例：简单模拟单队列排队
用程序简单模拟一个单队列多窗口的排队模式：
设某银行有一个固定能容纳N个顾客的等候区，顾客想进银行，若等候区有空则可进，否则被拒绝进入。
每当银行柜员叫号时，等候区中最先进入的顾客离开等候区前往柜台办理业务，若叫号时等候区无人，则此次叫号作废。
输入格式:
第一行输入一个不大于20的正整数N，表示银行等候区能容纳的人数，
接下来用若干行表示依时间顺序先后发生的“顾客想进银行”或“叫号”事件，格式分别是：
顾客想进银行，用 In 表示，其中是顾客编号，为不大于100000的正整数；
叫号，用Calling表示。
最后一行是一个#符号，表示输入结束。
注意：
题目输入保证每个顾客的编号是独一无二的，即：不会出现想进银行的顾客与已经在等候区的顾客编号相同的情况。
保证后一个事件一定在前一个事件完成之后才发生，即：不需要考虑事件之间的“同步”问题。
输出格式:
对于输入的每个事件，按同样顺序在一行内输出事件的结果，格式分别是：
顾客想进银行，若顾客进入，则输出 joined. Total: 其中是该顾客的编号，是顾客进入后，等候区的人数
顾客想进银行，若因等候区满而被拒绝，则输出 rejected. 其中是该顾客的编号
叫号，若有顾客前往柜台，则输出 called. Total: 其中是该顾客的编号，是顾客去柜台后，等候区的人数
叫号，等候区无人，则输出 No one!
输入样例:
3
In 101
In 102
In 103
In 104
Calling
In 105
Calling
Calling
Calling
Calling
输出样例:
101 joined. Total:1
102 joined. Total:2
103 joined. Total:3
104 rejected.
101 called. Total:2
105 joined. Total:3
102 called. Total:2
103 called. Total:1
105 called. Total:0
No one!
使用C语言
#include<stdio.h>
#include<stdlib.h>
struct Queue {
int* data;
int capacity;
int front;
int rear;
int size;
};
void init(struct Queue* pq, int capacity) {
pq->capacity = capacity;
pq->data = (int*)malloc(sizeof(int) * (capacity + 1));
pq->front = pq->rear = pq->size = 0;
}
int isFull(const struct Queue* pq) {
if ((pq->rear + 1) % (pq->capacity + 1) == pq->front)
return 1;
else
return 0;
}
int isEmpty(const struct Queue* pq) {
return pq->front == pq->rear;
}
int enQueue(struct Queue* pq, int x) {
if (isFull(pq))
return 0;
else {
pq->data[pq->rear] = x;
pq->rear = (pq->rear + 1) % (pq->capacity + 1);
pq->size++;
return 1;
}
}
int deQueue(struct Queue* pq, int* px) {
if (isEmpty(pq))
return 0;
else {
*px = pq->data[pq->front];
pq->front = (pq->front + 1) % (pq->capacity + 1);
pq->size--;
return 1;
}
}
int main() {
int N;
scanf_s("%d", &N);
struct Queue q;
init(&q, N);
char op[20];
int id;
scanf_s("%s", op);
while (op[0] != '#') {
if (op[0] == 'I') {
scanf_s("%d", &id);
if (isFull(&q)) {
printf_s("%d rejected.\n", id);
}
else {
enQueue(&q, id);
printf_s("%d joined. Total:%d\n", id, q.size);
}
}
else {
if (isEmpty(&q)) {
printf_s("No one!\n");
}
else {
deQueue(&q, &id);
printf_s("%d called. Total:%d\n", id, q.size);
}
}
}
return 0;
}
使用C++语言
#include<iostream>
#include<queue>
using namespace std;
int main() {
int N;
cin >> N;
queue<string> q;
string op, id;
cin >> op;
while (op != "#") {//C++可以这样比较string
if (op == "In") {
cin >> id;
if (q.size() == N)
cout << id << " rejected." << endl;
else {
q.push(id);
cout << id << " joined. Total:" << q.size() << endl;
}
}
else {
if (q.empty()) {
cout << "No one!" << endl;
}
else {
id = q.front();
q.pop();
cout << id << " called. Total:" << q.size() << endl;
}
}
cin >> op;
}
return 0;
}
上一篇： （译）优化ORC和Parquet文件，提升大SQL读取性能
下一篇： 数据结构(二)线性结构之队列