网站建设的大公司排名,网站情况建设说明书,哈尔滨优质官网建站企业,贵阳网站托管第一题#xff08;括号匹配#xff09;给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效。有效字符串需满足#xff1a;1.左括号必须用相同类型的右括号闭合。2.左括号必须以正确的顺序闭合。…第一题括号匹配给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。有效字符串需满足1.左括号必须用相同类型的右括号闭合。2.左括号必须以正确的顺序闭合。3.每个右括号都有一个对应的相同类型的左括号。char pairs(char* ch)
{if(*ch})return {;if(*ch))return (;if(*ch])return [;return 0;
}
bool isValid(char * s){char stack[10000]{0};int top0,i0;while(*(si)){char chpairs(si);if(ch){if(top0||ch!stack[top-1])//这里需要判断栈是否为空的原因是没有左括号还在匹配会造成越界{return false;}else{top--;}}else{stack[top]*(si);}i;}return top0;}第二题用队列模拟栈这里需要判断栈是否为空的原因是没有左括号还在匹配会造成越界请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* obj (MyStack*)malloc(sizeof(MyStack));QueueInit(obj-q1);QueueInit(obj-q2);return obj;
}void myStackPush(MyStack* obj, int x) {assert(obj);if (!QueueEmpty(obj-q1)){QueuePush(obj-q1);}else{QueuePush(obj-q2);}return;
}int myStackPop(MyStack* obj) {Queue* pEmpty obj-q1;//注意左右两边的类型要匹配Queue* pNonEmpty obj-q2;if (!QueueEmpty(pEmpty)){Queue* pEmpty obj-q2;Queue* pNonEmpty obj-q1;}while (QueueSize(pNonEmpty) 1){QueuePush(pNonEmpty, QueueFront(pNonEmpty));QueuePop(pNonEmpty);}int top QueueFront(pNonEmpty);QueuePop(pNonEmpty);return top;
}int myStackTop(MyStack* obj) {Queue* pEmpty obj-q1;Queue* pNonEmpty obj-q2;if (!QueueEmpty(pEmpty)){Queue* pEmpty obj-q2;Queue* pNonEmpty obj-q1;}return QueueBack(pNonEmpty);
}bool myStackEmpty(MyStack* obj) {if (!(QueueEmpty(obj-q2)) !(QueueEmpty(obj-q1))){return false;}return true;
}void myStackFree(MyStack* obj) {QueueDestory(obj-q1);//free可能会free不干净万一是链式结构呢QueueDestory(obj-q2);free(obj);
}第三题用栈模拟队列请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty实现 MyQueue 类void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false说明你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。解题思路可以用两个栈实现一个栈进行入队操作我们称为入队栈另一个栈进行出队操作我们称为出队栈出队操作 当出队栈不为空是直接进行出栈操作如果为空需要把入队栈元素全部导入到出队的栈然后再进行出栈操作。#define maxSize 100
typedef struct {//入队栈Stack pushST;//出队栈Stack popST;
} MyQueue;/** Initialize your data structure here. */
MyQueue* myQueueCreate(int maxSize) {MyQueue* pqueue (MyQueue*)malloc(sizeof(MyQueue));StackInit(pqueue-pushST, maxSize);StackInit(pqueue-popST, maxSize);return pqueue;
}/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {//入队栈进行入栈操作StackPush(obj-pushST, x);
}/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {//如果出队栈为空导入入队栈的元素if(StackEmpty(obj-popST) 0){while(StackEmpty(obj-pushST) ! 0){StackPush(obj-popST, StackTop(obj-pushST));StackPop(obj-pushST);}}int front StackTop(obj-popST);//出队栈进行出队操作StackPop(obj-popST);return front;
}/** Get the front element. */
int myQueuePeek(MyQueue* obj) {//类似于出队操作if(StackEmpty(obj-popST) 0){while(StackEmpty(obj-pushST) ! 0){StackPush(obj-popST, StackTop(obj-pushST));StackPop(obj-pushST);}}return StackTop(obj-popST);
}//判断栈是否为空
bool myQueueEmpty(MyQueue* obj) {return StackEmpty(obj-pushST) 0 StackEmpty(obj-popST) 0;
}void myQueueFree(MyQueue* obj) {StackDestroy(obj-pushST);//与上题一样不能直接free要交给栈的销毁函数来做StackDestroy(obj-popST);free(obj);
}第四题设计循环队列设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。你的实现应该支持如下操作MyCircularQueue(k): 构造器设置队列长度为 k 。Front: 从队首获取元素。如果队列为空返回 -1 。Rear: 获取队尾元素。如果队列为空返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。#define dataType int typedef struct {dataType* arr;int front;int rear;int size;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* ret (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (ret NULL){perror(malloc::fail);}ret-arr (dataType*)malloc(sizeof(dataType) * (k 1));ret-front ret-rear 0;ret-size k1;return ret;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (((obj-rear 1) %obj-size) obj-front)//判断循环队列是否为满,%不是/{return false;}obj-arr[obj-rear] value;obj-rear(obj-rear1)%obj-size;//不需要加MaxSizereturn true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (obj-rear obj-front){return false;}obj-front (obj-front 1) % obj-size;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (obj-rear obj-front){return -1;}return obj-arr[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj) {if (obj-rearobj-front){return -1;}//因为是先存数据在加加所以rear实际上是指向队尾的下一个元素//故最好在此处进行分类讨论if(obj-rear0){return obj-arr[obj-size-1];}else{return obj-arr[obj-rear-1];}}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-front obj-rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if (obj-front (obj-rear 1 obj-size) % obj-size){return true;}return false;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-arr);//双层释放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);
*/
