本文共 4002 字，大约阅读时间需要 13 分钟。

3.1 抽象数据类型

ADT：抽象数据类型

3.2 表ADT

表的简单数组实现

优点

●查找第k个元素花费常数时间 缺点 ●插入和删除花费昂贵 ●数组大小需要提前指定，会浪费大量空间。

链表

结构

 由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和next指针。最后一个单元的next指针指向NULL

struct ListNode {
        int val;     ListNode *next;     ListNode(int x) : val(x), next(NULL) {
   }};

双链表

定义

 数据结构上附加包含指向前一个单元的指针。 优点  寻找前一个节点更容易 缺点  指针更多，插入和删除的开销增加一倍

循环链表

定义

 让最后的单元反过来直指第一个单元

3.3 栈ADT

栈模型

定义

 插入和删除操作只能在栈顶（表的末端）进行，又叫做LIFO（后进先出）表。

栈的单链表实现

定义

 用链表实现栈需要用到一个表头。在表顶端插入来实现Push，删除表顶端元素实现Pop。

缺点

 经常调用new和delete，开销大

typedef int dataType;class Node {
   public:	dataType val;	Node* next;};class stack {
   private:	Node *top;		//表头，这个表头不是哨兵结点（不存值），也要存值，初始化为NULLpublic:	stack() : top(NULL) {
   };	~stack();	bool IsEmpty();	void push(dataType val);	void pop();	dataType topval();};stack::~stack() {
   	Node *ptr = NULL;	while (top != NULL) {
   		ptr = top->next;		delete(top);		top = ptr;	}}bool stack::IsEmpty() {
   	return top == NULL;}void stack::push(dataType val) {
   	Node *ptr = new Node;	ptr->val = val;	ptr->next = top;	//更新top到新插入的节点	top = ptr;}void stack::pop() {
   	if (IsEmpty()) {
   		cout << "栈为空，不能pop" << endl;		return;	}	Node *ptr = top->next;	delete(top);	top = ptr;}dataType stack::topval() {
   	return top->val;}

栈的数组实现

定义

 每个栈有个TopOfStack，对于空栈它是-1。  入栈即将TopOfStack加一，然后将stack[TopOfStack]置为X。出栈即将TopOfStack减一。

#include
   
    #include 
    
     using namespace std;typedef int dataType;class stack {
   private:	vector
     
      *vec;	int TopOfStack;	int capacity;public:	stack(int size = 100);	~stack();	bool IsEmpty();	void push(dataType val);	void pop();	dataType topval();};stack::stack(int size /* = 100 */) {
   	vec = new vector
      
       (size);	TopOfStack = -1;	capacity = size;}stack::~stack() {
   	delete vec;	TopOfStack = -1;	capacity = 0;}bool stack::IsEmpty() {
   	return TopOfStack == -1;}void stack::push(dataType val) {
   	if (TopOfStack + 1 >= capacity) {
   		vec->resize(2 * capacity);		capacity *= 2;	}	(*vec)[++TopOfStack] = val;}void stack::pop() {
   	if (TopOfStack == -1) {
   		cout << "error" << endl;		return;	}	TopOfStack--;}dataType stack::topval() {
   	return (*vec)[TopOfStack];}
      
     
    
   

栈的应用

括号匹配

https://leetcode-cn.com/problems/valid-parentheses/

后缀/逆波兰表达式

 将中缀表达式变为后缀表达式，然后计算出。

函数调用

 首先操作系统为每个线程都分配了一块独立的空间，这块空间被组织成了栈这种数据结构，这玩意是用来存储栈帧，每进入一个函数，就会将该函数的栈帧入栈，但这个函数执行完，返回结果之后，这个函数对应的那个栈帧就出栈了。

3.4 队列ADT

定义

 队列是FIFO，基本操作是入队和出队。

链表实现队列

typedef int datatype;class Node {
   public:	datatype data;	Node *next;	Node(datatype val):data(val),next(NULL){
   }};class Queue {
   private:	Node *front;	Node *rear;	int size;public:	Queue() :front(NULL), rear(NULL),size(0) {
   };	~Queue();	bool IsEmpty();	void Enqueue(datatype val);	datatype Dequeue();};bool Queue::IsEmpty() {
   	return size == 0;}void Queue::Enqueue(datatype val) {
   	Node *temp = new Node(val);	//为空时	if (front == NULL) {
   		front = rear = temp;	}	else {
   		rear->next = temp;	}	rear = temp;	size++;}datatype Queue::Dequeue() {
   	if (front == NULL) {
   		cout << "为空不能出队" << endl;		return -1;	}	Node *temp = front->next;	datatype ret = front->data;	delete(front);	front = temp;	--size;	return ret;}Queue::~Queue() {
   	while (front != NULL) {
   		Node *temp = front;		front = front->next;		delete(temp);	}}

循环数组实现队列

#define Queue_size 10typedef int datatype;class Queue {
   public:	Queue():rear(0), front(0), size(0), capacity(Queue_size){
   }	bool IsEmpty();	void Enqueue(datatype val);	datatype Dequeue();private:	//不能用vector
   
     vec(10)初始化，因为像一个函数定义，返回值是vector
    
     	vector
     
      vec = vector
      
       (Queue_size);	int rear;	int front;	int size;	int capacity;};bool Queue::IsEmpty() {
   	return size == 0;}void Queue::Enqueue(datatype val) {
   	if (size >= capacity) {
   		cout << "已满" << endl;		exit(1);	}	vec[rear] = val;	rear = (rear + 1) % capacity;	size++;	}datatype Queue::Dequeue() {
   	if (size == 0) {
   		cout << "队列无元素" << endl;		exit(1);	}	int ret =  vec[front];	front = (front + 1) % capacity;	size--;	return ret;}
      
     
    
   

队列的应用

阻塞队列