栈和队列

队列

​ head tail

1	2	3	4	5

1.legth=9 head=0 tail=4 data_type=xxx

2.遵循FIFO（先入先出）

队列的两个操作

出队：头指针向后移动一位

入队：尾部指针向后移动一位

假溢出

队空间满后插入的值假溢出

循环队列

队空间满后尾指针+1指向头指针

栈4

遵循后入先出

出栈：栈顶指针下移一位

入栈：栈顶指针上移一位

栈的本质

例题：

推导过程：

1.问题简化成只有一种括号应该怎么做？

2.考虑用栈

括号匹配的性质：

1.在任意一个位置上，左括号数量>=右括号数量

2.在最后一个位置上，左括号数量==右括号数量

3.程序中只需要记录左括号数量和右括号数量即可

解法一：

bool isValid(char *s){
	inte32_t lnum=0,rnum=0;
	int32_t len=strlen(s);
	for(int32_t i=0;i<length;i++){
    	switch(s[i]){
			case'(':++lnum;break;
            case')':++rnum;break;
            default:return false;
        }
      if(lnum>=rnum)continue;
      return false;
    }
    return lnum==rnum;

优化版

左括号+1右括号-1，类似于栈顶指针的操作； 

总结：

1.一对（）可以等价为一个完整的事件

2.（（））可以看作事件与事件之间的完全包含关系

3.由括号的等价变换得到了一个新的数据结构

栈可以解决具有完全包含关系的问题

（子问题之间没有包含关系）