【数据结构】面试OJ题———栈|队列|互相实现|循环队列|括号匹配
目录
1. 有效的括号
给定一个只包括?
'('，')'，'{'，'}'，'['，']'?的字符串?s?，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路：
左右括号匹配，有两个需要考虑的点；
1.括号顺序问题；
2.括号数量问题；
1.括号顺序问题：括号都有对应的左右边，出现这样的 ({)} 就是错误的；只有相应的左括号会有对应的右括号在旁边；
栈：先进后出；一组括号，先比较的是最后输入的左括号；所以栈满足此功能；
队列：先进先出；最先输入的左括号应该是与最后输入的右括号比较，所以队列不满足此功能；
2.括号顺序问题： 即使右括号都满足了左括号，会有残留问题，比如右括号多些，而此时空间已经为空；
我们构建一个栈的基本功能?；【数据结构】——栈|队列（基本功能）-CSDN博客
// 支持动态增长的栈
typedef char STDataType;
typedef struct Stack
{
STDataType* arr;
int top; // 栈顶
int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
assert(ps);
ps->arr = NULL;
ps->capacity = 0;
ps->top = -1; //表示栈顶元素
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
//检查容量
if (ps->top + 1 == ps->capacity) //top表示的是栈顶元素，先++top,再插入的，所以检查+1位置是否可用
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* newnode = (STDataType*)realloc(ps->arr,sizeof(STDataType) * newcapacity);
assert(newnode); //七匹狼式检查是否开辟成功
ps->arr = newnode;
ps->capacity = newcapacity;
}
ps->top++;
ps->arr[ps->top] = data;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top >= 0);
ps->top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top >= 0);
return ps->arr[ps->top];
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
assert(ps);
if (ps->top < 0) //为空
{
return true;
}
else
{
return false;
}
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
ps->capacity = 0;
ps->top = -1;
free(ps->arr);
ps->arr = NULL;
}
当括号字符串 所有左括号都存储进栈中，当遇到右括号就开始逐个和栈顶括号比较；
?这里在于比较时，因为比较后还需要继续比较，所以采取找到不符合的条件跳出循环；
在字符串循环结束后，要检查是否栈为空
bool isValid(char* s) {
Stack ps;
StackInit(&ps);
while(*s)
{
//左括号入栈
if(*s == '(' || *s == '{' || *s == '[')
{
StackPush(&ps,*s);
}
//右括号与栈顶比较
else
{
//检查是否数量匹配,检查栈是否还有元素,为空返回非0
if(StackEmpty(&ps))
{
StackDestroy(&ps);
return false;
}
//左右括号比较,不相等返回fasle
char tmp = StackTop(&ps);
StackPop(&ps); //移除栈顶元素
if((tmp != '(' && *s == ')')
||( tmp != '{' && *s == '}')
|| (tmp != '[' && *s == ']'))
{
StackDestroy(&ps);
return false;
}
}
++s;
}
bool tmp = StackEmpty(&ps);
StackDestroy(&ps);
return tmp;
}2.用队列实现栈?
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop?和?empty）。实现?
MyStack?类：
void push(int x)?将元素 x 压入栈顶。int pop()?移除并返回栈顶元素。int top()?返回栈顶元素。boolean empty()?如果栈是空的，返回?true?；否则，返回?false?。
思路：
?栈是先进后出的结构，而队列是先进先出的；
两个队列，数据存储到队列1中后，按照先进先出的结构，将size(元数个数)-1移动到队列2中，再输出队列1的话，就实现了栈的结构，先进后出；
可以总结为：如果要输入元素，就输入到空队列中
//将元素X压入栈顶
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1)) //为空返回非0，取反
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}如何找到栈顶元素呢，我们可以将不为空的队列中 size(有效元素个数)-1个 数据移动到空队列中，再输出原不为空的队列；
我们采取假设法，找到不为空的队列，假设某一队列为empty，另外一个队列为noempty；然后if条件判断假设；?
//移除并返回栈顶元素
int myStackPop(MyStack* obj) {
//将size-1个元素移动到 另一个空队列中
//假设q1队列为空，q2不为空
Queue* empty = &obj->q1;
Queue* noempty = &obj->q2;
//验证假设
if(!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
noempty = &obj->q1;
}
//将size-1个元素 移动到空队列中
while(QueueSize(noempty)>1)
{
QueuePush(empty,QueueFront(noempty));
QueuePop(noempty);
}
int top = QueueFront(noempty); //此刻该队列仅有需要的数据
QueuePop(noempty);
return top;
}?这两个是这道题较为麻烦的函数，另外的函数需求因为较为简单，我就直接码上讲解；
且这段代码是这道题一半的代码，另外一般就是队列的基本功能实现代码，可以去【数据结构】——栈|队列（基本功能）-CSDN博客获取完整的代码，复制过来即可；
注：这里释放内存是由里往外，因为结构定义了多重?
?
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
//将元素X压入栈顶
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1)) //为空返回非0，取反
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
//移除并返回栈顶元素
int myStackPop(MyStack* obj) {
//将size-1个元素移动到 另一个空队列中
//假设q1队列为空，q2不为空
Queue* empty = &obj->q1;
Queue* noempty = &obj->q2;
//验证假设
if(!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
noempty = &obj->q1;
}
while(QueueSize(noempty)>1)
{
QueuePush(empty,QueueFront(noempty));
QueuePop(noempty);
}
int top = QueueFront(noempty);
QueuePop(noempty);
return top;
}
//返回栈顶元素
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1)) //为空返回非0，取反
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
//如果栈是空，返回true，非空 返回fasle
bool myStackEmpty(MyStack* obj) {
if(QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2)) //表示为空
{
return true;
}
else
return false;
}
void myStackFree(MyStack* 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
思路：
?这道题和题2相似，要实现1先出去，就是先把入栈的元素全部移动到出栈中，就实现了队列的结构；
与之不同的是：这边需要把全部的数据移动到另一个栈；
可以定义两个栈为：
pushst栈：用来数据存放的栈；
popst栈： 用来输出数据的栈；
1.需要获得栈内数据时，先检查popst栈是否为空，如果不为空，返回该栈数据即刻；
2.如果为空，先将pushst栈数据导入到popst栈内，在进行返回popst栈数据?
int myQueuePeek(MyQueue* obj) {
if(!STEmpty(&obj->popst)) //popst栈有数据 直接返回栈顶元素
{
return STTop(&obj->popst);
}
else
{
//先将数据导入到popst栈
while(!STEmpty(&obj->pushst))
{
STPush(&obj->popst,STTop(&obj->pushst));
STPop(&obj->pushst);
}
//返回栈顶元素
return STTop(&obj->popst);
}
}?注：这里和题2一样，注意释放顺序
因为其他功能较为思路明了，解析过程会在代码中解释；?
栈函数接口实现功能代码在【数据结构】——栈|队列（基本功能）-CSDN博客
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
//数据进到pushst栈，
STPush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj) {
int front = myQueuePeek(obj);
STPop(&obj->popst);
return front;
}
int myQueuePeek(MyQueue* obj) {
if(!STEmpty(&obj->popst)) //popst栈有数据 直接返回栈顶元素
{
return STTop(&obj->popst);
}
else
{
//先将数据导入到popst栈
while(!STEmpty(&obj->pushst))
{
STPush(&obj->popst,STTop(&obj->pushst));
STPop(&obj->pushst);
}
//返回栈顶元素
return STTop(&obj->popst);
}
}
bool myQueueEmpty(MyQueue* obj) {
if(STEmpty(&obj->pushst) && STEmpty(&obj->popst))
{
return true;
}
else
return false;
}
void myQueueFree(MyQueue* obj) {
STDestrory(&obj->pushst);
STDestrory(&obj->popst);
free(obj);
}?4.设计循环队列
?设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
思路：
?这里有两种数据结构可以选择：数组和链表；
链表对后续的操作比较方便，但是不好控制，而且构建的时候也极为麻烦；
如果用数组 需要考虑的是如何规避为满和为空的判断
?
采用数组的话，我们定义front，back；来进行判断循环点；
?
这里的问题就是如何规避 为满和为空的问题；?
解决：1.可以定义一个size；在front == back的基础上，size == 0 就是空
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? size ！= 0就是满；
? ? ? ? 2. 可以多开辟一块空间；动态空间；
?
多开辟一块空间，这块空间是动态移动的，但是不存储数据；
当front == back时，就是空；
当 back+1 == front 就是满，
这里因为数组 如果在边界点的话 会导致越界，
所以采取取模来规范范围；也达到了循环的条件
?这里需要注意的就是获取最后一个结点；
因为back是指向最后一个数据的下一个位置；如果back在边界 -1 有可能越界；
需要特殊处理规范这块；
?
取模的操作：如果该数大于本身，就不会有影响；?
这里删除和增加一个数据，都有可能引起越界；所以在对back front操作后，都要规范范围；
取模实际空间大小?
typedef struct {
int* parr; //动态开辟
int front; //头结点
int back; //指向尾结点的下一个
int size; //实际开辟的空间
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->parr = (int*)malloc(sizeof(int)*(k+1)); //多开辟一块空间
obj->front = 0;
obj->back = 0;
obj->size= k+1;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->back;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->back+1) % obj->size == obj->front; //满了返回真
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//先判断是否满了
if(myCircularQueueIsFull(obj)) //满了返回真
return false;
obj->parr[obj->back] = value;
obj->back++;
obj->back %= obj->size;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//判断是否为空
if(myCircularQueueIsEmpty(obj))
return false;
obj->front++;
obj->front %= obj->size;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->parr[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->parr[(obj->back-1 + obj->size) % obj->size];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->parr);
free(obj);
}
?
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！