代码随想录算法训练营第九天|232.用栈实现队列、225.用队列实现栈、 20.有效的括号、1047.删除字符串中的所有相邻重复项

文章目录

• 232.用栈实现队列
• • 思路--直接模拟
• 225.用队列实现栈
• • 解法一、两个队列模拟
  • 解法二、一个队列模拟
• 20.有效的括号
• • 栈模拟
• 1047.删除字符串中的所有相邻重复项
• • 解法一、栈
  • 解法二、双指针

232.用栈实现队列

题目链接：232. 用栈实现队列 - 力扣（LeetCode）
题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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 操作是合法的。

思路–直接模拟

设置两个栈，一个输入栈，一个输出栈，在push操作时，只需要将数据放进输入栈即可，但是在pop的时候，如果输出栈为空，就需要先把输入栈的全部数据放进输出栈，再从输出栈弹出数据，如果输出栈为不为空，直接弹出数据即可。
当输入栈和输出栈均为空时，模拟队列为空

typedef struct {
    int input[100];
    int output[100];
    int inputTop;
    int outputTop;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue *obj=(MyQueue*)malloc(sizeof(MyQueue));
    obj->inputTop=0;
    obj->outputTop=0;
    return obj;
}
void myQueuePush(MyQueue* obj, int x) {
    obj->input[obj->inputTop]=x;
    obj->inputTop++;
}
int myQueuePop(MyQueue* obj) {
    if(obj->outputTop==0){//输出栈为空时，将输入栈全部数据放进输出栈中
        while(obj->inputTop){
            obj->inputTop--;
            obj->output[obj->outputTop++]=obj->input[obj->inputTop];
        }
    }
    int ans=obj->output[obj->outputTop-1];
    obj->outputTop--;
    return ans;
}
int myQueuePeek(MyQueue* obj) {
    if(obj->outputTop==0){
        return obj->input[0];
    }
    return obj->output[obj->outputTop-1];
}

bool myQueueEmpty(MyQueue* obj) {
    if(obj->inputTop==0&&obj->outputTop==0){
        return true;
    }
    return false;
}

void myQueueFree(MyQueue* obj) {
    free(obj);
    obj=NULL;
}

225.用队列实现栈

题目链接：225. 用队列实现栈 - 力扣（LeetCode）
题目描述：请你仅使用两个队列实现一个后入先出（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 这些操作。

只能使用单端队列

解法一、两个队列模拟

设置两个队列queue1、queue2，先用queue2备份queue1，弹出最后面的元素，再把其他元素从queue2导回queue1,就做到了后进先出。

typedef struct {
    int que1[100];
    int rear1,front1;
    int que2[100];//备份队列
    int rear2,front2;
} MyStack;
MyStack* myStackCreate() {
    MyStack *stack=(MyStack*)malloc(sizeof(MyStack));
    stack->front1=0,stack->front2=0;
    stack->rear1=0,stack->rear2=0;
    return stack;
}
void myStackPush(MyStack* obj, int x) {
    obj->que1[obj->rear1++]=x;
}
int myStackPop(MyStack* obj) {
    // //优化：复制队列头尾指针，减少对内存的访问次数
    int rear1=obj->rear1;
    int rear2=obj->rear2;
    int front1=obj->front1;
    int front2=obj->front2;
    while(front1<rear1){//将que1备份到que2中
        obj->que2[rear2++]=obj->que1[front1++];
    }
    rear1=0,front1=0;
    int top=obj->que2[--rear2];//弹出最后一个元素
    while(front2<rear2){//将que2导回que1
        obj->que1[rear1++]=obj->que2[front2++];
    }
    obj->rear1=rear1,obj->front1=front1;
    obj->rear2=0,obj->front2=0;
    return  top;
}
int myStackTop(MyStack* obj) {
    return obj->que1[obj->rear1-1];
}
bool myStackEmpty(MyStack* obj) {
    return obj->front1==obj->rear1 ? true:false;
}
void myStackFree(MyStack* obj) {
    free(obj);
    obj=NULL;
}

解法二、一个队列模拟

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外）重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

typedef struct {
    int que[100];
    int rear,front;
} MyStack;
MyStack* myStackCreate() {
    MyStack *stack=(MyStack*)malloc(sizeof(MyStack));
    stack->rear=0;
    stack->front=0;
    return stack;
}
void myStackPush(MyStack* obj, int x) {
    obj->que[obj->rear++]=x;
}
int myStackPop(MyStack* obj) {
    int rear=obj->rear;
    int front=obj->front;
    int temp=rear;
    while(front<temp-1){
        obj->que[rear++]=obj->que[front++];
    }
    int top=obj->que[front++];
    obj->rear=rear;
    obj->front=front;
    return top;
}
int myStackTop(MyStack* obj) {
    return obj->que[obj->rear-1];
}
bool myStackEmpty(MyStack* obj) {
    return obj->rear==obj->front?true:false;
}
void myStackFree(MyStack* obj) {
    free(obj);
    obj=NULL;
}

20.有效的括号

题目链接：20. 有效的括号 - 力扣（LeetCode）
题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

栈模拟

bool isValid(char * s){
   int len=strlen(s);
   char *stack=(char*)malloc(sizeof(char)*len);
   int top=0;
   for(int i=0;i<len;i++){
       if(s[i]=='('||s[i]=='['||s[i]=='{'){
           stack[top++]=s[i];
       }
       else{
          if((--top)<0)  return false;
          if(s[i]==')'&&stack[top]!='(')  return false;
          if(s[i]==']'&&stack[top]!='[')  return false;
          if(s[i]=='}'&&stack[top]!='{')  return false;
       }
   }
   return (!top); //防止出现【情况
}

1047.删除字符串中的所有相邻重复项

题目链接：1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

题目描述：给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1. 1 <= S.length <= 20000
2. S 仅由小写英文字母组成。

解法一、栈

char * removeDuplicates(char * s){
    //求出字符串长度
    int strLength = strlen(s);
    //开辟栈空间。栈空间长度应为字符串长度+1（为了存放字符串结束标志'\0'）
    char* stack = (char*)malloc(sizeof(char) * strLength + 1);
    int stackTop = 0;

    int index = 0;
    //遍历整个字符串
    while(index < strLength) {
        //取出当前index对应字母，之后index+1
        char letter = s[index++];
        //若栈中有元素，且栈顶字母等于当前字母（两字母相邻）。将栈顶元素弹出
        if(stackTop > 0 && letter == stack[stackTop - 1])
            stackTop--;
        //否则将字母入栈
        else
            stack[stackTop++] = letter;
    }
    //存放字符串结束标志'\0'
    stack[stackTop] = '\0';
    //返回栈本身作为字符串
    return stack;
}

解法二、双指针

char * removeDuplicates(char * s){
    //创建快慢指针
    int fast = 0;
    int slow = 0;
    //求出字符串长度
    int strLength = strlen(s);
    //遍历字符串
    while(fast < strLength) {
        //将当前slow指向字符改为fast指向字符。fast指针+1
        char letter = s[slow] = s[fast++];
        //若慢指针大于0，且慢指针指向元素等于字符串中前一位元素，删除慢指针指向当前元素
        if(slow > 0 && letter == s[slow - 1])
            slow--;
        else
            slow++;
    }
    //在字符串结束加入字符串结束标志'\0'
    s[slow] = 0;
    return s;
}