目录
一. 225. 用队列实现栈
题目链接：
题目：用队列实现栈
解题思路：
完整代码实现：
二.622. 设计循环队列
题目链接：
题目：
解题思路：
完整代码实现：
一. 225. 用队列实现栈 题目链接：
225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)
题目：用队列实现栈请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种 *** 作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本 *** 作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些 *** 作。
你所使用的语言也许不支持队列。
你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列 *** 作即可。
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
提示：
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空
前提是先有各种队列函数供使用！
0.先创建一个结构体 MyStack (这个结构体变量就是我们创建的“栈”)，“栈”中包含q1，q2两个队列，核心思想是：q1，q2中保持一个队列存储数据，另外一个队列空着；要出栈时，空队列用来倒数据，下面有出栈示意图(因为 队列是先进先出，栈是先进后出，所以主要是出栈需要改造)
typedef struct {
Queue q1;
Queue q2;
} MyStack;
出栈示意图：假设开始q1中有1,2,5三个值，q2为空队列 ; 最终q1前N-1个数据给q2，最后一个数据删掉，实现了栈的后进先出(或者先进后出)
逐个分析“栈”对应功能的函数：
1.创建栈：先开辟一块 MyStack 类型的空间并赋值给 指针pst，同时断言检查是否为NULL，再把此空间中的两个队列变量q1和q2都用队列初始化函数进行初始化，并返回这个地址pst
MyStack* myStackCreate() {
MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
assert(pst);
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}2.入栈： q1和q2一个是空的队列，一个是存数据的队列，方便后面出栈，通过 QueuePush 队列插入函数(相当于单链表尾插) 将数据给到不为空的队列中，因为刚开始都是空队列，所以给q1或q2都行，当其中一个为非空队列时，再次尾插就会尾插到这个非空队列中
void myStackPush(MyStack* obj, int x) {
assert(obj);
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
3.出栈：把不为空的队列的数据前N-1导入另一个空队列,最后剩下的一个删掉。
前面先找出空队列 emptyQ 和非空队列 nonEmptyQ ，讲空队列的前N-1个数据导入另一个空队列,最后剩下的一个删掉。
int myStackPop(MyStack* obj) {
assert(obj);
Queue* emptyQ=&obj->q1;
Queue* nonEmptyQ=&obj->q2;
if(!QueueEmpty(&obj->q1))
{
emptyQ=&obj->q2;
nonEmptyQ=&obj->q1;
}
while(QueueSize(nonEmptyQ)>1)
{
QDataType front=QueueFront(nonEmptyQ);
QueuePush(emptyQ,front);
QueuePop(nonEmptyQ);
}
QDataType top=QueueFront(nonEmptyQ);
QueuePop(nonEmptyQ);
return top;
} 4.找"栈"的栈顶：即最后一个结点的值，哪个队列不为空，就返回哪个队列的末尾节点的值。
int myStackTop(MyStack* obj) {
assert(obj);
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}5.判断“栈”是否为空：只要q1和q2两个队列全为空队列就返回true
bool myStackEmpty(MyStack* obj) {
assert(obj);
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}6.释放“栈”：销毁q1，q2两个队列，并free“栈”的地址空间即可
void myStackFree(MyStack* obj) {
assert(obj);
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
size_t QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
void QueueDestory(Queue* pq) //复盘！！！
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head =pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->next = NULL;
newnode->data = x;
if (pq->tail == NULL)
{
assert(pq->head==NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode; //写的时候漏了！！！
}
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
if (pq->head == pq->tail)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
//return pq->head == NULL && pq->tail == NULL;
return pq->head == NULL;
}
size_t QueueSize(Queue* pq)
{
assert(pq);
size_t size = 0;
QNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
//——————————————————————————————————————————————————————以上是队列的 *** 作
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
assert(pst);
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
void myStackPush(MyStack* obj, int x) {
assert(obj);
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
assert(obj);
Queue* emptyQ=&obj->q1;
Queue* nonEmptyQ=&obj->q2;
if(!QueueEmpty(&obj->q1))
{
emptyQ=&obj->q2;
nonEmptyQ=&obj->q1;
}
while(QueueSize(nonEmptyQ)>1)
{
QDataType front=QueueFront(nonEmptyQ);
QueuePush(emptyQ,front);
QueuePop(nonEmptyQ);
}
QDataType top=QueueFront(nonEmptyQ);
QueuePop(nonEmptyQ);
// if(!QueueEmpty(&obj->q2))
// printf("1111111");
// if(!QueueEmpty(&obj->q2))
// printf("2222222");
return top;
}
int myStackTop(MyStack* obj) {
assert(obj);
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
assert(obj);
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
assert(obj);
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}
请你仅使用两个栈实现先入先出队列。
队列应当支持一般队列支持的所有 *** 作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈 *** 作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty *** 作是合法的。
你所使用的语言也许不支持栈。
你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈 *** 作即可。
示例 1：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有 *** 作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek *** 作）
前提是先有各种 栈函数 供使用！
0.这是第一题的兄弟题，跟上面 *** 作差不多，唯一不同是不用来回倒数据(下面核心思想讲)，这里也是先创建一个结构体 MyQueue (这个结构体变量就是我们创建的“队列”)，“队列”中包含 pushST ，popST两个队列，核心思想是：因为 队列是先进先出，栈是先进后出，所以肯定主要还是改造 "出队列" ，给pushST插入数据(比如插入四个数据1,2,3,4)，要想实现出队列把 "1" 删掉，就先把pushST所有数据 出栈 到popST中，此时popST中数据是“4,3,2,1”，再出栈就可以删除1 达到出队列删除1的目的。
如果一直出队列，删除1->删除2->删除3->删除4,删完了，只要pushST中还有数据，就依旧把pushST中的数据出栈到popST中(比如pushST中)
typedef struct {
ST pushST;
ST popST;
} MyQueue;
1.创建“队列”函数：malloc一块MyQueue的空间obj (这个结构体变量就是我们创建的“队列”)，初始化其中的两个栈，并返回这个“队列”的地址。
MyQueue* myQueueCreate() {
MyQueue* obj=( MyQueue*)malloc(sizeof( MyQueue));
assert(obj);
StackInit(&obj->pushST);
StackInit(&obj->popST);
return obj;
}2.“队列”插入函数：就直接往pushST中插入就行了
void myQueuePush(MyQueue* obj, int x) {
assert(obj);
StackPush(&obj->pushST, x);
}3.
完整代码实现：typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
STDataType StackTop(ST* ps);
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//入栈 复盘
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = (STDataType*)realloc(ps->a,sizeof(STDataType)*newcapacity);
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps) //StackTop+StackPop => 出栈
{
assert(ps);
assert(ps->top>0);
--ps->top;
}
bool StackEmpty(ST* ps)
{
assert(ps);
//if (ps->top > 0)
// return false;
//else
// return true;
return ps->top == 0;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
//————————————————————————————————————————————————————————————————以上是栈 *** 作
typedef struct {
ST pushST;
ST popST;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj=( MyQueue*)malloc(sizeof( MyQueue));
assert(obj);
StackInit(&obj->pushST);
StackInit(&obj->popST);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
assert(obj);
StackPush(&obj->pushST, x);
}
int myQueuePop(MyQueue* obj) {
assert(obj);
if(StackEmpty(&obj->popST))
{
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
int front =StackTop(&obj->popST);
StackPop(&obj->popST);
return front;
}
int myQueuePeek(MyQueue* obj) {
assert(obj);
if(StackEmpty(&obj->popST))
{
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
return StackTop(&obj->popST);
}
bool myQueueEmpty(MyQueue* obj) {
assert(obj);
return StackEmpty(&obj->pushST)&& StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj) {
assert(obj);
StackDestory(&obj->pushST);
StackDestory(&obj->popST);
free(obj);
}622. 设计循环队列 - 力扣（LeetCode） (leetcode-cn.com)
题目：设计你的循环队列实现。
循环队列是一种线性数据结构，其 *** 作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。
它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。
在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。
但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下 *** 作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。
如果队列为空，返回 -1 。
Rear: 获取队尾元素。
如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。
如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。
如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
0. 次循环队列有数组和单链表两个底层结构，该选哪一个呢？
答：选数组较好。
实际上两者各有优劣，其实都差不多，
选数组的原因：
数组的优点：(也是单链表的缺点) 因为tail只能指向末尾数据的下一个地址，如果要找尾结点数据时，单链表找tail的上一个节点很费劲，数组就只需要tail-1就能找到。
数组的缺点：(也是单链表的优点) 如果是数组结构，当tail到最后一个节点时，为了成为循环队列结构，需要手动让tail=0，单链表就不用手动赋值。
0.0 创建结构体 MyCircularQueue ，包含数组队列int* a，整形front代表队列头部的角标，tail代表队列尾部的角标，k代表能存几个数据
typedef struct {
int* a;
int front;
int tail;
int k;
} MyCircularQueue;接下来逐一分析我们创建的循环队列对应的各个函数：
1.创建循环队列函数：开辟一个循环队列的结构体的空间，地址名叫obj，通过下面动态图①发现：最开始front=tail=0，每增加一个数据，tail++，当增加k个(假设k=4)数据时，tail又不得不回到角标0处，此时front=tail=0，这样空列表和慢列表无法区分，(图②)为了避免空和满混淆，多开一个空间，front == tail时是空，tail的下一个位置是front就是满
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->front=obj->tail=0;
obj->k=k;
return obj;
}图①
图②
2.入“队列”函数：“队列”结构体：
typedef struct {
int* a;
int front;
int tail;
int k;
} MyCircularQueue;
通常是将value赋给数组队列的最后一个值，然后tail++即可，但是也应考虑 满队列 和 tail走到头（obj->tail=k）两种情况：满队列应提前用 myCircularQueueIsFull(obj) 判断队列是否满的函数，如果是true，说明队列已满，返回布尔值false说明添加失败；当tail走到头，obj->tail==obj->k 成立，就将tail置为0，达到队列循环的作用，否则就是正常情况，直接obj->tail++即可。
最终返回布尔值true说明添加成功。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
obj->a[obj->tail]=value;
if(myCircularQueueIsFull(obj))
return false;
if(obj->tail==obj->k)
obj->tail=0;
else
obj->tail++;
return true;
} 3.“队列”删除函数：队列是头删，正常情况是质疑删一个，obj->front++即可，但要考虑到“空队列”和front走到头 两种情况：提前利用下面的判空函数 myCircularQueueIsEmpty(obj) ，如果此函数为true，说明队列为空，不能再删除，return false，表明删除失败；front走到头时，即obi->front==obj->k成立，就把front置为0，达到循环的目的，否则为正常情况，直接obj->front++即可，只要删除成功，就return true。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
return false;
if(obj->front==obj->k)
{
obj->front=0;
}
else
{
obj->front++;
}
return true;
}4.查找“队列”头部数值的函数：如果是空队列就返回-1（题目要求），不空就返回数组队列头部的那个值。
int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
if( myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->front];
}5.查找“队列”尾部数值的函数：如果是空队列就返回-1（题目要求），因为tail是最后一个数据的下一个结点的地址，所以不空也有两种情况：如果obj->tail是整个队列的第一个数据的角标，那他的上一个数据就是尾数据，因为当obj->tail=obj->k时，再添加数据，tail因为循环又要回到头部，即obj->tail=0，这个情况就直接返回尾数据 obj->a[obj->k] 即可。
否则就是正常情况，返回tail位置的上一个值即可。
int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
if( myCircularQueueIsEmpty(obj))
return -1;
if(obj->tail==0)
return obj->a[obj->k];
else
return obj->a[obj->tail-1];
}6.检查“队列”是否为空函数：当front和tail相等时，说明队列为空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
assert(obj);
return obj->front==obj->tail;
}7.检查“队列”是否已满 函数：正常情况是：当tail的下一个位置的角标和front相等时，即为满队列。
但考虑特殊情况 obj->tail=obj->k 时，tail的下一个位置是头坐标，所以就是obj->tail=obj->k的同时obj->front=0，也是满队列的情况。
要考虑全！
bool myCircularQueueIsFull(MyCircularQueue* obj) {
assert(obj);
if(obj->tail==obj->k && obj->front==0)
return true;
return obj->tail+1==obj->front;
}
8.释放“队列” 函数：释放两个空间，分别是结构体“队列”中的数组a，其实就是结构体obj本身的空间也要释放。
void myCircularQueueFree(MyCircularQueue* obj) {
assert(obj);
free(obj->a);
free(obj);
}typedef struct {
int* a;
int front;
int tail;
int k;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->front=obj->tail=0;
obj->k=k;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
obj->a[obj->tail]=value;
if(myCircularQueueIsFull(obj))
return false;
if(obj->tail==obj->k)
obj->tail=0;
else
obj->tail++;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
return false;
if(obj->front==obj->k)
{
obj->front=0;
}
else
{
obj->front++;
}
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
if( myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
if( myCircularQueueIsEmpty(obj))
return -1;
if(obj->tail==0)
return obj->a[obj->k];
else
return obj->a[obj->tail-1];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
assert(obj);
return obj->front==obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
assert(obj);
if(obj->tail==obj->k && obj->front==0)
return true;
return obj->tail+1==obj->front;
}
void myCircularQueueFree(MyCircularQueue* obj) {
assert(obj);
free(obj->a);
free(obj);
}欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）