题目来源：力扣
基础知识
一.栈
1.栈的概念
定义：堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。
压栈：向一个栈插入新元素，又称作进栈、入栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
出栈：从一个栈删除元素又称作退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
特点：先入后出，后入先出。
2.栈的实现
//利用动态数组实现栈
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;//用数组来实现栈
int top;
int capacity;
}ST;
// 初始化和销毁
void STInit(ST* pst)
{
assert(pst);
pst->arr = NULL;
pst->capacity = 0;
pst->top = 0;//top指向栈顶元素的下一位，数组下标从0开始
//top实际指向的是下标，且top == 数据个数
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->arr);
pst->arr = NULL;
pst->capacity = 0;
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);//栈的数据个数大于0
pst->top--;
}
// 取栈顶数据
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);//栈的数据个数大于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 ;
}二.队列
1.队列的概念
定义：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。
队尾：进行插入操作端称为队尾
队头：进行删除操作的端称为队头。
特点：先进先出（FIFO—first in first out）
分类：顺序队列和循环队列
顺序队列：
2.顺序队列的实现
//队列的基本接口
//用单链表实现队列
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
QNode* phead;//队列头节点指针
QNode* ptail;//队列尾节点指针
int size;//数据个数
}Queue;
//初始化 销毁
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* pcur = pq->phead;
while (pcur)
{
QNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->next = NULL;
newnode->val = x;
//队列为空
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
// 队头删除
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size > 0);
//一个节点
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else//多个节点
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
// 取队头和队尾的数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}
//队列数据个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return (pq->size == 0);
}3.循环队列的概念：
定义：在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦tail(尾）指针增1或head（头）指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。
空和满的判别条件：在循环队列中，当队列为空时，有head = tail，而当所有队列空间全占满时，也有head = tail。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是head = tail，而队列判满的条件是head=（tail+1）%MaxSize
题目一.有效的括号（括号匹配问题）
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
-
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}" 输出：true示例 3：
输入：s = "(]" 输出：false
解题方法：
分析：
从字符串s的右边开始看，若左右括号不匹配或者左括号在前，则字符串无效，若匹配，则二者可以消掉，继续重复上述步骤。
左右括号数量一致
核心思想：
后进先出
工具：
栈
思路：（从s的左边开始依次，一个一个读取）
1. 左括号入栈
2.右括号与栈顶的左括号尝试匹配
代码（力扣中的部分代码）（由于栈和队列的接口代码在上文中已经写明，题目代码中就不再赘述）
（题目一至题目三都用到了前面实现的接口函数，题目四没有）
//题目主代码逻辑
bool isValid(char* s)
{
//左括号入栈，右括号出栈
ST st;
STInit(&st);
while(*s)
{
//左括号入栈
if(*s == '('||*s == '['||*s == '{')
{
STPush(&st,*s);
}
else//右括号与栈顶左括号尝试匹配
{
//如果栈为空，且s中的是右括号，则直接返回false
if(STEmpty(&st))
{
STDestroy(&st);
return false;
}
char top = STTop(&st);
//不匹配
if(top=='('&&(*s)!=')'||
top=='['&&(*s)!=']'||
top=='{'&&(*s)!='}')
{
STDestroy(&st);//销毁
return false;
}
//匹配，栈顶的左括号出栈
STPop(&st);
}
s++;
}
//如果栈为空，说明左括号和右括号数量匹配
//反之，数量不匹配
bool ret = STEmpty(&st);
STDestroy(&st);
return ret;
}
题目二.用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
分析：
压栈：将数据依次插入第一个队列
出栈：将尾数据之前的所有数据导入到第二个队列中（队列之间导入数据可以保证数据的顺序不变），留下的尾数据就是要出栈的栈顶元素
判空：如果两个队列都为空则栈为空
要点：
1.一个队列始终往不为空，用于进行压栈操作
2.另一个队列在每一次操作之后，一直保持为空，用于导入数据，实现出栈
解题代码
//题目代码主逻辑
typedef struct
{
Queue que1;
Queue que2;
} MyStack;
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->que1);
QueueInit(&pst->que2);
return pst;
}
void myStackPush(MyStack* obj, int x)
{
//往非空队列插入数据
if(!QueueEmpty(&obj->que1))
{
QueuePush(&obj->que1,x);
}
else
{
QueuePush(&obj->que2,x);
}
}
int myStackPop(MyStack* obj)
{
//判断哪个队列为空
//假设法
Queue* empty = &obj->que1;
Queue* noempty = &obj->que2;
if(!QueueEmpty(&obj->que1))
{
empty = &obj->que2;
noempty = &obj->que1;
}
//非空队列的前size-1个数据导到空队列中
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->que1))
{
return QueueBack(&obj->que1);
}
else
{
return QueueBack(&obj->que2);
}
}
bool myStackEmpty(MyStack* obj)
{
return (QueueEmpty(&obj->que1))&&(QueueEmpty(&obj->que2));
}
void myStackFree(MyStack* obj)
{
//先释放每个队列，在释放栈
QueueDestroy(&obj->que1);
QueueDestroy(&obj->que2);
free(obj);
obj = NULL;
}
题目三.用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
分析：
方法一
和前面用队列实现栈大致相同，一个栈始终不为空，用于插入数据，另一个栈在每一次操作之后，一直保持为空，用于数据的转移，实现出队列的操作
不同的是，每一次Pop操作要进行两次数据的转移
方法二
设计两个栈，一个叫pushst，只用来插入数据，另一个叫popst，只用来删除数据，当popst为空时，将pushst中的所有数据导入到popst中。
方法一：
typedef struct
{
ST st1;
ST st2;
} MyQueue;
MyQueue* myQueueCreate()
{
MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&pq->st1);
STInit(&pq->st2);
return pq;
}
void myQueuePush(MyQueue* obj, int x)
{
//往非空栈中存数据
if(!STEmpty(&obj->st1))
{
STPush(&obj->st1,x);
}
else
{
STPush(&obj->st2,x);
}
}
int myQueuePop(MyQueue* obj)
{
//把非空栈中后size-1个数据挪到空栈中
ST* empty = &obj->st1;
ST* noempty = &obj->st2;
if(STEmpty(&obj->st2))
{
ST* empty = &obj->st2;
ST* noempty = &obj->st1;
}
while(noempty->top>1)
{
STPush(empty,STTop(noempty));
STPop(noempty);
}
int top = STTop(noempty);
STPop(noempty);
//再把数据导回去
while(empty->top)
{
STPush(noempty,STTop(empty));
STPop(empty);
}
return top;
}
int myQueuePeek(MyQueue* obj)
{
if(!STEmpty(&obj->st1))
{
return obj->st1.arr[0];
}
else
{
return obj->st2.arr[0];
}
}
bool myQueueEmpty(MyQueue* obj)
{
return (STEmpty(&obj->st1)&&STEmpty(&obj->st2));
}
void myQueueFree(MyQueue* obj)
{
STDestroy(&obj->st1);
STDestroy(&obj->st2);
free(obj);
obj = NULL;
}
方法二.
typedef struct
{
ST pushst;//插入数据
ST popst; //删除数据
} MyQueue;
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)
{
//myQueuePop和 myQueuePeek的整体逻辑是大致相似的，只是多了一步删除，可以直接调用
int top = myQueuePeek(obj);
STPop(&obj->popst);
return top;
}
int myQueuePeek(MyQueue* obj)
{
//如果popst为空
if(STEmpty(&obj->popst))
{
//将pushst中的所有数据导入到popst中
while(!STEmpty(&obj->pushst))
{
STPush(&obj->popst,STTop(&obj->pushst));
STPop(&obj->pushst);
}
}
//popst为空和不为空，最终要返回的都是popst中的栈顶元素
return STTop(&obj->popst);
}
bool myQueueEmpty(MyQueue* obj)
{
return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj)
{
STDestroy(&obj->pushst);
STDestroy(&obj->popst);
free(obj);
obj = NULL;
}
题目四.设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
代码：
typedef struct
{
int* arr;//动态数据实现循环队列
int head;//指向队头
int tail;//指向队尾数据的下一个
int k;//k表示最多可存数据的个数,即队列长度,等于 MaxSize - 1
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//多开一个空间解决空和满冲突的问题
pq->arr = (int*)malloc(sizeof(int)*(k+1));
pq->head = pq->tail = 0;
pq->k = k;
return pq;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->head == obj->tail;//head == tail
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return (obj->tail+1)%(obj->k+1) == obj->head;//head=（tail+1）%MaxSize
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->arr[obj->tail++] = value;
}
//若tail超出了所分配的队列空间，即走到了数组下标为k+1的位置，则要回到起点
//可以让tail%(k+1),若tail<k+1,则不变,若等于,则tail刚好为0
obj->tail %= obj->k+1;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
obj->head++;
obj->head %= obj->k+1;
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->arr[obj->head];
}
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
//情况一.tail位于起点，此时队尾在下标为k的地方
//情况二.tail不在起点，队尾==tail-1
//写法一.
return obj->tail == 0?obj->arr[obj->k]:obj->arr[obj->tail-1];
//写法二.
//return obj->arr[(obj->tail - 1 + obj->k + 1)%(obj->k + 1)];
//假设k == 4
//若 tail == 0,则 (0-1+5)%5 == 4,恰好 == k
//若 tail != 0,则 (k+1)%(k+1) == 0,二者相互抵消
}
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->arr);
obj->arr = NULL;
obj->head = obj->tail = 0 ;
free(obj);
obj = NULL;
}
