单位门户网站建设,站酷设计网站官网入,品牌网站设计有哪些建议,广州网站建设 全包目录
题目 思路1(链表)
代码
思路2(数组) 代码 题目 题目要求的队列需要实现的功能有 ①Creat---设置队列长度 ②Front---获取队列头 ③Rear---获取队列尾 ④en----插入元素 ⑤de---删除元素 ⑥empty---判空 ⑦full---判满 思路1(链表)
#x1f50d;普通队列长度没有限制普通队列长度没有限制循环队列的长度是初始化时被规定的。
❓ 请思考普通的队列我们可以通过链表来实现那么环状的队列能否继续通过链表实现呢 答案可以需要将链表设计为循环链表。解析这样可以通过最后一个链表节点找到第一个链表节点。
❓请思考怎么通过循环链表构造循环队列呢 构造出一个循环链表定义front指向队列头定义back指向队列尾后一个空间。规定frontback时队列为空。 插入4个元素 ❗注意此时不能继续插入元素了如果在插入元素back接下来就和front一样而这是我们之前定义队列为空的条件。也就是说在前提条件frontback表示队列为空时循环链表有5个节点只能存储4个数据推而广之如果想要队列中存放k个数据那么循环链表需要定义(k1)个节点。
删除元素删除队列头只需要将链表头删即可。 ❗注意头删不要将需要删除数据所在的空间释放这样可能会导致下次插入元素时非法访问内存空间。头删只需要让front指向下一个空间即可。front和back之间的数据才是队列中的元素。
❓请思考怎么找到队列尾 解决方案 ①循环队列结构中添加一个preTail指针指向链表尾节点的前一个结点。 ②遍历整个链表在链表尾节点的前一个节点时停止遍历。 ③使用双向循环链表。
三种方案大同小异这里不在赘述
代码
方案1代码
//使用链表实现循环队列
typedef struct Qnode
{struct Qnode* next;int val;
}Qnode;
typedef struct MyCircularQueue{Qnode* head;Qnode* tail;Qnode* preTail;int size;int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q (MyCircularQueue*)malloc(sizeof(MyCircularQueue));q-size 0;q-capacity k;//创建第一个空间q-head (Qnode*)malloc(sizeof(Qnode));q-tail q-head;q-preTail NULL;Qnode* cur q-head;//创建k个节点while (k--){cur-next (Qnode*)malloc(sizeof(Qnode));cur cur-next;}cur-next q-head;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满了插入失败if (obj-tail-next obj-head)return false;//插入数据obj-tail-val value;obj-preTail obj-tail;obj-tail obj-tail-next;obj-size;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//队列为空删除失败if (obj-size 0)return false;//链表头删(不要销free节点的空间)obj-head obj-head-next;obj-size--;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {return obj-size 0 ? -1 : obj-head-val;
}int myCircularQueueRear(MyCircularQueue* obj) {return obj-size 0 ? -1 : obj-preTail-val;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-size 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj-size obj-capacity;
}void myCircularQueueFree(MyCircularQueue* obj) {//需要释放k1个节点int cnt obj-capacity 1;Qnode* cur obj-head;while (cnt--){Qnode* tmp cur-next;free(cur);cur tmp;}free(obj);
}
方案2代码
//使用链表实现循环队列
typedef struct Qnode
{struct Qnode* next;int val;
}Qnode;
typedef struct MyCircularQueue{Qnode* head;Qnode* tail;int size;int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q (MyCircularQueue*)malloc(sizeof(MyCircularQueue));q-size 0;q-capacity k;//创建第一个空间q-head (Qnode*)malloc(sizeof(Qnode));//tailfront初始化为空q-tail q-head;Qnode* cur q-head;//创建k个节点while (k--){cur-next (Qnode*)malloc(sizeof(Qnode));cur cur-next;}cur-next q-head;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满了插入失败if (obj-size obj-capacity)return false;//插入数据obj-tail-val value;obj-tail obj-tail-next;obj-size;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//队列为空删除失败if (obj-size 0)return false;//链表头删(不要销free节点的空间)obj-head obj-head-next;obj-size--;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {return obj-size 0 ? -1 : obj-head-val;
}int myCircularQueueRear(MyCircularQueue* obj) {if (obj-size 0)return -1;//遍历链表Qnode* cur obj-head;while (cur-next ! obj-tail){cur cur-next;}return cur-val;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-size 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj-size obj-capacity;
}void myCircularQueueFree(MyCircularQueue* obj) {//需要释放k1个节点int cnt obj-capacity 1;Qnode* cur obj-head;while (cnt--){Qnode* tmp cur-next;free(cur);cur tmp;}free(obj);
}
方shuzu案3代码
//使用链表实现循环队列
typedef struct Qnode
{struct Qnode* next;struct Qnode* pre;int val;
}Qnode;
typedef struct MyCircularQueue{Qnode* head;Qnode* tail;int size;int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q (MyCircularQueue*)malloc(sizeof(MyCircularQueue));q-size 0;q-capacity k;//创建第一个空间q-head (Qnode*)malloc(sizeof(Qnode));//tailfront初始化为空q-tail q-head;Qnode* cur q-head;//创建k个节点while (k--){Qnode* newnode (Qnode*)malloc(sizeof(Qnode));cur-next newnode;newnode-pre cur;cur cur-next;}cur-next q-head;q-head-pre cur;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满了插入失败if (obj-size obj-capacity)return false;//插入数据obj-tail-val value;obj-tail obj-tail-next;obj-size;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//队列为空删除失败if (obj-size 0)return false;//链表头删(不要销free节点的空间)obj-head obj-head-next;obj-size--;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {return obj-size 0 ? -1 : obj-head-val;
}int myCircularQueueRear(MyCircularQueue* obj) {return obj-size 0 ? -1 : obj-tail-pre-val;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-size 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj-size obj-capacity;
}void myCircularQueueFree(MyCircularQueue* obj) {//需要释放k1个节点int cnt obj-capacity 1;Qnode* cur obj-head;while (cnt--){Qnode* tmp cur-next;free(cur);cur tmp;}free(obj);
}
思路2(数组)
❓先思考通过数组实现的环形队列有哪些成员 数组、队列头下标、队列尾下标、队列元素个数、队列最大容量。
我们规定头下标和尾下标相等时队列为空。 来看数组模拟循环队列示意图(队列的容量是5) ①队列为空 ②入队 ③出队 ④入队
❗注意从上述过程中可以观察到在物理结构中 队尾可能在队头的前面也可能在队头后面。 思维导图 代码
typedef struct {int* a;//a指向数组int front;//头下标int back;//尾下标int size;//队列元素个数int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q (MyCircularQueue*)malloc(sizeof(MyCircularQueue));q-a (int*)malloc(sizeof(int) * (k 1));q-size 0;q-capacity k;q-front q-back 0;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列已满if (obj-size obj-capacity)return false;obj-a[obj-back] value;obj-back;//尾下标越界归0if (obj-back obj-capacity){obj-back 0;}obj-size;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (obj-size 0)return false;obj-front;//头下标越界归0if (obj-front obj-capacity)obj-front 0;obj-size--;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {return obj-size 0 ? -1 : obj-a[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj) {//空队列if (obj-size 0)return -1;if (obj-back 0){return obj-a[obj-capacity];}return obj-a[obj-back - 1];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-size 0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj-size obj-capacity;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}
