栈和队列题目详解
前言：
在前面我们学习了栈和队列，栈的特性是后进先出，队列的特性是先进先出，当我们了解了这些之后，我们就可以用到栈和队列的特性来简单的做一些题目了。
1. 有效的括号
有效的括号：. - 力扣（LeetCode）
思路：这个题目我们就可以很好的利用栈的特性来进行解决，我们让左括号入栈，如果我们读取过程中，遇到了右括号，我们就将栈顶的左括号拿出来与它进行匹配，这里会出现两种情况：
情况1：我们在遇到右括号的时候，发现栈为空，此时说明配对失败了。
情况2：当我们遍历完字符串了之后，发现栈不为空，那么此时说明左右括号的数量不匹配，此时也说明失败了。
代码：
typedef char STDataType;
typedef struct Stack
{
STDataType* arr;
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->arr = NULL;
pst->top = pst->capacity = 0;
}
void STDestroy(st* pst)
{
assert(pst);
free(pst->arr);
pst->arr = NULL;
pst->capacity = pst->top = 0;
}
void STPush(st* pst, STDataType x)
{
assert(pst);
if (pst->capacity == pst->top)
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
STDataType* tmp = (STDataType*)realloc(pst->arr, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc");
return;
}
pst->arr = tmp;
pst->capacity = newcapacity;
}
pst->arr[pst->top++] = x;
}
void STPop(st* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
STDataType STTop(st* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->arr[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 pst;
STInit(&pst);
while(*s)
{
//左扩号进栈
if(*s == '('||*s == '[' || *s == '{')
{
STPush(&pst,*s);
}
else
{
//如果左括号没有入栈，那么栈是空的，就不能和之后的右括号进行匹配
if(STEmpty(&pst))
{
return false;
}
//创建字符类型接收栈顶元素
char tmp = STTop(&pst);
//出栈
STPop(&pst);
//这里有一对匹配不合格直接返回false
if(tmp == '(' && *s != ')' ||
tmp == '[' && *s != ']' ||
tmp == '{' && *s != '}')
return false;
}
//让s往后走
s++;
}
//如果s走完了，但是栈内还有元素，就说明匹配不成功
if(!STEmpty(&pst))
{
return false;
}
else
{
return true;
}
}2. 用队列实现栈
用队列实现栈：. - 力扣（LeetCode）
思路：我们知道栈的特性是后进先出，队列是先进先出，我们如何使用两个队列来实现一个栈，其实，我们可以一个队列用来存数据，一个队列为空队列，我们在之后的入数据入到不为空的队列，如果要出数据，我们就可以将不为空的队列的前size-1个数据入到空队列里面，不为空的队列最后剩下的一个数据就栈的栈顶元素。
代码：
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//初始化队列
void QInit(Queue* qp);
//入队 出队
void QPush(Queue* qp, QDataType x);
void QPop(Queue* qp);
//获取队首,队尾数据
QDataType QFront(Queue* qp);
QDataType QBack(Queue* qp);
//获取对内有效数据个数
int QSize(Queue* qp);
//判断队列是否为空
bool QEmpty(Queue* qp);
//销毁队列
void QDestroy(Queue* qp);
void QInit(Queue* qp)
{
assert(qp);
qp->phead = NULL;
qp->ptail = NULL;
qp->size = 0;
}
void QDestroy(Queue* qp)
{
assert(qp);
QNode* cur = qp->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
qp->phead = qp->ptail = NULL;
qp->size = 0;
}
void QPush(Queue* qp, QDataType x)
{
assert(qp);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->data = x;
newnode->next = NULL;
if (qp->phead == NULL)
{
qp->phead = qp->ptail = newnode;
}
else
{
qp->ptail->next = newnode;
qp->ptail = newnode;
}
qp->size++;
}
void QPop(Queue* qp)
{
assert(qp);
assert(qp->size > 0);
if (qp->phead->next == NULL)
{
free(qp->phead);
qp->phead = qp->ptail = NULL;
}
else
{
QNode* next = qp->phead->next;
free(qp->phead);
qp->phead = next;
}
qp->size--;
}
QDataType QFront(Queue* qp)
{
assert(qp);
assert(qp->phead);
return qp->phead->data;
}
QDataType QBack(Queue* qp)
{
assert(qp);
assert(qp->ptail!=NULL);
return qp->ptail->data;
}
int QSize(Queue* qp)
{
assert(qp);
return qp->size;
}
bool QEmpty(Queue* qp)
{
assert(qp);
return qp->size == 0;
}
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
//初始化栈
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
if(pst == NULL)
{
perror("malloc");
exit(1);
}
//初始化两个队列
QInit(&pst->q1);
QInit(&pst->q2);
return pst;
}
void myStackPush(MyStack* obj, int x) {
assert(obj);
//如果q1队列为空，我们就把数据插入到q2
if( QEmpty(&obj->q1))
{
QPush(&obj->q2,x);
}
else//反之插入到q1
{
QPush(&obj->q1,x);
}
}
int myStackPop(MyStack* obj) {
assert(obj);
//假设法
//这里我们们假设q1为空队列，q2为非空队列
Queue* empty = &obj->q1;
Queue* noempty = &obj->q2;
if(QEmpty(&obj->q2))//如果q2为空队列
{
//交换一下
empty = &obj->q2;
noempty = &obj->q1;
}
//将非空队列里面前size-1个数据导入到空队列，此时剩下的数据就是栈顶元素
while(QSize(noempty)>1)
{
QPush(empty,QFront(noempty));
QPop(noempty);
}
//接收非空队列的最后一个数据即栈顶数据
int ret = QFront(noempty);
//删除栈顶数据
QPop(noempty);
return ret;
}
int myStackTop(MyStack* obj) {
assert(obj);
//这里如果q1是空队列，返回q2的队尾
if(QEmpty(&obj->q1))
{
return QBack(&obj->q2);
}
else
{
//反之返回q1的队尾
return QBack(&obj->q1);
}
}
bool myStackEmpty(MyStack* obj) {
assert(obj);
//两个队列同时为空才是空
return QEmpty(&obj->q1)&& QEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
assert(obj);
//释放
QDestroy(&obj->q1);
QDestroy(&obj->q2);
free(obj);
obj = NULL;
}
3. 用栈实现队列
用栈实现队列：. - 力扣（LeetCode）
思路：这里我们如何用两个队列来是实现栈，我们还是可以用一个栈用来入数据，一个栈用来出数据，如果有数据，就都入到入数据的这个栈里面，如果需要出数据，我们先判断出数据的这个栈是否为空，如果为空，我们就把入数据的这个栈里面的数据全部导入到出数据的这个栈里面。
代码：
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
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->arr = NULL;
pst->top = pst->capacity = 0;
}
void STDestroy(st* pst)
{
assert(pst);
free(pst->arr);
pst->arr = NULL;
pst->capacity = pst->top = 0;
}
void STPush(st* pst, STDataType x)
{
assert(pst);
if (pst->capacity == pst->top)
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
STDataType* tmp = (STDataType*)realloc(pst->arr, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc");
return;
}
pst->arr = tmp;
pst->capacity = newcapacity;
}
pst->arr[pst->top++] = x;
}
void STPop(st* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
STDataType STTop(st* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->arr[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* tmp = (MyQueue*)malloc(sizeof(MyQueue));
if(tmp == NULL)
{
perror("malloc");
exit(1);
}
//初始化两个栈
STInit(&tmp->pushst);
STInit(&tmp->popst);
return tmp;
}
void myQueuePush(MyQueue* obj, int x) {
assert(obj);
//我们直接将数据插入到入栈栈里面
STPush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj) {
//这里我们调用一下下面的函数，如果出栈栈为空则把入栈栈的数据都导入到出栈栈里面
//然后接收队列开头元素
int ret = myQueuePeek(obj);
//直接删除出栈栈的栈顶元素
STPop(&obj->popst);
return ret;
}
int myQueuePeek(MyQueue* obj) {
assert(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) {
assert(obj);
//两个栈都为空，队列才为空
return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj) {
assert(obj);
//先释放动态申请的两个栈
STDestroy(&obj->pushst);
STDestroy(&obj->popst);
//在释放动态申请的队列
free(obj);
obj = NULL;
}原文地址：https://blog.csdn.net/2301_81291674/article/details/140107876
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！