1.括号匹配问题
（1）题目描述：
点击链接
（2）思路表述：
解题思路：
该题比较简单，是对栈特性很好的应用，具体操作如下：
循环遍历String中的字符，逐个取到每个括号，如果该括号是：
1. 左括号，直接入栈
2. 右括号，与栈顶的左括号进行匹配，如果不匹配直接返回false
否则继续循环
循环结束后，如果栈空则匹配，否则左括号比右括号多肯定不匹配
（3）代码实现：
bool isValid(char * s){
// oj题目给的提示：1 <= s.length <= 104 说明s中一定是有字符串的 不考虑空串或者s为空的情况
int size = strlen(s);
Stack st;
StackInit(&st);
bool isMatch = true;
for(int i = 0; i < size; ++i)
{
// 如果是左括号则入栈
if(('(' == s[i]) || ('[' == s[i]) || ('{' == s[i]))
{
StackPush(&st, s[i]);
}
else
{
// 拿到的是右括号
// 此时: 需要从栈顶获取左括号来检测是否匹配
// 注意：一定要保证栈中有元素才可以获取栈顶元素
if(StackEmpty(&st))
{
//StackDestroy(&st);
//return false;
isMatch = false;
break;
}
char top = StackTop(&st);
if((top == '(' && s[i] == ')') ||
(top == '[' && s[i] == ']') ||
(top == '{' && s[i] == '}'))
{
StackPop(&st);
}
else
{
// 没有匹配
// StackDestroy(&st);
// return false;
isMatch = false;
break;
}
}
}
// 如果完全匹配，则循环结束时，栈一定是空的
// 否则说明：左括号比右括号多
if(!StackEmpty(&st))
{
//StackDestroy(&st);
//return false;
isMatch = false;
}
StackDestroy(&st);
return isMatch;
}
2.用队列实现栈
（1）题目描述：
点击链接
（2）思路表述：
解题思路：
此题可以用两个队列去实现一个栈，每次始终保持一个队列为空，
入栈操作相当于给非空队列进行入队操作
出栈操作相当于非空队列的队尾元素出队，此时需要把非空队列除最后一个元素之外的其余元素入队到空队列，然后出队最后一个队尾元素
（3）代码实现：
typedef struct {
Queue q1;
Queue q2;
} MyStack;
/** Initialize your data structure here. */
MyStack* myStackCreate(int maxSize) {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
//给非空队列进行入队操作
if(QueueEmpty(&obj->q1) != 0)
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
//把非空队列的除最后一个元素之外的剩余元素全部入队空队列
Queue* pEmpty = &obj->q1, *pNonEmpty = &obj->q2;
if(QueueEmpty(&obj->q1) != 0)
{
pEmpty = &obj->q2;
pNonEmpty = &obj->q1;
}
while(QueueSize(pNonEmpty) > 1)
{
QueuePush(pEmpty, QueueFront(pNonEmpty));
QueuePop(pNonEmpty);
}
int top = QueueFront(pNonEmpty);
//队尾元素出队
QueuePop(pNonEmpty);
return top;
}
/** Get the top element. */
int myStackTop(MyStack* obj) {
//获取非空队列的队尾元素
Queue* pEmpty = &obj->q1, *pNonEmpty = &obj->q2;
if(QueueEmpty(&obj->q1) != 0)
{
pEmpty = &obj->q2;
pNonEmpty = &obj->q1;
}
return QueueBack(pNonEmpty);
}
/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
return !(QueueEmpty(&obj->q1) | QueueEmpty(&obj->q2));
}
void myStackFree(MyStack* obj) {
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}
3.用栈实现队列
（1）题目描述：
点击链接
（2）思路表述：
解题思路：
此题可以用两个栈实现，一个栈进行入队操作，另一个栈进行出队操作出队操作： 当出队的栈不为空是，直接进行出栈操作，如果为空，需要把入队的栈元素全部导入到出队的栈，然后再进行出栈操作
1.
2.
3.
文章来源：https://www.toymoban.com/news/detail-751595.html
（3）代码实现：
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);
}
/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->pushST) == 0
&& StackEmpty(&obj->popST) == 0;
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->pushST);
StackDestroy(&obj->popST);
free(obj);
}
好了，今天的分享就到这里了
如果对你有帮助，记得点赞👍+关注哦！
我的主页还有其他文章，欢迎学习指点。关注我，让我们一起学习，一起成长吧！
文章来源地址https://www.toymoban.com/news/detail-751595.html
到了这里，关于【LeetCode】栈和队列OJ题---C语言版的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
