声明：仅供留档查阅，仅用作起到提示引导性作用，仅用作学习交流，切勿直接照搬

Ch3-1.

总结栈空、栈满、队空、队满的判定条件。

栈和队列是两种常见的数据结构，它们的空和满的判断条件如下：

栈：

  • 栈空：当栈顶指针top等于-1时，表示栈为空。
  • 栈满：当栈顶指针top等于栈的最大容量减1（假设栈的最大容量为maxSize）时，表示栈已满，即top == maxSize - 1。

队列：

  • 队空：当队头指针front等于队尾指针rear时，表示队列为空。
  • 队满：这个判断条件取决于你如何实现队列。如果你使用数组实现循环队列，那么当(rear + 1) % maxSize == front时，表示队列已满（假设队列的最大容量为maxSize）。这里的 % 是取余运算，用于实现循环。

Ch3-2.

循环队列的优点是什么？设用数组来存放循环队列，你有几种判断队满和队空的方案？

循环队列的优点主要有以下几点：

  1. 有效利用空间：在普通队列中，当队尾指针到达数组的末端时，即使数组的前端还有空闲空间，也无法再添加新的元素。而循环队列通过将队列的首尾相连，形成一个循环，使得在队尾指针到达数组末端时，可以从数组前端继续添加新的元素，从而更有效地利用了空间。
  2. 避免数据迁移：在普通队列中，每次出队操作后，为了维持队列的连续性，需要将所有元素向前移动一位，这会消耗大量的时间和计算资源。而在循环队列中，通过移动队头和队尾指针来实现入队和出队操作，无需移动元素本身，因此效率更高。

对于使用数组实现的循环队列，常见的判断队满和队空的方案有以下几种：

  1. 牺牲一个存储空间：这是最常见的方法。当(rear + 1) % maxSize == front时，判断队列已满；当rear == front时，判断队列为空。这种方法的缺点是会浪费一个数组的存储空间。
  2. 使用一个标志位：除了使用front和rear两个指针外，还可以额外使用一个标志位来判断队列的状态。当入队操作后rear == front时，将标志位设为满；当出队操作后rear == front时，将标志位设为空。这种方法可以充分利用所有存储空间，但需要额外的标志位。
  3. 记录元素个数：除了使用front和rear两个指针外，还可以使用一个计数器来记录队列中元素的个数。当计数器为0时，判断队列为空；当计数器等于数组大小时，判断队列已满。这种方法同样可以充分利用所有存储空间，但需要额外的计数器。

Ch3-3.

*假设以带头结点的循环单链表表示队列，并且只设一个尾指针Node*Rear 指向队尾结点（没有队头指针Node front），试编写入队和出队算法。

自己写的，目前还在报错，修改中……

已完工

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>                  //引入输入输出流
using namespace std;

template <typename DataType>
struct Node
{
    DataType data;               //数据域
    Node<DataType>* next;       //指针域
};

template <typename DataType>
class LinkList_Queue
{
public:
    LinkList_Queue();                      //无参构造函数，建立只有头结点的空链表
    ~LinkList_Queue();                     //析构函数
    int Empety();
    DataType Push(DataType x);       //插入操作，第i个位置插入值为x的结点
    DataType Pop();            
private:
    Node<DataType>* first, * rear;           //单链表的头指针
};

template <typename DataType>
LinkList_Queue<DataType> ::LinkList_Queue()
{
    Node<DataType>* s = nullptr;
    s = new Node<DataType>;    
    s->next = nullptr;
    first = rear = s;                      //头结点的指针域置空
}

template <class DataType>
LinkList_Queue<DataType> :: ~LinkList_Queue()
{

}

template <typename DataType>
int LinkList_Queue<DataType> ::Empety()
{
    if (first == rear)
        return 1;
    else
        return 0;
}


//入队算法
template <typename DataType>
DataType LinkList_Queue<DataType> ::Push(DataType x)
{
    Node<DataType>* s = nullptr;           
    s = new Node<DataType>; 
    s->data = x;
    s->next = nullptr;
    rear->next = s;
    rear = s;
    return x;
}

//出队算法
template <typename DataType>
DataType LinkList_Queue<DataType> ::Pop()
{
    if (first == rear )
    {
        cout << "队空" << endl;
        return 0;
    }
    else
    {
        DataType x;
        Node<DataType>* p = first->next;
        x = p->data;
        first->next = p->next;
        if (rear == p)  // 如果队列中只有一个元素
            rear = first;  // 则需要更新尾指针
        delete p;
        return x;
    }
}

int main()
{
    LinkList_Queue<int> s = {};
    int a = 0;
    s.Push(1);
    s.Push(2);
    s.Push(3);
    cout << "已入队1,2,3" << endl;
    cin >> a;
    cout << "已入队：" << s.Push(a) << endl;
    cout << "出队一次"<< endl;
    cout << "已出队：" << s.Pop() << endl;
    cout << "已出队：" << s.Pop() << endl;
    cout << "已出队：" << s.Pop() << endl;
    cout << "已出队：" << s.Pop() << endl;
    return 0;
}

AI生成的，不想做了，谨慎查阅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#include <stdlib.h>

// 定义结点
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义队列
typedef struct Queue {
    Node* rear;
} Queue;

// 初始化队列
Queue* initQueue() {
    Node* head = (Node*)malloc(sizeof(Node));  // 创建头结点
    head->next = head;  // 循环链表
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->rear = head;  // 尾指针指向头结点
    return queue;
}

// 入队操作
void enQueue(Queue* queue, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = queue->rear->next;  // 新结点指向头结点
    queue->rear->next = newNode;  // 尾结点指向新结点
    queue->rear = newNode;  // 更新尾指针
}

// 出队操作
int deQueue(Queue* queue) {
    if (queue->rear == queue->rear->next) {
        printf("队列为空，无法出队。\n");
        return -1;
    }
    Node* head = queue->rear->next;  // 头结点
    Node* firstNode = head->next;  // 第一个结点（即要出队的结点）
    int data = firstNode->data;
    head->next = firstNode->next;  // 头结点指向第二个结点
    if (firstNode == queue->rear) {  // 如果只有一个元素，出队后更新尾指针
        queue->rear = head;
    }
    free(firstNode);  // 释放出队的结点内存
    return data;
}

int main() {
    Queue* queue = initQueue();
    

    printf("入队：\n");
    for (int i = 1; i <= 5; i++) {
        printf("%d ", i);
        enQueue(queue, i);
    }
    
    printf("\n出队：\n");
    for (int i = 1; i <= 5; i++) {
        printf("%d ", deQueue(queue));
    }
    
    return 0;

}