1. 括号匹配问题。OJ链接

step1:思路分析 ：

1.括号匹配，我们首先考虑用栈实现，我们通过符号栈帧的思想知道，求前中后缀表达式的时候用的就是栈帧，操作数栈和符号栈。

2.根据常见的情况 考虑怎么使用栈，首先我们以示例2为例——“（）{} []”，如果我们用栈我们可以先考虑把“（或 {或[ ” 压入栈中  遇到“）或 } 或  】”就停下来 进行匹配，例如本例就是我们将栈中的（和字符串中的）进行匹配，后续相同，即可说明是匹配的。如果是（（{{[[]]}} ) )这样看起来就很复杂，但是其实我们先把（（{{[[压入栈中，又将]]}} ) )与pop出的栈顶元素匹配，此时也是匹配的，所以满足。但如果是{(}){]{这种情况 ，很明显我们现将{（ 压入栈中，然后发现栈顶（与字符串第一个是} 不匹配，即可说明不满足。

step2. 实现代码：

typedef char STDataType;
typedef struct Stack {
	STDataType*a ;
	int capacity;
	int top;
}ST;

void StackInit(ST*ps);

void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);

STDataType StackTop(ST* ps);
//返回栈顶元素
bool StackEmpty(ST* ps);
//判空
int  StackSize(ST* ps);

bool StackEmpty(ST* ps)
{
	assert(ps);

	/*if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return(ps->top == 0);
}

void StackInit(ST* ps)
{
	assert(ps);
	//创建一个节点空间类似顺序表；
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
		
	}
	ps->top = 0;
	ps->capacity = 4;
}
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)

{
	assert(ps);
	if (ps->top == ps->capacity)//判断是否栈满  需要扩容
	{
		STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);
		if (tmp == NULL)
		{
			perror("melloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;

	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

int  StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}


bool isValid(char* s) {
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s=='['||*s=='{'||*s=='(')
        {
            StackPush(&st,*s);
            s++;//字符串后移一个单位
        }
        else
        {
            if(StackEmpty(&st))
            {
                StackDestroy(&st);//防止内存泄漏
                return false;
            }
           //前面已经返回了所以这里并不需要else
                char top = StackTop(&st);
                StackPop(&st);//出栈操作  不能忘取值不代表出栈；
                if((*s==']'&&top !='[')||(*s=='}'&&top !='{')||(*s==')'&&top !='('))
                {
                    StackDestroy(&st);//防止内存泄漏
                    return false ;
                }

                else
                {
                    ++s;
                }
        }
    }
    bool ret =StackEmpty(&st);
    StackDestroy(&st);//防止内存泄漏
    return ret;
}

2. 用队列实现栈。OJ链接

3. 用栈实现队列。OJ链接

4. 设计循环队列。OJ链接