栈和队列及习题讲解1

从内存先拿到寄存器运算完再放回内存①int ret1 i;前置自增mov eax,dword ptr [i] ; 把i从内存读到eax add eax,1 ; eax eax 1 【先自增】 mov dword ptr [i],eax ; 把1后的值写回i内存 mov ecx,dword ptr [i] ; 读取已经更新完的i mov dword ptr [ret1],ecx; 把**自增之后**的值赋给ret1逻辑先 再赋值ret1 拿到的是 i 增加完成后的新值。②int ret2 i;后置自增mov eax,dword ptr [i] ; 读取i原始旧值 mov dword ptr [ret2],eax; 【先把旧值赋值给ret2】 mov ecx,dword ptr [i] ; 再读i旧值 add ecx,1 ; ecx ecx1 mov dword ptr [i],ecx ; 写回i完成i自增要实现的接口size永远代表有效元素数量全世界教材统一。空表size 0最后一个有效元素下标size‑1新元素插在表尾data[size] x;栈的 top 为什么会有两套栈的top存的是数组下标不是计数下标本身就有两种理解所以诞生两套流派top0top 是下一个可存放位置的下标等价于顺序表的 sizetop-1top 是当前栈顶元素的下标入栈需要拿掉栈顶元素才能访问下一个括号的匹配最后也排除了左括号多的情况出栈可以和入栈顺序不同但出队和入队顺序一定相同/ 入队需要二级指针 QNode**原先的void QueuePush(QNode** pphead, QNode** pptail, QDataType x){// 创建新节点QNode* newnode (QNode*)malloc(sizeof(QNode));//...if(*pphead NULL){*pphead newnode; // 修改外部phead本身*pptail newnode; // 修改外部ptail本身}else{(*pptail)-next newnode;*pptail newnode;}}// 调用的时候要传地址QueuePush(phead, ptail, 10);成为成员之后只需要传结构体的地址void QueuePush(Queue* pq, QDataType x){QNode* newnode (QNode*)malloc(sizeof(QNode));//...if(pq-phead NULL){pq-phead newnode;pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}}//调用只传结构体地址一级指针Queue q;QueueInit(q);QueuePush(q,10);防止只有一个节点free以后ptail是野指针的问题一定要防止野指针的出现就是phead和ptail因为后面的接口要访问他们的成员用两个队列实现栈往空的里面插入底层结构1. 入栈push—— O(1)cvoid myStackPush(MyStack* obj, int x) { if(!QueueEmpty(obj-q1)) { QueuePush((obj-q1), x); // q1 非空入 q1 } else { QueuePush((obj-q2), x); // q1 空入 q2不管 q2 是否为空 } }✅ 两个队列都为空时默认入 q2因为 q1 空走 else2. 出栈pop—— O(n)核心轮转你的假设法非常经典c// 先假设 q1 是空q2 是非空 Queue* empty (obj-q1); Queue* nonEmpty (obj-q2); // 检查假设是否正确如果 q1 非空说明假设反了 if(!QueueEmpty((obj-q1))) { nonEmpty (obj-q1); empty (obj-q2); }然后轮转c// 把 nonEmpty 中除了最后一个元素外全部搬到 empty while(QueueSize(nonEmpty) 1) { QueuePush(empty, QueueFront(nonEmpty)); QueuePop(nonEmpty); } // 此时 nonEmpty 只剩一个元素就是栈顶弹出它 int top QueueFront(nonEmpty); QueuePop(nonEmpty); return top;3. 取栈顶top—— 利用队列的队尾接口cint myStackTop(MyStack* obj) { if(!QueueEmpty((obj-q1))) { return QueueBack((obj-q1)); // 非空队列的队尾就是栈顶 } else { return QueueBack((obj-q2)); } }这里用了一个关键点队列的队尾back正好对应栈顶因为入栈时元素都在队尾追加。多开一个空间解决判空和判满相重合的问题解决回绕问题两种取尾的数据结果一样删除和增加都要有回环的能力获取头的数据比尾部简单因为尾部是有效节点的下一个位置就是包含加减的都会比较麻烦因为有回环的问题链表判断空很简单但是取尾部很麻烦