算法与数据结构（1）——栈和队列初步认识


《栈》
栈的实现栈只能在一头进行操作，相对比较容易实现。用一个数组int stack[]和栈顶指针top即可，插入和删除（也称push和pop）
栈的实现代码：
//用一个数组int stack[]和栈顶指针top即可实现//top指向栈顶元素（即栈顶元素的坐标）//这里逻辑上的“顶”实际上为无理数组上的“尾”部；1 stack[++top ] = x ; /¤ push ¤/2 x = s tack [ top ¡¡]; /¤ pop ¤/
对物理实现和逻辑实现的理解：
和链表删除类似，出栈时并不需要让stack[top]变为0。由于top已经减1了，在逻辑上原来的栈顶元素已经不在栈中，虽然在物理上这个元素本身没有一点变化。
《队列》：
可以借鉴STL的规矩，把¯rst作为第一个元素而last 作为最后一个元素的后一个位置，则插入和删除的
代码如下：
1 //注意first指向第一个元素，2  //last指向最后一个元素的后一个位置  //队列的实现，一个数组，两个指针即可，前插入，后弹出3  x = queue [ f i r s t ++] ;/*出队*/4 queue [ l a s t ++] = x ; /*入队*/
出现的问题：空间上的浪费 ！！！
解决代码方案——循环队列：
//没有加“尾撞头”可能性的判断和处理，所以该队列的元素承载量要保证//不能超过预设的nx = queue [ f i r s t ] ; f i r s t = ( f i r s t+1)%n ; /*出队*/queue [ l a s t ] = x ; l a s t = ( l a s t+1)%n ; /*入队*/

补充：综合编程 , 其他综合 ,