3. 栈和队列

布满荆棘的人生 2023-01-20 15:58 186阅读 0赞

## 1. 栈（FILO） ##

### 1. 基本概念 ###

*  仅允许在表的一端删除或插入
 *  当n个元素以某种顺序进栈，并可在任意时刻出栈，元素排列数目 N = 1 n + 1 C 2 n n N = \\frac\{1\}\{n+1\} C^n\_\{2n\} N=n\+11C2nn

### 2. 存储结构 ###

*  **顺序存储**：一组地址链路的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（int型变量）
 *  **链式存储**：单链表（操作均在表头进行）

### 3. 结构体定义 ###

#### 1. 顺序栈定义 ####

#define maxSize 20;
    typedef struct
    { 
    	ElemType data[maxSize];
    	int top;
    }SqStack;

#### 2. 链栈结点定义 ####

typedef struct LNode
    { 
    	ElemType data;
    	struct LNode *next;
    }LNode;

### 4. 顺序栈和链栈 ###

#### 1. 顺序栈 ####

##### 1. 四个状态 #####

*  **栈空状态**：st.top == -1;
 *  **栈满状态**：st.top == maxSize -1;（maxSzie为栈中最大元素的个数）
 *  **非法状态**
    
     *  **上溢**：栈满继续入栈
     *  **下溢**：栈空继续出栈

##### 2. 两个操作 #####

*  **元素x进栈**
    
        st.data[++st.top] = x;		//先移动指针，再入栈
 *  **元素x出栈**
    
        x = st.data[st.top--];		//先出栈，再移动指针

##### 3. 基本操作实现 #####

*  **理论**
    
     *  **初始化**
    
        void initStack(SqStack &st)
        { 
        	st.top = -1;
        }
    
     *  **判断栈空**
    
        int isEmpty(SqStack st)
        { 
        	if(st.top == -1)
        		return 1;
        	else
        		return 0;
        }
    
     *  **进栈**
    
        int push(SqStack &st, int x)
        { 
        	if(st.top == maxSize-1)
        		return 0;
        	st.data[++st.top] = x;
        	return 1;
        }
    
     *  **出栈**
    
        int pop(SqStack &st, int &x)
        { 
        	if(st.top == -1)
        		return 0;
        	x = st.data[st.top--];
        	return 1;
        }
 *  **考题中实用**
    
     *  **初始化**
    
        int stack[maxSize];
        int top -1;
    
     *  **进栈**
    
        stack[++top] = x;
    
     *  **出栈**
    
        x = stack[top--];

##### 4. 基本应用 #####

> **1. 将一个非负的十进制整数N转换成一个二进制数**

int BaseTrans(int N)
    { 
    	int i, result = 0;
    	int stack[maxSize], top = -1;		//定义并初始化栈，其中maxSize是已定义的常量，其大小足够处理本题数据
    	while(N != 0)
    	{ 
    		i = N%2;
    		N = N/2;
    		stack[++top] = i;
    	}
    	while(top != -1)
    	{ 
    		i = stack[top];
    		--top;
    		result = result*2 + i;
    	}
    	return result;
    }

> **2. 检查一个程序中的花括号、方括号和圆括号是否匹配，若全部配对，则返回1，否则返回0.对于程序中出现的一对单引号或双引号内的字符不进行括号配对检查。39为单引号的ASCII值，34为双引号的ASCII值，单引号和双引号成对出现。假设stack是已经定义的顺序栈结构体。可以直接调用的元素进栈/出栈、取栈顶元素、判断栈空的函数定义如下**

*  void push(stack &s, char ch);
 *  void pop(stack &s, char &ch);
 *  void getTop(stack s, char &ch);
 *  int isEmpty(stack s); //若栈s空，则返回-1，否则返回0
    
        int bracketsCheck(char f[])
        { 
        	stack S; char ch;				//定义一个栈
        	char *p = f;
        	while(*p != '\0')
        	{ 
        		if(*p == 39)
        		{ 
        			++p;					//跳过第一个单引号
        			while(*p != 39)			//39为单引号的ASCII值
        				++p;
        			++p;					//跳过最后一个单引号
        		}
        		else if(*p == 34)
        		{ 
        			++p;					//跳过第一个双引号
        			while(*p != 34)			//34为单引号的ASCII值
        				++p;
        			++p;					//跳过最后一个双引号
        		}
        		else
        		{ 
        			switch(*p)
        			{ 
        				case '{':
        				case '[':
        				case '(':
        					push(S, *p);	//出现左括号：“{”、“[”、“(”进栈
        					break;
        				case '}':
        					getTop(S, ch);
        					if(ch == '{')
        						pop(S, ch);
        					else
        						return 0;
        					break;
        				case ']':
        					getTop(S, ch);
        					if(ch == '[')
        						pop(S, ch);
        					else
        						return 0;
        					break;
        				case ')':
        					getTop(S, ch);
        					if(ch == '(')
        						pop(S, ch);
        					else
        						return 0;
        			}
        			++p;
        		}
        	}
        	if(isEmpty(S))
        		reutrn 1;
        	else
        		return 0;
        }

#### 2. 链栈 ####

##### 1. 两个状态 #####

*  **栈空状态**：lst -> next == NULL;
 *  **栈满状态**：不存在栈满的情况

##### 2. 两个操作 #####

*  **元素（由指针p所指）进栈**
    
        p->next = lst->next;		//头插操作
        lst->next = p;
 *  **出栈（出栈元素保存在x中）**
    
        p = lst->next;				//单链表的删除操作
        x = p->data;
        lst -> next = p->next;
        free(p);

##### 3. 基本操作实现 #####

*  **初始化**
    
        void initStack(LNode *&lst)
        { 
        	lst = (LNode *)malloc(sizeof(LNode));
        	lst->next = NULL;
        }
 *  **判断栈空**
    
        int isEmpty(LNode *lst)
        { 
        	if(lst->next == NULL)
        		return 1;
        	else
        		return 0;
        }
 *  **进栈**
    
        void push(LNode *lst, int x)
        { 
        	LNode *p;
        	p = (LNode *)malloc(sizeof(LNode));
        	p->next = NULL;
        	p->data = x;				//头插法
        	p->next = lst->next;
        	lst->next = p;
        }
 *  **出栈**
    
        int pop(LNode *lst, int &x)
        { 
        	LNode *p;
        	if(lst->next == NULL)
        		return 0;
        	p = lst->next;				//单链表的删除操作
        	x = p->data;
        	lst->next = p->next;
        	free(p);
        	return 1;
        }

#### 3. 共享栈 ####

*  **定义**
    
     *  利用栈底位置相对不变的特性，让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
 *  **两个状态**
    
     *  **栈满**：top0 + 1 == top1
     *  **栈空**：top0==-1; top1== maxSize;

### 5. 栈的应用 ###

#### 1. 栈在括号匹配中的应用 ####

*  **算法思想**：依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素，算法结束后扫描栈是否为空  
    ![流程图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70]
 *  **算法实现**
    
        #define MaxSize 20
        typedef struct{ 
        	char data[MaxSize];
        	int top;
        }
        
        bool bracketCheck(char str[], int length)
        { 
        	SqStack S;
        	S.top = -1;
        	for(int i = 0; i < length; i++)
        	{ 
        		if(str[i] == '(' || str[i] == '[' || str[i] == '{')
        		{ 
        			S.data[++S.top] = str[i];
        		}
        		else
        		{ 
        			if(S.top == -1)
        				return false;
        			char topElem;
        			topElem = S.data[S.top--];
        			if(str[i] == ')' && topElem != '(')
        				return false;
        			if(str[i] == ']' && topElem !='[')
        				return false;
        			if(str[i] == '}' && topElem !='{')
        				return false;
        		}
        	}
        	return S.top == -1 ? true : false;
        }

#### 2. 栈在表达式求值中的应用 ####

##### 1. 中缀表达式转后缀表达式（机算） #####

*  **算法思想**
    
     *  遇到操作数。直接加入后缀表达式
     *  遇到界限符。遇到“（”直接入栈 ；遇到 “）”则依次弹出栈内运算符并加入后缀表达式，直到弹出“（”为止。注意：“（”不加入后缀表达式
     *  遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若遇到“（”或栈空则停止。之后再把当前运算符入栈
     *  按上述方法处理完所有字符后，将栈中剩余运算符依次弹出

##### 2. 中缀表达式的计算 #####

*  **算法思想**
    
     *  初始化两个栈，操作数栈和运算符栈
     *  若扫描到操作数，压入操作数栈
     *  若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再押回操作数栈）

##### 3. 后缀表达式的计算 #####

*  **算法思想**
    
     *  遇到操作数就输出，遇到运算符就计算结果，并将结果存入栈中
 *  **算法实现**
    
        #define maxSize 50;
        typedef struct
        { 
        	int data[maxSize];
        	int top;
        }Stack;
        
        int Op(int a, char op, int b)
        { 
        	if(op == '+')
        		return a+b;
        	if(op == '-')
        		return a-b;
        	if(op == '*')
        		return a*b;
        	if(op == '/')
        	{ 
        		if(b == 0)
        		{ 
        			cout<<"ERROR"<<endl;
        			return 0;
        		}
        		else
        			return a/b;
        	}
        }
        
        int com(char exp[])
        { 
        	int i, a, b, c;
        	Stack stack; stack.top = -1;
        	char op;
        	for(i = 0; exp[i] != '\0'; ++i)
        	{ 
        		if(exp[i] >= '0' && exp[i] <= '9')
        			stack[++top] = exp[i] - '0';
        		else
        		{ 
        			op = exp[i];
        			b = stack[top--];
        			a = stack[top--];
        			c = Op(a, op, b);
        			stack[++top] = c;
        		}
        	}
        }

#### 3. 栈在递归中的应用 ####

*  **函数调用时，需要用一个栈存储**
    
     *  调用返回地址
     *  实参
     *  局部变量

1.  递归算法求阶乘
    
        int factorial(int n)
        { 
        	if(n == 0 || n == 1)
        		return 1;
        	else
        		reutrn n * factorial(n-1);
        }
2.  递归算法求斐波那契数列
    
        int Fib(int n)
        { 
        	if(n == 0)
        		return 0;
        	else if(n == 1)
        		return 1;
        	else
        		return Fib(n-1) + Fib(n-2);
        }

### 6. 相关算法题 ###

> **1. I和O分别表示进栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，可以操作的序列称为合法序列。判定给定的操作序列是否合法，若合法，返回true，否则返回false**

*  **算法思想**：依次逐一扫描入栈出栈序列，每扫描至任一位置均需检查出栈次数是否小于入栈次数，若大于则为非法序列。扫描结束后，再判断入栈和出栈次数是否相等，若不相等则不合题意，为非法序列
 *  **算法实现**
    
        bool Judge(char A[])
        { 
        	int i=j=0;
        	while(A[i] != '\0')
        	{ 
        		switch(A[i])
        		{ 
        			case 'I': ++j; break;
        			case 'O': 
        				--j;
        				if(j < 0)
        					return false;
        		}
        		++i;
        	}
        	if(j != 0)
        		return false;
        	else
        		return true;
        }

> **2. 设单链表的表头指针为L，结点结构由data和next两个域构成，其中data域为字符型。试设计算法判断该链表的全部n个字符是否中心对称。例如xyx、xyyx都是中心对称**

*  **算法思想**：让链表的前一半元素依次进栈，在处理链表的后一般元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两个元素比较，若相等，则将链表中的下一个元素与栈中再弹出的元素比较，直至链表到尾，这时若栈是空栈，则中心对称，否则为非中心对称。
 *  **算法实现**
    
        int central(LNode *L,int n)
        { 
        	int i;
        	char s[n/2]				//s为字符栈
        	LNode *p = L->next;		//p是链表的工作指针，指向待处理的当前元素
        	for(i = 0; i < n/2; ++i)
        	{ 
        		s[i] = p->data;
        		p = p->next;
        	}
        	--i;					//恢复最后的i值
        	if(n%2 == 1)			//若n是奇数，后移过中心结点
        		p = p->next;
        	while(p != NULL && s[i] == p->data)
        	{ 
        		i--;				//i充当栈顶指针
        		p = p->next;
        	}
        	if(i == -1)
        		return 1;
        	else 
        		return 0;
        }

> **3. 设有两个栈s1、s2都采用顺序栈方式，并共享一个存储区\[0, 1, … , maxSize-1\]，元素类型为整型，试设计一个共享栈，并写出有关入栈和出栈的操作算法**

#define maxSize 100
    typedef struct
    { 
    	int data[maxSize];
    	int top[2];
    }Stack;
    //入栈操作
    int push(Stack &st, int stNo, int x)
    { 
    	if(i < 0 || i > 1)
    		return -1;					//栈编号输入有误，返回-1
    	if(st.top[1] - st.top[0] == 1)
    		return 0;					//栈满返回0
    	switch(i)
    	{ 
    		case 0:
    			st.data[++st.top[0]} = x;
    			return 1;
    			break;
    		case 1:
    			st.data[--st.top[1]] = x;
    			return 1;
    	}
    } 
    //出栈操作
    int pop(Stack &st, int stNo, int &x)
    { 
    	if(i < 0 || i > 1)
    		return -1;					//栈编号输入有误，返回-1
    	if(st.top[0] == -1 && st.top[1] == maxSize)
    		return 0;					//栈空返回0
    	switch(i)
    	{ 
    		case 0:
    			if(st.top[0] == -1)
    				return 0;					//栈空返回0
    			x = st.data[st.top[0]--];
    			return 1;
    			break;
    		case 1:
    			if(st.top[0] == -1 && st.top[1] == maxSize)
    				return 0;					//栈空返回0
    			x = st.data[st.top[1]++];
    			return 1;
    	}
    }

> **4. 设计一个栈，使它可以再O(1)的时间复杂度实现Push、Pop和min操作。min操作是指得到栈中最小的元素**

*  **结构体定义**
    
        #define maxSize 100;
        typedef struct
        { 
        	ElemType data[maxSize];
        	ElemType min[maxSize];
        	int top;
        }Stack;
 *  **入栈**
    
        void Push(Stack &s, ElemType x)
        { 
        	++S.top;
        	S.data[S.top] = x;
        	if(S.top == 0)
        		S.min[S.top] = x;
        	else
        	{ 
        		if(x < S.min[S.top--]
        			S.min[S.top] = x;
        		else
        			S.min[S.top] = S.min[S.top-1];
        	}
        }
 *  **出栈**
    
        void Pop(ElemType &x)
        { 
        	if(S.top == -1)
        		return;
        	S.min[S.top] = 0;
        	x = S.data[S.top--];
        }
 *  **取最小值**
    
        void Min(ElemType &x)
        { 
        	if(S.top == -1)
        		return;
        	x = S.min[S.top];
        }

> **5. 火车调度站的入口处有n节硬座和软座车厢（分别用H和S表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作序列，以使所有的软座车厢都被调整到硬座车厢之前**

*  **算法实现**
    
        void Train_Arrange(char *train)
        { 
        	char *p = train, *q = train, c;
        	stack s;
        	InitStack(s);
        	while(*p)
        	{ 
        		if(*p == 'H')
        			Push(s, *p);
        		else
        			*(q++）= *p;
        		p++;
        	}
        	while(!StackEmpty(S))
        	{ 
        		Pop(s, c);
        		*(q++) = c;
        	}
        }

> **6. 利用一个栈实现一下递归函数的非递归计算**  
>  P n ( x ) = \{ 1 ， n = 0 2 x ， n = 1 2 x P n − 1 − 2 ( n − 1 ) P n − 2 ( x ) ， n > 1 P\_n(x)=\\left\\\{ \\begin\{aligned\} 1， n=0\\\\ 2x， n=1 \\\\ 2xP\_\{n-1\}-2(n-1)P\_\{n-2\}(x)， n>1 \\end\{aligned\} \\right. Pn(x)=⎩⎪⎨⎪⎧1，n=02x，n=12xPn−1−2(n−1)Pn−2(x)，n>1

*  **算法思想**：设置一个栈用于保存n和对应的 P n ( x ) P\_n(x) Pn(x)值，栈中相邻元素的 P n ( x ) P\_n(x) Pn(x)有题中关系。然后边出栈边计算 P n ( x ) P\_n(x) Pn(x)，栈空后该值就计算出来了
 *  **算法实现**
    
        double p(int n, double x)
        { 
        	struct stack
        	{ 
        		int no;						//保存n
        		double val;					//保存Pn(x)值
        	}st[maxSize];
        	int top = -1, i;
        	double fv1 = 1, fv2 = 2*x;		//n=0。n=1时的初值
        	for(i = n; i >= 2; i--)
        	{ 
        		++top;
        		st[top].no = i;
        	}
        	while(top >= 0}
        	{ 
        		st[top].val = 2*x*fv2-2*(st[top].no-1)*fv1; //入栈
        		fv1 = fv2;
        		fv2 = st[top].val;
        		top--;										//出栈
        	}
        	if(n == 0)
        		return fv1;
        	return fv2;
        }

## 2. 队列（FIFO） ##

### 1. 基本概念 ###

*  仅允许在表的一段插入，另一端进行删除

### 2. 存储结构 ###

*  顺序存储：分配一块连续的存储单元存放队列中的元素，并附设两个指针
 *  链式存储：同时带有队头指针和队尾指针的单链表，头指针只想队头结点，尾指针指向队尾结点

### 3. 结构体定义 ###

*  **顺序队列定义**
    
        #define maxSize 20;
        typedef struct
        { 
        	ElemType data[maxSize];
        	int front;
        	int rear;
        }SqQueue;
 *  **链队定义**
    
     *  **队结点类型定义**
    
        typedef struct QNode
        { 
        	ElemType data;
        	struct QNode *next;
        }QNode;
    
     *  **链队类型定义**
    
        typedef struct
        { 
        	QNode *front;
        	QNode *rear;
        }LiQueue;

### 4. 顺序队和链队 ###

#### 1. 循环队列（必须损失一个存储空间） ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 1]

##### 1. 两个状态 #####

*  **队空状态**：qu.rear == qu.front;
 *  **队满状态**：(qu.rear+1)%maxSize == qu.front;

##### 2. 两个操作 #####

*  **元素x进队**
    
        qu.rear == (qu.rear+1)%maxSize;
        qu.data[qu.rear] = x;
 *  **元素x出队**
    
        qu.front = (qu.front+1)%maxSize;
        x = qu.data[qu.front];

##### 3. 基本操作实现（正常情况） #####

*  **初始化**
    
        void intitQueue(SqQueue &qu)
        { 
        	qu.front = qu.rear =0;
        }
 *  **判断队空**
    
        int isQueueEmpty(SqQueue qu)
        { 
        	if(qu.front == qu.rear)
        		return 1;
        	else
        		return 0;
        }
 *  **进队**
    
        int enQueue(SqQueue &qu, ElemType x)
        { 
        	if((qu.rear+1)%maxSize == qu.front)	//队满
        		return 0;
        	qu.rear = (qu.rear+1)%maxSize;
        	qu.data[qu.rear] = x;
        	return 1;
        }
 *  **出队**
    
        int deQueue(SqQueue &qu, ElemType &x)
        { 
        	if(qu.front == qu.rear)				//队空
        		return 0;
        	qu.front = (qu.front+1)%maxSize;
        	x = qu.data[qu.front];
        	return 1;
        }

##### 4. 基本应用 #####

> **1. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队和出队算法**

*  **入队**
    
        void enQueue(LNode *&rear, int x)
        { 
        	LNode *s = (LNode *)malloc(sizeof(LNode));
        	s->data = x;
        	s->next = rear->next;
        	rear = s;
        }
 *  **出队**
    
        void deQueue(LNode *&rear, int &x)
        { 
        	LNode *s;
        	if(rear->next == rear)
        		return 0;
        	else
        	{ 
        		s = rear->next->next;
        		rear->next->next = s->next;
        		x = s->data;
        		if(s == rear)
        			rear = rear->next;
        		free(s);
        		return 1;
        	}
        }

> **2. 如果允许在循环队列的两端都可以进行插入和删除操作。写出结构体定义及相关操作算法**

*  **结构体定义**
    
        typedef struct
        { 
        	int data[maxSize];
        	int front, rear;
        }CysQueue;
 *  **入队**
    
        int enQueue(CycQueue &Q, int x)
        { 
        	if(Q.rear == (Q.front-1+maxSize)%maxSize)
        		return 0;
        	else
        	{ 
        		Q.data[Q.front] = x;
        		Q.front = (Q.front-1+maxSize)%maxSize;	//修改队头指针
        		return 1;
        	}
        }
 *  **出队**
    
        int deQueue(CycQueue &Q, int &x)
        { 
        	if(Q.front == Q.rear)
        		return 0;
        	else
        	{ 
        		x = Q.data[Q.rear];
        		Q.rear = (Q.rear-1+maxSize)%maxSize;	//修改队尾指针
        		return 1;
        	}
        }

> **3. 设计一个循环队列，用front和rear分别作为队头和队尾指针，另外用一个标志tag表示队列是空还是非空，约定当tag=0时队空，当tag=1时队不空，这样就可以使用front==rear作为队满的条件。设计相关操作算法**

*  **结构体定义**
    
        typedef struct
        { 
        	int data[maxSize];
        	int front, rear;
        	int tag;
        }Queue;
 *  **初始化**
    
        void initQueue(Queue &qu)
        { 
        	qu.front = qu.rear = 0;
        	qu.tag = 0;
        }
 *  **判断队是否为空**
    
        void isQueueEmpty(Queue &qu)
        { 
        	if(qu.front == qu.rear && qu.tag == 0)
        		return 1;
        	else
        		return 0;
        }
 *  **判断是否队满**
    
        void QueueFull(Queue &qu)
        { 
        	if(qu.front == qu.rear && qu.tag == 1)
        		return 1;
        	else
        		return 0;
        }
 *  **入队**
    
        int enQueue(Queue &qu, int x)
        { 
        	if(QueueFull(qu) == 1)
        		return 0;
        	else
        	{ 
        		qu.rear = (qu.rear+1)%maxSize;
        		qu.data[qu.rear] = x;
        		qu.tag = 1;						//只要进队就把tag置为1
        		return 1;
        	}
        }
 *  **出队**
    
        iint deQueue(Queue &qu, int &x)
        { 
        	if(isQueueEmpty(qu) == 1)
        		return 0;
        	else
        	{ 
        		qu.front = (qu.front+1)%maxSize;
        		x = qu.data[qu.front];
        		qu.tag = 0;						//只要进队就把tag置为0
        		return 1;
        	}
        }

> **4. 某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类，上渡船有如下规定：同类车先到先上车；客车优于货车先上船，且没上4辆客车，才允许上一辆货车；若等待客车不足4辆，则以货车代替；若无货车等待，允许客车都上船。试设计一个算法模拟渡口管理**

*  **算法思想**：假设数组q的最大下标为10，恰好是每次载渡的最大量。假设客车的队列为q1，货车的队列为q2。若q1充足，则每取4个q1元素后再取一个q2元素，直到q的长度为10。若q1不充足，则直接用q2补齐。且最多只需循环两轮。
 *  **算法实现**
    
        Queue q;								//过江渡船载渡队列
        Queue q1;								//客车队列
        Queue q2;								//货车队列
        void manager()
        { 
        	int i = 0, j = 0;					//j表示渡船上的总车辆数
        	while(j < 10)
        	{ 
        		if(!QueueEmpty(q1) && i < 4)	//客车队列不空，且未上足4辆
        		{ 
        			DeQueue(q1, x);				//从客车队列出队
        			EnQueue(q, x);				//客车上渡船
        			++i;						//客车数加1
        			++j;						//渡船上的总车辆数加1
        		}
        		else if(i == 4 && !QueueEmpty(q2))//客车已上足4辆
        		{ 
        			DeQueue(q2, x);				//从货车队列出队
        			EnQueue(q, x);				//货车上渡船
        			++j;						//渡船上的总车辆数加1
        			i = 0;						//每上一辆货车，i重新计数
        		}
        		else							//其他情况（客车队列空或货车队列空）
        		{ 
        			while(j < 10 && i < 4 && !QueueEmpty(q2))//客车对裂空
        			{ 
        				DeQueue(q2, x);			//从货车队列出队
        				EnQueue(q, x);			//货车上渡船
        				++i;					//i计数，当i>4时，退出本循环
        				++j;					//渡船上的总车辆数加1
        			}
        			i = 0;
        		}
        		if(QueueEmpty(q1) && QueueEmpty(q2))
        			j = 11;						//货车和客车加起来不足10辆
        	}
        }

#### 2. 链队 ####

![在这里插入图片描述][20210514083232727.png]

##### 1. 两个状态 #####

*  **队空状态**：lqu->rear = NULL 或 lqu->front = NULL
 *  **队满状态**：不存在队满的情况

##### 2. 两个操作 #####

*  **进队（p指向进队元素）**
    
        lqu->rear->next = p;
        lqu->rear = p;
 *  **出队（x存储出队元素）**
    
        p = lqu->front;
        lqu->front = p->next;
        x = p->data;
        free(p);

##### 3. 基本操作实现 #####

*  **初始化**
    
        void intitQueue(LiQueue *&lqu)
        { 
        	lqu = (LiQueue *)malloc(sizeof(LiQueue));		//创建头结点
        	lqu->front = lqu-rear=NULL;
        }
 *  **判断队空**
    
        int isQueueEmpty(LiQueue *lqu)
        { 
        	if(lqu->rear == NULL || lqu->front == NULL)
        		return 1;
        	else
        		return 0;
        }
 *  **入队**
    
        void enQueue(LiQueue *lqu, ElemType x)
        { 
        	QNode *p;
        	p = (QNode *)malloc(sizeof(QNode));
        	p->data = x;
        	p->next = NULL;
        	if(lqu->rear == NULL)				//队空
        		lqu->front = lqu->rear=p;
        	else
        	{ 
        		lqu->rear->next = p;
        		lqu->rear = p;
        	}
        }
 *  **出队**
    
        int deQueue(LiQueue *lqu, ElemType &x)
        { 
        	QNode *p;
        	if(lqu->rear == NULL)
        		return 0;
        	else
        		p = lqu->front;
        	if(lqu->front == lqu->rear)				//只有一个数据结点
        		lqu->front = lqu->rear = NULL;
        	else
        		lqu->front = lqu->front->next;
        }

#### 3. 双端队列 ####

*  **定义**
    
     *  两端都可以进行入队和出队操作的队列
 *  **分类**
    
     *  输入受限的双端队列：允许从两端删除、从一端插入的队列
     *  输出受限的双端队列：允许从两端插入、从一段删除的队列
 *  **考点：判断输出序列的合法性**
    
     *  在栈中合法的输出序列，在双端序列中必定合法
     *  前端进的元素排列在队列中后端进的元素前面，后端进的元素排列在队列中前端进的元素后面

## 3. 特殊矩阵的压缩存储 ##

#### 1. 压缩存储 ####

*  为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间

#### 2. 对称矩阵 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 2]

#### 3. 三角矩阵 ####

*  **下三角**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 3]
 *  **上三角**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 4]

#### 4. 三对角矩阵 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 5]

#### 5. 稀疏矩阵 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70]: /images/20221021/7d7f9812768f4dd4bdc71026dfe8e114.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 1]: /images/20221021/96567cfa229e47ff993edc86eaebc770.png
[20210514083232727.png]: /images/20221021/aac9b5d41cb346b5ac924c386a568b96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 2]: /images/20221021/58169a6dbfe24aee98ae8c2e18d15b7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 3]: /images/20221021/711ce2c2127343508b88dc021872aa9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 4]: /images/20221021/a5edf9e02a2c4967947e9335340d0abe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 5]: /images/20221021/ad21369f7fba4e018dc6ec6c771e3269.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 6]: /images/20221021/4ed251a94f30484293d0afc040a80ac5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY5NDk2_size_16_color_FFFFFF_t_70 7]: /images/20221021/5974979648b74a10917ce0f73dc0d78f.png