前言
计划更新23王道数据结构所有课后代码习题的实现，虽然考试写的一般都是伪代码，但是强迫症的我还是全部实现了一遍，仓库在这里
代码是用 C++ 写的，全部可以编译运行，尽量包含暴力解和最优解（考试时间不够可以直接怼一个暴力上去，稳拿一半分以上）。
持续更新，目前更新进度：
- 线性表 14/14
- 链表 25/25
- 栈 3/3
- 队列 4/4
- 栈和队列的应用
- ...
仅供参考！ 会包含一些考试不让写的语法，可能也会有一些错误。
3.2.6, 1
- 队空：
Q.front == Q.rear && Q.tag == 0 - 队满：
Q.front == Q.rear && Q.tag == 1 - 因为只有进队操作会导致队满，所以在进队时将tag置为1，同理在出队时将tag置为0
bool enqueue(Queue &Q, int x) { if (Q.front == Q.rear && Q.tag == 1) { cout << "队列满" << endl; return false; } Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % maxsize; Q.tag = 1; return true; } bool dequeue(Queue &Q, int &x) { if (Q.front == Q.rear && Q.tag == 0) { cout << "队列空" << endl; return false; } x = Q.data[Q.front]; Q.front = (Q.front + 1) % maxsize; Q.tag = 0; return true; } 复制代码
2
- 队内元素逐个出队入栈，全部入栈后再逐个出栈入队列即可
- 非常简单的一道题，就是考察“先进先出”以及“后进先出”的性质
void reverseQueue(Queue &Q, Stack &S) { int x; while (!isEmpty(Q)) { dequeue(Q, x); push(S, x); } while (!isEmpty(S)) { pop(S, x); enqueue(Q, x); } } 复制代码
3
- S1的入栈用作入队，若S1满且S2空，才能将S1的元素插入S2中
- S2的出栈用作出队，若S2空，将S1的所有元素插入S2中
- 判空只需要判断两个栈是否都为空
bool Enqueue(Stack &S1, Stack &S2, int x) { if (!StackOverflow(S1)) { Push(S1, x); return true; } if (StackOverflow(S1) && !StackEmpty(S2)) { cout << "队列满" << endl; return false; } // S1满且S2空，先将S1中的元素全部入S2，再入S1 while (!StackEmpty(S1)) { int tmp; Pop(S1, tmp); Push(S2, tmp); } Push(S1, x); return true; } bool Dequeue(Stack &S1, Stack &S2, int &x) { if (!StackEmpty(S2)) { Pop(S2, x); return true; } if (StackEmpty(S1)) { cout << "队列空" << endl; return false; } // S2为空且S1不为空 while (!StackEmpty(S1)) { int tmp; Pop(S1, tmp); Push(S2, tmp); } Pop(S2, x); return true; } bool QueueEmpty(Stack S1, Stack S2) { return StackEmpty(S1) && StackEmpty(S2); } 复制代码
4
- 如题，应选择链式存储结构，且为包含头尾指针的单循环链表（头front，尾rear)
- 队空条件
front == rear - 队满条件
front == rear -> next - 遵循”入判满，出判空“的原则，写出伪代码即可
