1.括号匹配问题
题解：栈 2.用队列实现栈结构
题解：两个队列实现 3.用栈实现队列结构
题解：两个栈实现
1.括号匹配问题给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
题目链接: 力扣20. 有效的括号.
题解：栈借助栈的数据结构特性，我们可以遍历给定的括号数组：当遇到左括号时数组元素入栈，当遇到一个右括号时，栈内的栈顶元素出栈，并进行比较，若不能与之相互匹配为左右括号，则该括号数组不成立；反之再进一步判断，直至括号数组遍历完毕，这时若栈内仍有元素（左括号）尚未匹配出栈，说明括号数组左右括号数量不匹配，仍不满足要求。
//用栈结构实现括号判断问题
//动态开辟顺序表结构作为栈的结构
typedef struct stack
{
char* array;
int capacity; //空间总大小
int top; //栈顶（存放结点个数）
}Stack;
//检测空间是否已满
void CheckCapacity(Stack* ps)
{
assert(ps);
int newCapacity = 2 * ps->capacity;
if (ps->top == ps->capacity)
{
//1.申请新空间
char* newArray = (char*)malloc(sizeof(char) * newCapacity);
if (NULL == newArray)
{
printf("空间扩容失败!n");
return;
}
//2.拷贝原空间至新空间
memcpy(newArray, ps->array, ps->top * sizeof(char));
//3.释放原空间
free(ps->array);
ps->array = newArray;
ps->capacity = newCapacity;
}
}
//初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->array = (char*)malloc(sizeof(char)*3); //默认开辟3个结点
if(NULL == ps->array) //检测堆上是否成功开辟空间
{
assert(0);
return;
}
ps->capacity = 3;
ps->top = 0;
}
//销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
if(ps->array)
{
free(ps->array); //顺序结构连续空间 一次性释放
ps->array++;
ps->capacity = 0;
ps->top = 0;
}
}
//入栈（尾插）
void StackPush(Stack* ps,char a)
{
assert(ps);
//先判断栈空间是否满了
CheckCapacity(ps);
ps->array[ps->top] = a;
ps->top++;
}
//出栈（头删）
void StackPop(Stack* ps)
{
assert(ps);
if(ps->top == 0)
{
printf("栈为空！n");
}
ps->top--;
}
//返回栈顶元素
char StackTop(Stack* ps)
{
assert(ps);
//1.检测栈是否为空
if (ps->top == 0)
{
printf("获取错误！栈为空n");
return -1;
}
//2.返回数组最后一位元素
return ps->array[ps->top - 1];
}
bool isValid(char * s)
{
bool flag = true;
Stack st;
StackInit(&st);
while(*s)
{
if(*s == '[' || *s == '(' || *s == '{')
{
StackPush(&st,*s);
s++;
}
else
{
if(st.top == 0) //栈为空
{
flag = false;
break;
}
char ch = StackTop(&st);
StackPop(&st);
if((*s == ']' && ch != '[')
|| (*s == '}' && ch != '{')
|| (*s == ')' && ch != '('))
{
flag = false;
break;
}
else
{
s++;
}
}
}
if(flag == true)
{
if(st.top != 0)
{
flag = false;
}
}
StackDestroy(&st);
return flag;
}
2.用队列实现栈结构
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种 *** 作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false
题目链接: 力扣225. 用队列实现栈.
题解：两个队列实现//两队列实现栈结构
//用队列模拟栈结构，那么结点应该用队列的结点结构
//队列是前出后进 也就是头删尾插
//头删更适合链表结构
// 定义单链表结点
typedef struct QNode
{
int data;
struct QNode* next;
}QNode;
// 定义队列结构体
typedef struct Queue
{
QNode* front; //指向队头结点 队头：出队
QNode* rear; //指向队尾结点 队尾：入队
int size; //队列元素个数
}Queue;
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
// 检测队列是否为空
int QueueEmpty(Queue* q)
{
assert(q);
return 0 == q->size;
}
// 创建队列结点
QNode* buyQNode(int data)
{
QNode* newQNode = (QNode*)malloc(sizeof(QNode));
if (NULL == newQNode)
{
assert(0);
return NULL;
}
newQNode->data = data;
newQNode->next = NULL;
return newQNode;
}
// 入队列 尾插
void QueuePush(Queue* q, int data)
{
assert(q);
QNode* newQNode = buyQNode(data);
//1.队列为空
if (QueueEmpty(q))
{
q->front = newQNode;
}
else
{
//2.队列已有元素
q->rear->next = newQNode;
}
//3.调整队列其余元素
q->rear = newQNode;
q->size++;
return;
}
// 出队列 头删
int QueuePop(Queue* q)
{
assert(q);
//1.队列为空
if (QueueEmpty(q))
{
assert(0);
return -1;
}
else
{
//2.队列已有元素
QNode* delNode = q->front;
int delData = delNode->data;
q->front = q->front->next;
q->size--;
free(delNode);
if (NULL == q->front)
{
q->rear = NULL;
}
return delData;
}
}
// 获取队尾元素
int QueueBack(Queue* q)
{
//队列为空情况设为违法
assert(!QueueEmpty(q));
return q->rear->data;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->front;
while (cur)
{
q->front = cur->next;
free(cur);
cur = q->front;
}
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
//------------------------------------------------------------------------------
//定义栈结构--由两个队列构成
typedef struct
{
Queue Q1;
Queue Q2;
} MyStack;
//创建栈
MyStack* myStackCreate()
{
MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); //在堆上开辟栈结构
if (NULL == obj)
{
assert(0);
return NULL;
}
QueueInit(&(obj->Q1)); //初始化队列1
QueueInit(&(obj->Q2)); //初始化队列2
return obj;
}
//入栈
//哪个队列不为空，存进那个队
void myStackPush(MyStack* obj, int x)
{
if (QueueEmpty(&(obj->Q1)))
{
QueuePush(&(obj->Q2),x);
}
else
{
QueuePush(&(obj->Q1), x);
}
}
//出栈
//将不为空队列的前n-1个结点转到另一个队列
//在将该队列最后一个结点出队即可
int myStackPop(MyStack* obj)
{
if (QueueEmpty(&(obj->Q1)))
{
while (obj->Q2.size > 1)
{
QueuePush(&(obj->Q1), QueuePop(&(obj->Q2)));
}
return QueuePop(&(obj->Q2));
}
while (obj->Q1.size > 1)
{
QueuePush(&(obj->Q2), QueuePop(&(obj->Q1)));
}
return QueuePop(&(obj->Q1));
}
//返回栈顶元素
//将不为空的队列的队尾元素返回即可
int myStackTop(MyStack* obj)
{
if (QueueEmpty(&(obj->Q1)))
{
return QueueBack(&(obj->Q2));
}
else
{
return QueueBack(&(obj->Q1));
}
}
//判断是否空栈
//判断两个队列是否为空
bool myStackEmpty(MyStack* obj)
{
if (QueueEmpty(&(obj->Q1)) && QueueEmpty(&(obj->Q2)))
{
return true;
}
return false;
}
//释放栈
//先销毁栈的两个队列，再销毁栈结构
void myStackFree(MyStack* obj)
{
assert(obj);
QueueDestroy(&(obj->Q1));
QueueDestroy(&(obj->Q2));
free(obj);
}
3.用栈实现队列结构
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有 *** 作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
题目链接: 力扣232. 用栈实现队列.
题解：两个栈实现//用两栈实现队列结构
//栈结构只从尾部出入 因此采用顺序表结构
//采用动态开辟顺序表结构
typedef struct Stack
{
int* array;
int capacity; //空间总大小
int size; //储存实际大小
}Stack;
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->array = (int*)malloc(sizeof(int) * 3); //初始化默认开辟三个单位
if (NULL == ps->array)
{
assert(0);
return;
}
ps->capacity = 3;
ps->size = 0;
}
// 检测空间是否已满
static void CheckCapacity(Stack* ps)
{
assert(ps);
int newCapacity = 2 * ps->capacity;
if (ps->size == ps->capacity)
{
//1.申请新空间
int* newArray = (int*)malloc(sizeof(int) * newCapacity);
if (NULL == newArray)
{
assert(0);
return;
}
//2.拷贝原空间至新空间
memcpy(newArray, ps->array, ps->size * sizeof(int));
//3.释放原空间
free(ps->array);
ps->array = newArray;
ps->capacity = newCapacity;
}
}
// 入栈 （尾插）
void StackPush(Stack* ps, int data)
{
assert(ps);
//1.判断栈空间
CheckCapacity(ps);
//2.直接插入
ps->array[ps->size] = data;
ps->size++;
}
// 检测栈是否为空
int StackEmpty(Stack* ps)
{
assert(ps);
return 0 == ps->size;
}
// 出栈 （尾删）
int StackPop(Stack* ps)
{
assert(ps);
//1.检测栈是否为空
if (StackEmpty(ps))
{
printf("删除错误！栈为空n");
return -1;
}
//2.保存删除的值
int delData = ps->array[ps->size - 1];
//3.直接减值
ps->size--;
return delData;
}
// 获取栈顶元素
int StackTop(Stack* ps)
{
assert(ps);
//1.检测栈是否为空
if (StackEmpty(ps))
{
printf("获取错误！栈为空n");
return -1;
}
//2.返回数组最后一位元素
return ps->array[ps->size - 1];
}
//销毁链表
void StackDestroy(Stack* ps)
{
assert(ps);
if (ps->array)
{
free(ps->array);
ps->array = NULL;
ps->capacity = 0;
ps->size = 0;
}
}
//-------------------------------------------------------------------------------
//定义队列结构--两个栈构成
typedef struct
{
Stack S1; //令S1为入队栈
Stack S2; //令S2为出队栈
} MyQueue;
//初始化队列
MyQueue* myQueueCreate()
{
//先在堆上开辟队列空间
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
if (NULL == obj)
{
assert(0);
return NULL;
}
//初始化队列里的栈空间
StackInit(&(obj->S1));
StackInit(&(obj->S2));
return obj;
}
//入队
//直接将数据存入栈S1中
void myQueuePush(MyQueue* obj, int x)
{
assert(obj);
StackPush((&(obj->S1)), x);
}
//出队
//将栈S2的栈顶出栈
//若S2没有数据，则先将栈S1的所有数据转入栈S2中
int myQueuePop(MyQueue* obj)
{
if (StackEmpty(&(obj->S2))) //栈S2为空
{
while (obj->S1.size)
{
StackPush(&(obj->S2), StackPop(&(obj->S1)));
}
}
return StackPop(&(obj->S2));
}
//返回队列开头的元素
//返回栈S2的栈顶元素
//若S2没有数据，则先将栈S1的所有数据转入栈S2中
int myQueuePeek(MyQueue* obj)
{
assert(obj);
if (StackEmpty(&(obj->S2))) //栈S2为空
{
while (obj->S1.size)
{
StackPush(&(obj->S2), StackPop(&(obj->S1)));
}
}
return StackTop(&(obj->S2));
}
//判断队列是否为空
//直接判断两个栈是否为空即可
bool myQueueEmpty(MyQueue* obj)
{
assert(obj);
if (StackEmpty(&(obj->S1)) && StackEmpty(&(obj->S2)))
{
return true;
}
return false;
}
void myQueueFree(MyQueue* obj)
{
assert(obj);
StackDestroy(&(obj->S1));
StackDestroy(&(obj->S2));
free(obj);
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）