关于加强网站建设与管理的通知北京网站制作人才

当前位置： 首页 > news >正文

关于加强网站建设与管理的通知,北京网站制作人才,山西本土网站建设,wordpress改论坛文章目录225. 用队列实现栈示例#xff1a;提示#xff1a;分析#xff1a;题解#xff1a;622. 设计循环队列示例#xff1a;提示#xff1a;分析#xff1a;题解#xff1a;225. 用队列实现栈 请你仅使用两个队列实现一个后入先出#xff08;LIFO#xff09;的栈提示分析题解622. 设计循环队列示例提示分析题解225. 用队列实现栈 请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。 实现 MyStack 类 void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的返回 true 否则返回 false 。 注意 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 你所使用的语言也许不支持队列。 你可以使用 list 列表或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。 示例 输入 [“MyStack”, “push”, “push”, “top”, “pop”, “empty”] [[], [1], [2], [], [], []] 输出 [null, null, null, 2, 2, false] 解释 MyStack myStack new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False 提示 1 x 9 最多调用100 次 push、pop、top 和 empty 每次调用 pop 和 top 都保证栈不为空 分析 目前没有学习C所以先用C语言实现。那么就要手撕一个队列。例子输入1 2 3 4输出 4 3 2 1根据队列的性质先进先出所以先要进行移数据只剩一个然后出数据来回倒腾。
题解 #includestdio.h #includeassert.h #includemalloc.h #includestdbool.htypedef int QDataType;//这是结点的结构但是队列是FIFO所以要记录头指针和尾指针方便尾入和头出 typedef struct QueueNode {struct QueueNode* next;QDataType data; }QNode;typedef struct Queue {QNode* head;//有多个数据就可以再使用一个结构体QNode* tail;int size; }Queue;void QueueInit(Queue* pq);//队列的初始化 void QueueDestroy(Queue* pq);//队列的销毁 void QueuePush(Queue* pq, QDataType x);//队列的尾部插入数据 void QueuePop(Queue* pq);//队列的头部删除数据 bool QueueEmpty(Queue* pq);//判断队列为不为空 int QueueSize(Queue* pq);//知道队列有几个有效元素 QDataType QueueFront(Queue* pq);//返回队列的首个元素 QDataType QueueBack(Queue* pq);//返回队列的尾元素void QueueInit(Queue* pq) {assert(pq);pq-head pq-tail NULL;//队列的初始化将两个指针置为空pq-size 0;//有效元素为0 }void QueueDestroy(Queue* pq) {assert(pq);//将一个结点指针指向头节点作为循环的条件QNode* cur pq-head;while (cur){QNode* del cur-next;//一个要删除的结点free(cur);cur del;//指向下一个结点}//销毁时及时将两个指针置为空避免野指针的出现pq-head pq-tail NULL;pq-size 0; }void QueuePush(Queue* pq, QDataType x) {assert(pq);QNode* newnode (QNode)malloc(sizeof(QNode));//malloc申请新的结点if (newnode NULL){perror(malloc fail);//申请失败报错并返回return;}//如果为空队列那么就要将指针同时指向新的结点if (pq-head NULL){pq-head pq-tail newnode;}else//这里没加else语句那么if执行了的话就会混乱{pq-tail-next newnode;pq-tail newnode;//同时将尾指针指向新的结点}//将尾结点的next指向新的结点newnode-data x;//新的结点进行赋值newnode-next NULL;pq-size;//有效元素进行加1 }void QueuePop(Queue pq) {assert(pq);assert(!QueueEmpty(pq));//空的队列就不能删除QNode* del pq-head;pq-head pq-head-next;//将头指针指向下个结点free(del);//释放空间del NULL;//这里要考虑只有一个节点的时候tail可能会是野指针if (pq-head NULL){pq-tail NULL;}pq-size–;//有效元素减1 }bool QueueEmpty(Queue* pq) {assert(pq);return pq-size 0; }int QueueSize(Queue* pq) {assert(pq);return pq-size; }QDataType QueueFront(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-head-data; }QDataType QueueBack(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-tail-data; }//创建两个队列 typedef struct {Queue q1;Queue q2; } MyStack;MyStack* myStackCreate() {//对队列进行初始化MyStack* newStack (MyStack)malloc(sizeof(MyStack));if (newStack NULL){perror(malloc fail);return NULL;}QueueInit(newStack-q1);QueueInit(newStack-q2);return newStack; }void myStackPush(MyStack obj, int x) {//如果一个队列为空那么就放入另一个队列if (!QueueEmpty(obj-q1)){QueuePush(obj-q1, x);}else{QueuePush(obj-q2, x);} }int myStackPop(MyStack* obj) {//利用假设法找出有数据的队列Queue* emptyq obj-q1;Queue* nonemptyq obj-q2;if (!QueueEmpty(obj-q1)){emptyq obj-q2;nonemptyq obj-q1;}//进行倒元素直到剩下一个元素while (QueueSize(nonemptyq) 1){QueuePush(emptyq, QueueFront(nonemptyq));QueuePop(nonemptyq);}int top QueueFront(nonemptyq);QueuePop(nonemptyq);return top; }int myStackTop(MyStack* obj) {//哪一个不为空就返回哪一个if (!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);} }bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1) QueueEmpty(obj-q2); }void myStackFree(MyStack* obj) {//malloc几次就要释放几次QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj); }/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj myStackCreate();* myStackPush(obj, x);* int param_2 myStackPop(obj);* int param_3 myStackTop(obj);* bool param_4 myStackEmpty(obj);* myStackFree(obj); /622. 设计循环队列 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。 你的实现应该支持如下操作 MyCircularQueue(k): 构造器设置队列长度为 k 。 Front: 从队首获取元素。如果队列为空返回 -1 。 Rear: 获取队尾元素。如果队列为空返回 -1 。 enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。 deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。 isEmpty(): 检查循环队列是否为空。 isFull(): 检查循环队列是否已满。 意思就是设计一个开好的空间存放数据并且具有队列的性质而且还能存放很多值。 示例 MyCircularQueue circularQueue new MyCircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4 提示 所有的值都在 0 至 1000 的范围内 操作数将在 1 至 1000 的范围内 请不要使用内置的队列库。 分析 这道题目可以使用数组实现这是一个空间固定的数组如何判断这个数组是满还是空呢可以多开一个空间作为缓冲位置。 每次插入之前要判断是否满了每次删除之前要判断是否空了。 还要考虑rear在队尾时如何判满rear在队头时如何找到最后一个数front在队尾时如何判断为多少 题解 typedef struct {int s;int front;int rear;int k; } MyCircularQueue;//创建循环队列 MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj (MyCircularQueue)malloc(sizeof(MyCircularQueue));if (obj NULL){perror(malloc fail);return NULL;}//创建数组时多创建一个空间以便进行循环obj-s (int)malloc(sizeof(int) * (k 1));if (obj-s NULL){perror(malloc fail);return NULL;}//将头指针和尾指针置为空将长度记住obj-front obj-rear 0;obj-k k;return obj; } //如果头指针和尾指针相等代表为空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-rear obj-front; } //为满的情况1. rear在front前面直接进行加1是否相等相等则满了 //2. rear在front后面考虑rear在队尾那么要将rear指向下标0就要进行模运算相等就满了 bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-rear 1) % (obj-k 1) obj-front; }bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//插入元素如果为满就返回假if (myCircularQueueIsFull(obj))return false;obj-s[obj-rear] value;//让rear指向下个位置考虑rear在队尾那么就要进行模运算obj-rear (obj-rear 1) % (obj-k 1); return true; }bool myCircularQueueDeQueue(MyCircularQueue* obj) {//删除元素如果为空就返回假if (myCircularQueueIsEmpty(obj))return false;//要将front指向下一个但是要考虑front在队尾进行模运算obj-front (obj-front 1) % (obj-k 1);return true; }int myCircularQueueFront(MyCircularQueue* obj) {//队列为空返回-1if (myCircularQueueIsEmpty(obj))return -1;return obj-s[obj-front]; }int myCircularQueueRear(MyCircularQueue* obj) {//队列为空返回-1if (myCircularQueueIsEmpty(obj))return -1;//考虑rear在队头的情况在队头就赋值为队尾元素其它情况就返回前一个元素int tail obj-rear 0?obj-s[obj-k]:obj-s[obj-rear - 1];return tail; }void myCircularQueueFree(MyCircularQueue* obj) {//申请两个空间就要释放两个空间free(obj-s);free(obj); }/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj myCircularQueueCreate(k);* bool param_1 myCircularQueueEnQueue(obj, value);* bool param_2 myCircularQueueDeQueue(obj);* int param_3 myCircularQueueFront(obj);* int param_4 myCircularQueueRear(obj);* bool param_5 myCircularQueueIsEmpty(obj);* bool param_6 myCircularQueueIsFull(obj);* myCircularQueueFree(obj); */