目录

栈,队列和链表


栈,队列和链表是最基础的数据结构,它们出现在很多生活场景中,比如说堆起来的集装箱,排队坐过山车,人体蜈蚣(如果不知道就别去搜了,啦啦啦)

简介

栈就像堆起来的集装箱,或者是一堆书,每次加入新的元素只能在旧的之上,每次移出元素只能拿出最新加入的,所以有“后进先出”的原则(后进去的元素先出来)。

常见操作有:

进栈出栈
/stack-queue-linked-list/stack_push.gif/stack-queue-linked-list/stack_pop.gif

数组实现

一般我们用数组的第一个元素array[0]作为栈底,创建一个变量max_index来存储栈的最顶部元素在数组中的下标,也就是数组最后一个栈中元素的下标。

进栈:max_index += 1,然后在该下标插入进栈的元素

出栈:初始化在max_index下标的元素,max_index -= 1

链表实现

单向链表,用head记录栈头,每个元素都有next指向下一个元素,栈顶的next指向NULLsize纪录链表大小(栈的大小)。

进栈:让在栈顶(链表尾部)元素的next指向新的元素,新元素的nextnullsize += 1

出栈:初始化栈顶(链表尾部)元素,移动到上一个元素,设置nextnull, size -= 1

C++ STL - stack

 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
#include<iostream>
#include<stack>
using namespace std;

int main(void) {
    /* 创建一个栈,名为stk,元素类型为int */
	stack <int> stk;

    /* 使一个元素进栈 */
	stk.push(1);	// 1
	stk.push(2);	// 1 2

	/*
	 * cout << stk.push(3) << endl;
	 * 错误!! stk.push(3) 返回void类型
	 */

    /* top() 返回栈最顶部的元素,且不改变栈 */
	cout << stk.top() << endl; // print out 2

	stk.push(1);

    /* 返回栈的大小,有多少元素 */
	cout << stk.size() << endl; // print out 3

    /* 使栈顶部的元素出栈,返回void类型 */
	stk.pop();
	stk.pop();

	cout << stk.top() << endl; // print out 1

    /* 查看栈是否为空,如果为空,返回真(1) */
	cout << stk.empty() << endl;

	return 0;
}

队列

简介

队列就像排队一样,在队尾加入新的元素,在队首出队。所以队列有着“先进先出”的原则。

常见操作有:

入队出队
/stack-queue-linked-list/queue_enqueue.gif/stack-queue-linked-list/queue_dequeue.gif

链表实现

使用单向链表,用head记录队列头,每个元素都有next指向下一个元素,队尾元素的next指向NULLsize纪录队列的长度。

入队:在队尾(链表尾部)插入元素,即旧队尾的next指向新元素,新元素的next指向nullsize += 1

出队:通过next移动到第二个元素,head指向第二个元素,初始化原队首(链表头部),size -= 1

C++ STL - queue

基本用法和栈相同,

信息
队列分别使用frontback来返回队首和队尾元素。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<queue>
using namespace std;

int main() {
	queue<int> q;
	q.push(1); // q: 1
	q.push(2); // q: 1 2

	cout << q.front() << endl; // 1
	cout << q.back() << endl; // 2

	q.push(3); // q: 1 2 3
	cout << q.size() << endl; // 3
	q.pop(); // q: 2 3
	cout << q.front() << endl; // 2
	cout << q.back() << endl; // 3
	cout << q.empty() << endl; // 0

	return 0;
}

### 优先队列 优先队列类似于队列,只不过每个元素都有一个优先级,出队的元素不一定是最先入队的元素,而是当前队列中优先级最高的元素。就像有人有VIP卡的可以走专属通道,有人可以插队一样,对每个元素来说并不公平,叹气。

在C++ STL中,如果把int作为优先队列的类型, 默认情况下如果是整数的优先队列,那整数越小,则优先级越低。如果想整数越大,优先级越低,可以用greater<int>, 完整声明std::priority_queue<int, std::vector<int>, std::greater<int> q_name。如有其它需求,可自定义cmp函数来完成优先级的比较。

警告
优先队列取队首元素不再是用队列的front(),而是用top()

链表

简介

链表像一个个回形针串起来的链子。链表有多种结构:单向链表,双向链表,循环链表等等。主要介绍单向链表,其他类型脑补脑补ok的。

常见操作有:

  • 添加节点
  • 销毁节点
  • 下一节点

/stack-queue-linked-list/link_in.gif

C++ struct 实现

 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
#include<iostream>

struct Node {
	int value;
	Node *next;
};

int main() {
	Node *root;
	Node *cur;

	/* 初始化链表 */
	root = new Node;
	root->value = 1;
	root->next = NULL;
	cur = root;

	/* 在链表尾部加入节点 */
	cur = cur->next;
	cur = new Node;
	cur->value = 2;
	cur->next = NULL; // linked list: 1 2

	/* 在节点中间 */
	Node *second = new Node;
	second->value = 3;
	second->next = cur;
	root->next = second; // linked list: 1 3 2

	/* 知道数据,寻找节点 */
	cur = root;
	while (cur->value != 3) {
		cur = cur->next;
	}
	std::cout << cur->value << std::endl;  // 3

	/* 遍历到链表尾部 */
	while (cur->next != NULL) {
		cur = cur->next;
	}
	std::cout << cur->value << std::endl; // 2

	/* 删除节点 */
	Node *last;
	cur = root;
	if (cur == NULL)
		; // empty list
	if (cur->value == 1) { // if we want to delete the first node
		root = cur->next;
		delete cur;
	} else {
		while (cur->value != 1 && cur->next != NULL) {
			last = cur;
			cur = cur->next;
		}

		if (cur->value == 1) {
			last->next = cur->next;
			delete cur;
		}
	}
}