数据结构 栈和队列 力扣例题AC——代码以及思路记录

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

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

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被free，ptail此时和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再返回。说实话栈实现队列更容易一些，到这里逻辑比队列实现栈清楚许多了