LeetCode数据结构栈和队列必刷OJ题

题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

首先我们知道队列的特性是先入先出，栈的特性是先入后出，题目既然给了我们两个队列，那么一定是利用这两个队列进行捯数据，从而实现栈先入后出的特性。

思路：

每次入栈，利用不空的队列入数据；
当需要出栈时，将非空队列“出队”到空的队列上，直到剩余最后一个元素，取该元素，然后出队，即完成出栈动作。
当需要取栈顶元素时，只需要取非空队列的队尾，此时该队尾即为栈顶元素。
当需要判空时，只需要判断两个队列是否都为空即可。

注意：该题主要考察的其实是大家对于结构的理解，如形参MyStack* obj，实参对应为&obj->q1或&obj->q2，&操作符的优先级低于->，obj是该栈指针，obj->q1为队列结构体，但由于参数为指针类型，所以需要&。

代码实现：

// 队列的基本函数
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Que;
void QueueInit(Que* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
bool QueueEmpty(Que* pq)
{
assert(pq);
return pq->head == NULL;
}
void QueueDestroy(Que* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueuePush(Que* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->tail = pq->head = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size ;
}
void QueuePop(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}
QDataType QueueFront(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataType QueueBack(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
int QueueSize(Que* pq)
{
assert(pq);
return pq->size;
}
// 以上为队列的基本函数
// 以下为用队列实现栈
// 定义栈
typedef struct
{
Que q1;
Que q2;
} MyStack;
// 创建栈
MyStack* myStackCreate()
{
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
// 入栈
void myStackPush(MyStack* obj, int x)
{
if (!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
// 出栈
int myStackPop(MyStack* obj)
{
// 假设法，假设q1为空，q2不空
Que* EmpQue = &obj->q1;
Que* noEmpQue = &obj->q2;
if (!QueueEmpty(&obj->q1))
{
noEmpQue = &obj->q1;
EmpQue = &obj->q2;
}
// 此时EmpQue一定为空的队列，noEmpQue 一定不为空的队列
// 将size-1个数据移动到空队列中
while (QueueSize(noEmpQue) > 1)
{
QueuePush(EmpQue, QueueFront(noEmpQue));
QueuePop(noEmpQue);
}
//保存返回值
int ret = QueueFront(noEmpQue);
QueuePop(noEmpQue);
return ret;
}
// 取栈顶元素
int myStackTop(MyStack* obj)
{
// 不空的队列的队尾即为栈顶
if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
// 判空
bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
// 销毁栈
void myStackFree(MyStack* obj)
{
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
// free栈之前一定要先销毁队列，否则会导致内存泄露
free(obj);
}

【LeetCode】232.用栈实现队列

原题链接：🍏用栈实现队列🍏

题目：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾

int pop() 从队列的开头移除并返回元素

int peek() 返回队列开头的元素

boolean empty() 如果队列为空，返回 true ；否则，返回 false

与上面用队列实现栈的思路相似，需要两个栈用来捯数据，不同的是，分析过后你会发现这里的两个栈，一个可以固定用来做入队栈（下面统称为pushst），而另外一个固定用来做出队栈（下面统称为popst）。

思路：

入队时，直接push到pushst即可；
出队时，需要进行判断，当popst不为空时，直接出栈popst，注意保存栈顶元素以便返回；当popst为空时，需要将pushst的数据依次捯到popst中，然后出栈popst，同样注意保存栈顶元素以便返回；
返回队头元素时，我们可以写一个返回栈底元素的函数，然后同样进行判断，如果popst为空，我们就返回pushst的栈底；如果popst不为空，我们就返回popst的栈顶即可；
判空时，思路与用队列实现栈相同。

代码实现：

typedef struct
{
ST s1;//入队栈pushst
ST s2;//出队栈popst
} MyQueue;
MyQueue* myQueueCreate()
{
MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&pst->s1);
STInit(&pst->s2);
return pst;
}
void myQueuePush(MyQueue* obj, int x)
{
STPush(&obj->s1,x);
}
int myQueuePop(MyQueue* obj)
{
if(!STEmpty(&obj->s2))
{
int x=STTop(&obj->s2);
STPop(&obj->s2);
return x;
}
else
{
while(!STEmpty(&obj->s1))
{
int x=STTop(&obj->s1);
STPop(&obj->s1);
STPush(&obj->s2,x);
}
int y=STTop(&obj->s2);
STPop(&obj->s2);
return y;
}
}
int myQueuePeek(MyQueue* obj)
{
if(STEmpty(&obj->s2))
{
return STbase(&obj->s1);
}
else
{
return STTop(&obj->s2);
}
}
bool myQueueEmpty(MyQueue* obj)
{
return STEmpty(&obj->s1)&&STEmpty(&obj->s2);
}
void myQueueFree(MyQueue* obj)
{
STDestroy(&obj->s1);
STDestroy(&obj->s2);
free(obj);
}

【LeetCode】622.设计循环队列

原题链接：🍏设计循环队列🍏

题目：设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。

Front: 从队首获取元素。如果队列为空，返回 -1 。

Rear: 获取队尾元素。如果队列为空，返回 -1 。

enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

isEmpty(): 检查循环队列是否为空。

isFull(): 检查循环队列是否已满。

由于题目中已经明确队列长度，所以定长数组是一个较优的解决方案。

该题目最要首先理解的两个函数为判空和判满。

判空：我们首先肯定会想到当front和rear相等时，即为空。

学新通

那么问题来了，如何判满呢？

貌似判空和判满都可以利用front和rear是否相等来判断，如何区分呢？

判满：普遍的解决方案为牺牲一个空间，让该数组始终留有一个空间，用作区分，那么就有以下几种情况，请试着依据下图总结规律，得到判满通用公式。

学新通

判满公式：(rear 1)%(k 1)==front

只要了解了这个思想，剩下的就简单很多了。

代码实现：

typedef struct
{
int* a;
int front;
int rear;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k 1));
obj->front=obj->rear=0;
obj->k=k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front==obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return (obj->rear 1)%(obj->k 1)==obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->rear]=value;
obj->rear ;
obj->rear%=obj->k 1;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->front ;
obj->front%=(obj->k 1);
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
return obj->a[(obj->rear obj->k)%(obj->k 1)];
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);
free(obj);
}

=========================================================================

如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容

🍎博主很需要大家的支持，你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏＋关注 ~🌟

=========================================================================

这篇好文章是转载于：学新通技术网

LeetCode数据结构栈和队列必刷OJ题

前言：

【LeetCode】20.有效的括号（栈的括号匹配问题）

【LeetCode】225.用队列实现栈

【LeetCode】232.用栈实现队列

【LeetCode】622.设计循环队列

photoshop保存的图片太大微信发不了怎么办

《学习通》视频自动暂停处理方法

word里面弄一个表格后上面的标题会跑到下面怎么办

Android 11 保存文件到外部存储，并分享文件

photoshop扩展功能面板显示灰色怎么办

微信公众号没有声音提示怎么办

excel下划线不显示怎么办

excel打印预览压线压字怎么办

TikTok加速器哪个好免费的TK加速器推荐

怎样阻止微信小程序自动打开