医院网站建设具体内容,湖南网站推广建设公司,杭州建筑设计公司排名,阳曲网站建设价格多少20. 有效的括号
给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效。
有效字符串需满足#xff1a;
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应…20. 有效的括号
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
AC
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top; //标识栈顶位置元素数量int capacity; //栈的容量
}ST;void STInit(ST* pst);
void STDestory(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;// 1.表示top指向栈顶元素的下一个位置pst-top 0;// 2.表示top指向栈顶元素//pst-top -1; // top为0的话不清楚是top为0还是空因此空的时候给-1//位置(下标) top 0 1//数值 -1(空) 0 1//top 1指向栈顶元素的下一个位置}void STDestory(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;}void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2; //如果栈的当前容量为0将其设为4否则将其扩大为当前容量的两倍STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp; //将原来栈中数据的指针更新为新的内存空间的指针pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-a[pst-top - 1];
}bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}int STSize(ST* pst)
{assert(pst);return pst-top;}bool isValid(char* s) {ST st;STInit(st);while(*s){if(*s ( || *s [ || *s {){STPush(st,*s);}else{// 这种情况是右括号多现在有右括号但是现在存左括号的栈里是空的if(STEmpty(st)){STDestory(st);return false;}// 栈里面取左括号进行判断char top STTop(st);STPop(st);if((*s ) top ! ()|| (*s ] top ! [)|| (*s } top ! {)){return false;}}s;}// 若左右括号数量不相同栈里可能还会有括号上述只能解决可以对应的// 栈为空返回真说明数量也匹配这行解决左括号多右括号少的情况bool ret STEmpty(st);STDestory(st);return ret;
}
代码思路
这道题使用C解题需要创建一个栈但是使用C可以直接用栈暂时先使用C语言解题因此上述代码实现了栈的功能手搓哈哈哈后续会更新C版本具体解题函数为最后一个。在栈里存储左括号如果遍历到了左括号就入栈遍历到了右括号就拿出栈里最后一个入栈的也就是离该右括号最近的左括号进行判断是不是相匹配的这一步判断由于是字符所以需要将情况都列出来然后只要不匹配就返回false若果匹配s就继续下一个判断但是在该左括号判断后一定要出栈。
但是有种情况是右括号比左括号多遍历到了右括号此时存左括号的栈是空的这时候直接返回false所以这里需要检测栈是否为空返回前需要将栈清空否则有可能发生内存泄漏。
还有一种情况是左括号比右括号多在右括号都遍历完以后栈内依旧存着左括号因此在可以匹配的括号都判断以后需要检测栈内是否为空然后将栈清空。最后返回值使用了栈是否为空的判断返回值ret因为如果ret为true就说明栈确实是空的匹配正好都对应符合题目要求而返回false说明栈不空左括号还有多余的不是匹配的。
另外在创建实例的时候要注意不能使用和形参一样的变量这段代码中使用的是st因为函数传参写的是s否则会分不清到底是存储需要入栈的左括号还是指向字符数组的指针。
225. 用队列实现栈
请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
AC
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead; // 头指针QNode* ptail; // 尾指针int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}void QueueDestory(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);// 空节点assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);// 一个节点的时候phead向前走// del被freeptail此时和del指的是一个节点如果free就变成了野指针if (pq-phead NULL){pq-ptail NULL;}pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);// 空节点assert(pq-phead);return pq-phead-val;
}QDataType QueueBack(Queue* pq)
{assert(pq);// 空节点assert(pq-phead);return pq-ptail-val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}//上述代码为队列的实现
//下边开始用队列实现栈的逻辑typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst (MyStack*)malloc(sizeof(MyStack));QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}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;}// 非空队列前N-1个导入空队列最后一个就是栈顶元素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) {QueueDestory(obj-q1);QueueDestory(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);
*/
代码思路
栈和队列的区别就是先进先出和后进先出用队列实现栈假设现在队列内已经入队 1 2 3 4 5 要出队的话必定是 1 2 3 4 5现在是栈进行出栈那么就是 5 4 3 2 1此题给了我们两个队列当我们要出栈也就是让 5 先出就可以把队列 1 中的 1 2 3 4 依次出队并同时入队列 2然后弹出 5接着再将队列 2 中的 1 2 3 出队列并入队列 1弹出 4……依次这样交替执行就可以用两个队列实现栈了。虽然这道题实际上并没有什么卵用但是逻辑结构真的很锻炼人我也是只清楚大致思路代码一团糟可参考力扣官方给的解题代码
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty
实现 MyQueue 类
void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false
AC
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; //标识栈顶位置元素数量int capacity; //栈的容量
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;pst-top 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2; //如果栈的当前容量为0将其设为4否则将其扩大为当前容量的两倍STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp; //将原来栈中数据的指针更新为新的内存空间的指针pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-a[pst-top - 1];}bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}int STSize(ST* pst)
{assert(pst);return pst-top;
}//上述代码为栈的实现
//下边开始用栈实现队列的逻辑typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(obj-pushst, x);
}int myQueuePop(MyQueue* obj) {int front myQueuePeek(obj);STPop(obj-popst);return front;
}int myQueuePeek(MyQueue* obj) {if(STEmpty(obj-popst)){// 倒数据过来while(!STEmpty(obj-pushst)){STPush(obj-popst, STTop(obj-pushst));STPop(obj-pushst);}}return STTop(obj-popst);
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-pushst) STEmpty(obj-popst);
}void myQueueFree(MyQueue* obj) {STDestroy(obj-pushst);STDestroy(obj-popst);free(obj);
}代码思路
用栈实现队列假设现在栈内已经入队 1 2 3 4 5 要出栈的话必定是 5 4 3 2 1现在是队列进行出队列那么就是 1 2 3 4 5 此题给了我们两个栈当我们要出队列也就是让 1 先出就可以把栈 1 中的 5 4 3 2 依次出栈并同时入栈 2然后弹出 1接着栈 2 中的 5 4 3 2 出栈就已经是队列需要的顺序了执行栈2的出栈就是整个队列的出队机制了。Peek是查队列头部元素那就是栈2的顶部元素栈1如果为空直接返回栈2的顶部元素不为空先pop到栈2再返回。说实话栈实现队列更容易一些到这里逻辑比队列实现栈清楚许多了
