数据结构考试知识点总结——栈和队列
- 学会求不可能的的出栈序列。
- 设计一个判断表达式中左，右括号是否配对出现的算法，采用栈最佳。
- 用链接方式存储的队列，再进行删除运算时，头尾指针可能都要修改。
- 递归过程或函数调用时，处理参数及返回地址，要用栈。
- 将递归算法转换成对应的非递归算法时，通常需要栈来保存中间结果。
- 假设数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为**(rear-front+m)%m**
- 栈和队列共同点是只允许在端点处插入和删除元素。
- 栈和队列的主要区别是限定插入和删除的位置不同。
- 队列的插入操作是在队尾，删除操作在队首；栈的插入和删除操作在栈顶。
- 大小为N的数组存储顺序循环队列的最大长度为N-1。
- 在解决计算机主机和打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区是一个队列结构。
- 循环队列是随机存取的存储结构。
- CPU资源管理问题求解过程中无须使用栈。
- 页面替换问题求解过程中需要用到队列。
- 递归过程或调用函数时，处理参数及返回地址，要用栈。
- 顺序栈空条件：top == -1;
- 顺序栈满条件：top == MaxSize-1;
- 顺序栈元素e进栈操作：top++; data[top] = e;
- 顺序栈元素e出栈操作：e = data[top]; top–;
- 链栈空条件：S.head.next == null;
- 链栈满条件：不考虑
- 链栈元素e进栈操作：LinkStack p = new LinkStack; p.data = e; p.next = head.next; head.next = p;
- 栈链元素e出栈操作：LinkStack p; p = head.next; e = p.data; head.next = p.next; p = null;
- 顺序队空条件：front == rear;
- 顺序队满条件：(rear + 1) % MaxSize == front;
- 顺序队元素e进队操作：rear = (rear +1) % MaxSize; e = data[rear];
- 顺序队元素e出队操作：front = (front + 1) % MaxSize; e = data[front];
- 链队队空条件：Q.rear == null;(也可以Q.front == null);
- 链队队满条件：不考虑。
- 链队元素e进队操作：LinkNode p = new LinkNode(); p.data = e; Q.rear.next = p; Q.rear = p;
- 链队元素e出队操作：LinkNode p = Q.front; Q.front = Q.front.next; p = null;
