目录
题目一：括号匹配问题（来源）
题目描述
题目思路及实现
题目二：用队列实现栈（来源）
题目描述
题目思路及实现
题目三：用栈实现队列（来源）
题目描述
题目思路及实现
题目四：设计循环队列（来源）
题目描述
题目思路及实现
题目一：括号匹配问题（来源）
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
3、每个右括号都有一个对应的相同类型的左括号。
题目思路及实现
该题是栈的典型应用，满足后进先出的规则（后入栈的前括号将优先与先出现的后括号相匹配）。
遍历字符串，遇到前括号直接入栈。遇到后括号，判断该后括号与栈顶的前括号是否匹配（若此时栈为空，则字符串无效），若不匹配则字符串无效；若匹配则删除栈顶元素，继续遍历字符串，直到字符串遍历完毕。当字符串遍历完后，检测栈是否为空，若为空，则字符串有效，若不为空，说明有前括号未匹配，字符串无效。
typedef char STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}Stack;
//初始化栈
void StackInit(Stack* pst)
{
assert(pst);
pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);
pst->top = 0;
pst->capacity = 4;
}
//销毁栈
void StackDestroy(Stack* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
//入栈
void StackPush(Stack* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
pst->a = tmp;
pst->capacity *= 2;
}
pst->a[pst->top] = x;
pst->top++;
}
//检测栈是否为空
bool StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;
}
//出栈
void StackPop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
pst->top--;
}
//获取栈顶元素
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top - 1];
}
/*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/
bool isValid(char * s)
{
// 初始化一个栈st，用于存储遇到的打开的括号
Stack st;
StackInit(&st);
// 创建指向当前字符的指针cur
char* cur = s;
// 遍历输入字符串s中的每个字符
while(*cur)
{
// 如果当前字符是打开的括号
if(*cur == '(' || *cur == '{' || *cur == '[')
{
// 将其压入栈中
StackPush(&st, *cur);
// 移动到下一个字符
cur++;
}
// 否则，如果当前字符是关闭的括号
else
{
// 若栈为空，则说明没有对应的打开括号与之匹配，直接返回false
if(StackEmpty(&st))
{
StackDestroy(&st);
return false;
}
// 获取栈顶元素（即最近进入栈内的打开括号）
char top = StackTop(&st);
// 检查栈顶元素与当前关闭括号是否匹配
if((top == '(' && *cur != ')') ||
(top == '{' && *cur != '}') ||
(top == '[' && *cur != ']'))
{
// 不匹配，则返回false
StackDestroy(&st);
return false;
}
else
{
// 匹配成功，弹出栈顶元素（即消耗一个括号对）
StackPop(&st);
// 移动到下一个字符
cur++;
}
}
}
// 遍历结束后，若栈为空，则说明所有括号都已正确匹配，返回true；否则返回false
bool ret = StackEmpty(&st);
StackDestroy(&st);
return ret;
}此函数利用了栈这一数据结构的特性：对于任何有效的括号序列，当扫描到一个关闭括号时，栈顶的元素一定是与其相匹配的打开括号。遍历完字符串后，栈应为空，表示所有的打开括号都有相应的关闭括号与之匹配。
题目二：用队列实现栈（来源）
题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
题目思路及实现
使用两个队列，始终保持一个队列为空。 当我们需要进行压栈操作时，将数据压入不为空的队列中（若两个都为空，则随便压入一个队列）。当需要进行出栈操作时，将不为空的队列中的数据导入空队列，仅留下一个数据，这时将这个数据返回并且删除即可。判断栈是否为空，即判断两个队列是否同时为空。
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QListNode;
typedef struct Queue
{
QListNode* head;
QListNode* tail;
}Queue;
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QListNode* cur = pq->head;
while (cur)
{
QListNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = NULL;
pq->tail = NULL;
}
//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//检测队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
//队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = NULL;
pq->tail = NULL;
}
else
{
QListNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
//获取队列头部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
//获取队列尾部元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
//获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
QListNode* cur = pq->head;
int count = 0;
while (cur)
{
count++;
cur = cur->next;
}
return count;
}
/*---以上代码是队列的基本功能实现，以下代码是题解主体部分---*/
// 定义一个结构体MyStack，它包含两个队列q1和q2，用以模拟栈的功能
typedef struct
{
Queue q1; // 第一个辅助队列
Queue q2; // 第二个辅助队列
} MyStack;
// 创建并初始化一个MyStack类型的栈对象
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))
{
QueuePush(&obj->q1, x); // 如果q1非空，则将元素压入q1
}
else
{
QueuePush(&obj->q2, x); // 否则将元素压入q2
}
}
// 弹出并返回栈顶元素
int myStackPop(MyStack* obj)
{
Queue* pEmpty = &obj->q1; // 初始化一个指向空队列的指针
Queue* pNoEmpty = &obj->q2; // 初始化一个指向非空队列的指针
// 如果q1非空，则交换两个指针指向的队列
if (!QueueEmpty(&obj->q1))
{
pEmpty = &obj->q2;
pNoEmpty = &obj->q1;
}
// 把非空队列的所有元素依次转移到空队列，保持栈的后进先出性质
while (QueueSize(pNoEmpty) > 1)
{
QueuePush(pEmpty, QueueFront(pNoEmpty)); // 将非空队列的第一个元素移至空队列末尾
QueuePop(pNoEmpty); // 删除非空队列的第一个元素
}
// 获取并返回非空队列的最后一个元素（即栈顶元素）
int front = QueueFront(pNoEmpty);
QueuePop(pNoEmpty); // 删除已获取的栈顶元素
return front;
}
// 返回栈顶元素但不弹出
int myStackTop(MyStack* obj)
{
// 根据队列状态获取栈顶元素
if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1); // 若q1非空，则返回q1最后一个元素（栈顶元素）
}
else
{
return QueueBack(&obj->q2); // 否则返回q2最后一个元素（栈顶元素）
}
}
// 检查栈是否为空
bool myStackEmpty(MyStack* obj)
{
// 若两个队列均为空，则栈为空
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
// 销毁栈并释放内存
void myStackFree(MyStack* obj)
{
QueueDestroy(&obj->q1); // 销毁并释放q1队列资源
QueueDestroy(&obj->q2); // 销毁并释放q2队列资源
free(obj); // 释放栈对象本身占用的内存
}这段代码中，通过两个队列巧妙地实现了栈的功能。其中，压入操作总是把元素添加到非空队列的末尾，而弹出操作时，会先确保所有元素都在同一个队列内，并且按照栈的“后进先出”原则进行操作。
题目三：用栈实现队列（来源）
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
题目思路及实现
使用两个栈，第一个栈只用于数据的输入，第二个栈只用于数据的输出。当需要输出数据，但第二个栈为空时，先将第一个栈中的数据一个一个导入到第二个栈，然后第二个栈再输出数据即可。
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}Stack;
//初始化栈
void StackInit(Stack* pst)
{
assert(pst);
pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);
pst->top = 0;
pst->capacity = 4;
}
//销毁栈
void StackDestroy(Stack* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
//入栈
void StackPush(Stack* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
pst->a = tmp;
pst->capacity *= 2;
}
pst->a[pst->top] = x;
pst->top++;
}
//检测栈是否为空
bool StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;
}
//出栈
void StackPop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
pst->top--;
}
//获取栈顶元素
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top - 1];
}
//获取栈中有效元素个数
int StackSize(Stack* pst)
{
assert(pst);
return pst->top;
}
/*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/
// 定义一个名为MyQueue的结构体，该结构体包含两个栈：pushST（用于插入元素）和popST（用于取出元素），用来模拟队列的功能
typedef struct
{
Stack pushST; // 用于插入元素的栈
Stack popST; // 用于取出元素的栈
} MyQueue;
// 创建并初始化一个MyQueue类型的队列对象
MyQueue* myQueueCreate()
{
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); // 动态分配内存
StackInit(&obj->pushST); // 初始化插入元素的栈
StackInit(&obj->popST); // 初始化取出元素的栈
return obj; // 返回新创建的队列对象
}
// 将整数x推入队列尾部（实际操作是将其压入pushST栈顶）
void myQueuePush(MyQueue* obj, int x)
{
StackPush(&obj->pushST, x); // 将元素x压入pushST栈顶
}
// 查看队列头部元素但不删除
int myQueuePeek(MyQueue* obj)
{
// 如果popST栈为空，则将pushST栈中的所有元素依次弹出并压入popST栈
if(StackEmpty(&obj->popST))
{
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST)); // 将pushST栈顶元素移动到popST栈顶
StackPop(&obj->pushST); // 弹出pushST栈顶元素
}
}
// 返回popST栈顶元素（此时为队列头部元素）
return StackTop(&obj->popST);
}
// 从队列头部弹出并返回元素
int myQueuePop(MyQueue* obj)
{
int top = myQueuePeek(obj); // 获取队列头部元素
StackPop(&obj->popST); // 弹出popST栈顶元素（队列头部元素）
return top; // 返回已弹出的头部元素
}
// 判断队列是否为空
bool myQueueEmpty(MyQueue* obj)
{
// 当插入元素的pushST栈和取出元素的popST栈都为空时，队列为空
return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
// 销毁队列并释放内存
void myQueueFree(MyQueue* obj)
{
StackDestroy(&obj->pushST); // 销毁并释放pushST栈的内存
StackDestroy(&obj->popST); // 销毁并释放popST栈的内存
free(obj); // 释放MyQueue对象本身的内存
}这段代码通过两个栈来模拟队列功能，当插入元素时，将元素压入pushST栈。当需要查看或删除队列头部元素时，首先确保popST栈非空，若为空则将pushST栈中的元素全部转移至popST栈，从而保证popST栈顶元素始终为队列头部元素。这样，通过两个栈的配合，可以实现队列的先进先出（FIFO）特性。
题目四：设计循环队列（来源）
题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
题目思路及实现
在环形队列中，队列为空时，队头队尾指向同一个位置。当队列不为空时，队头指向插入的第一个数据，队尾指向最后一个数据的下一个位置。
当tail+1等于front时，说明环形队列已满。
注意：环形队列的队尾不能像常规队列中队尾一样指向最后一个数据，如果这样的话，我们将不能区别环形队列的状态是空还是满，因为此时队头和队尾都指向同一个位置。这就意味着，我们必须留出一个空间，这个空间不能存放数据，这样我们才能很好的区别环形队列的状态是空还是满。
如果用一个数组来实现这个环形队列的话，上面这三种状态就对应于以下三种状态：
可以看出，此时这个数组和环形完全扯不上关系，这其实很简单，我们只需注意判断两个地方：
1.当指针指向整个数组的后方的时候，让该指针重新指向数组的第一个元素。
2.当指针指向整个数组的前方的时候，让该指针直接指向数组最后一个有效元素的后面。
// 定义一个循环队列结构体MyCircularQueue
typedef struct
{
int* a; // 存储队列元素的数组
int k; // 队列的最大容量
int front; // 队列的头部索引
int tail; // 队列的尾部索引
} MyCircularQueue;
// 创建一个容量为k的循环队列
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int) * (k + 1)); // 为元素数组分配内存，预留一个额外位置便于循环
obj->front = 0; // 初始化头部索引
obj->tail = 0; // 初始化尾部索引
obj->k = k; // 设置队列容量
return obj;
}
// 判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front == obj->tail;
}
// 判断循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
int tailNext = obj->tail + 1; // 计算下一个可能的尾部索引
if (tailNext == obj->k + 1)
{
// 处理索引溢出，实现循环
tailNext = 0;
}
return tailNext == obj->front; // 如果计算后的尾部索引等于头部索引，则队列已满
}
// 往循环队列中入队一个值
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if (myCircularQueueIsFull(obj))
{
return false; // 队列已满，无法入队
}
else
{
obj->a[obj->tail] = value; // 在尾部索引处插入元素
obj->tail++; // 更新尾部索引
if (obj->tail == obj->k + 1)
{
obj->tail = 0; // 处理索引溢出，实现循环
}
return true; // 入队成功
}
}
// 从循环队列中出队一个值
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
{
return false; // 队列为空，无法出队
}
else
{
obj->front++; // 更新头部索引
if (obj->front == obj->k + 1)
{
obj->front = 0; // 处理索引溢出，实现循环
}
return true; // 出队成功
}
}
// 获取循环队列的头部元素
int myCircularQueueFront(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
{
return -1; // 队列为空，无头部元素
}
else
{
return obj->a[obj->front]; // 返回头部索引处的元素
}
}
// 获取循环队列的尾部元素
int myCircularQueueRear(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
{
return -1; // 队列为空，无尾部元素
}
else
{
int tailPrev = obj->tail - 1; // 计算上一个可能的尾部索引
if (tailPrev == -1)
{
// 处理索引负值，实现循环
tailPrev = obj->k;
}
return obj->a[tailPrev]; // 返回尾部索引前一个位置的元素
}
}
// 释放循环队列所占内存
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a); // 释放元素数组内存
free(obj); // 释放MyCircularQueue结构体内存
}
![[渗透测试学习] Monitored-HackTheBox](https://img-blog.csdnimg.cn/direct/77cce085151d4ddc9d40d9e600538743.png)
