目录
一、有效的括号
（1）思路
（2）注意
（3）解题
1.栈的结构
2. 函数主体
二、用队列实现栈
（1）思路
（2）注意
（3）解题
1.队列的结构
2.创建两个队列实现栈
3.初始化
4.入栈
5.出栈
6.取栈顶元素
7.判断栈是否为空
8.销毁栈
三、用栈实现队列
（1）思路
（2）注意
（3）解题
1.栈的结构
2.用两个栈模拟实现队列
3.初始化
4.入队列
5.出队列（注意
6.取队头元素
7.判断队列是否为空
8.队列销毁
四、写在最后
一、有效的括号
（1）思路
创建一个指针遍历字符串，若遍历到的字符为左括号，则入栈；若遍历到的元素为右括号，则取栈顶元素与其进行比较，如果两者匹配，那么栈顶元素出栈，继续比较；如果两者不匹配，则说明字符串无效。
（2）注意
①借助栈来解决这道题；
②栈中插入数据前需要判断空间是否足够，如果不够需要扩容（使用realloc），栈中删除数据时需要判断栈是否为空，如果为空则无法删除。
（3）解题
1.栈的结构
typedef char SDatatype;
typedef struct Stack
{SDatatype* arr;int capacity;int top;
}Stack;
//初始化
void StackInit(Stack* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//栈顶入数据
void StackPush(Stack* ps, SDatatype x)
{assert(ps);//判断空间是否足够!!!!if(ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SDatatype* tmp = (SDatatype*)realloc(ps->arr,sizeof(SDatatype) * newCapacity);//(char*)tmp = (char*)realloc(ps->arr,sizeof(char) * newCapacity);if(tmp == NULL){perror("malloc fail!");}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;
}//判断栈是否为空!!!!
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}//栈顶出数据
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}//取栈顶元素
SDatatype StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效元素的个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}//销毁
void StackDestroy(Stack* ps)
{assert(ps);if(ps->arr != NULL){free(ps->arr);}ps->arr = NULL;ps->capacity = ps->top = 0;
}2. 函数主体
bool isValid(char* s)
{//创建栈Stack st;//初始化StackInit(&st);//定义指针遍历字符串char* pcur = s;while (*pcur != '\0'){//如果是左括号，入栈if ((*pcur == '(') || (*pcur == '[') || (*pcur == '{')){StackPush(&st, *pcur);}else{//如果栈为空，则字符串无效！！！if (StackEmpty(&st)){return false;}//栈不为空才能取栈顶元素else{//判断栈顶元素与所指向的字符是否匹配char top = StackTop(&st);if ((top == '(' && *pcur == ')') || (top == '[' && *pcur == ']') || (top == '{' && *pcur == '}')){//如果匹配则栈头元素出栈StackPop(&st);}else//如果不匹配则为无效字符串{StackDestroy(&st);return false;}}}pcur++;}//如果跳出循环之后，栈为空，说明全部匹配bool ret = StackEmpty(&st);StackDestroy(&st);return ret;
}二、用队列实现栈
（1）思路
使用两个队列模拟栈，原则是必须保证至少有一个队列为空，且栈中的数据遵循先进后出。
①出栈：找到不为空的队列，将其中的size-1个数据导入到空队列中，再让剩余的一个数据出栈；
②入栈：向不为空的队列中插入数据；
③取栈顶元素：找到不为空的队列，取队尾元素。
（2）注意
①入队列时，要申请一个新的结点空间，尾插前需要判断队列是否为空；
②出队列时，首先确保队列不能为空，接着分别处理只有一个结点和其他情况；
③取队头数据和队尾数据之前要确保队列不能为空。
（3）解题
1.队列的结构
//定义队列的结构
typedef int QDatatype;
typedef struct QueueNode
{QDatatype data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//入队列（队尾）
void QueuePush(Queue* pq , QDatatype x)
{assert(pq);//申请新结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if(newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//如果队列为空，直接插入if(pq->phead == NULL){pq->phead = pq->ptail = newnode;}else {pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;//别忘了size++
}//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}//出队列（队头）
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//如果只有一个数据if(pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = 0;}else {QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}--pq->size;
}//取队头数据
QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//销毁
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while(pcur){QueueNode* Next = pq->phead->next;free(pcur);pcur = Next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}
2.创建两个队列实现栈
typedef struct
{Queue q1;Queue q2;
}MyStack;3.初始化
MyStack* myStackCreate()
{MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}4.入栈
void myStackPush(MyStack* obj, int x)
{//向不为空的队列中插入数据if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else {QueuePush(&obj->q2,x);}
}5.出栈
int myStackPop(MyStack* obj)
{//找不为空的队列Queue* empQ = &obj->q1;Queue* noneQ = &obj->q2;if(!QueueEmpty(&obj->q1)){noneQ = &obj->q1;empQ = &obj->q2;}//将不为空的队列中的size-1个数据导入空队列中while(QueueSize(noneQ) > 1){int front = QueueFront(noneQ);QueuePush(empQ,front);QueuePop(noneQ);}//非空队列中只剩下一个数据（要出栈的数据）int pop = QueueFront(noneQ);QueuePop(noneQ);return pop;
}6.取栈顶元素
int myStackTop(MyStack* obj)
{if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else {return QueueBack(&obj->q2);}}7.判断栈是否为空
bool myStackEmpty(MyStack* obj)
{return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}8.销毁栈
void myStackFree(MyStack* obj)
{QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj = NULL;
}三、用栈实现队列
（1）思路
使用两个栈模拟实现队列，一个用于插入数据，另一个用于删除数据。取队头数据时，跟出队列一样，只是不删除数据。
①入队：往pushST中插入数据；
②出队：先判断popST是否为空->如果为空，将pushST中的数据导入到popST中再pop；如果不为空，直接出队列pop；
③取队头元素：步骤跟出队列一样，只是仅仅取数据而不删除数据（pop）。
（2）注意
入队列的步骤。
（3）解题
1.栈的结构
typedef int StackDatatype;
typedef struct Stack
{StackDatatype* arr;int capacity;int top;
}Stack;//初始化
void StackInit(Stack* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//销毁
void StackDestroy(Stack* ps)
{assert(ps);if(ps->arr != NULL){free(ps->arr);}ps->arr = NULL;ps->capacity = ps->top = 0;
}//入栈（栈顶）
void StackPush(Stack* ps,StackDatatype x)
{assert(ps);//判断空间是否充足if(ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2*ps->capacity;StackDatatype* tmp = (StackDatatype*)realloc(ps->arr, sizeof(StackDatatype)*newCapacity);if(tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;//记得更改capacity}ps->arr[ps->top++] = x;
}//判断栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}//出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}//取栈顶元素
StackDatatype StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top-1];
}//栈中有效元素的个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}2.用两个栈模拟实现队列
typedef struct
{Stack pushST;Stack popST;} MyQueue;3.初始化
MyQueue* myQueueCreate()
{MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&pst->pushST);StackInit(&pst->popST);return pst;
}4.入队列
void myQueuePush(MyQueue* obj, int x)
{StackPush(&obj->pushST,x);
}5.出队列
//1.检查popST是否为空
//（1）若不为空，直接出
//（2）若为空，pushST导入到popST，再出数据int myQueuePop(MyQueue* obj)
{if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}//取栈顶，删除栈顶元素并返回栈顶数据int top = StackTop(&obj->popST);StackPop(&obj->popST);return top;
}6.取队头元素
int myQueuePeek(MyQueue* obj)
{if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}return StackTop(&obj->popST);}7.判断队列是否为空
bool myQueueEmpty(MyQueue* obj)
{return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}8.队列销毁
void myQueueFree(MyQueue* obj)
{StackDestroy(&obj->pushST);StackDestroy(&obj->popST);free(obj);obj = NULL;
}四、写在最后
是不是“有点意思”？
敬请期待“二叉树‘~
