2022_08_05__106期__栈和队列

目录

用队列实现栈

越界问题：

栈的创建

栈的插入：

栈的首位

栈的删除

栈的判空：

栈的销毁

用栈实现队列：

队列的定义：

队列的创建：

插入队列元素

转化函数：

队列元素的删除：

找出栈顶的元素：

判断队列是否为空

队列销毁：

设计循环队列：

数组名：

接下来，我们写数组的创建：

数组判空

数组判满

入队列：

出队列：

取队头的数据：

去队尾的数据：

数组的释放：

接下来，我们对代码整体分析：

---

力扣

用队列实现栈

我们首先讲一下思路：

 我们要保持其中一个队列为空，另一个队列不为空。

假如我们要删除数据的时候：

 对于队列来说，我们要删除队头的数据，也就是1，而对于栈来说，我们要删除的是队尾的数据，也就是4，所以我们要用两个队列来实现删除队尾的数据

我们先取出三个元素到另一个队列

 然后我们可以直接取出元素4，然后删除掉

 接下来，我们继续删除数据，对于栈来说，我们要删除队尾的数据，也就是3，但对于队列，我们只能删除队头的元素，也就是1.

 然后我们取出3，删除掉。

 这里，我们就实现了栈的删除，接下来，我们思考如何实现栈的添加。

假如我们要在这个时候，添加元素5和元素6

 我们只需判断，两个队列哪一个不为空，我们就添加元素5和6

 这就是整体的思路。

我们首先写栈的创建，有些人是这样写的：

MyStack* myStackCreate() {
	MyStack st;
	return &st;
}

这种写法是错误的，因为我们参数是在局部域中创建的，是局部变量，局部变量出函数自动销毁，我们返回参数的地址，但是我们创建的参数已经被释放，访问的话就形成了野指针。

正确的写法：

MyStack* myStackCreate() {
	MyStack*obj = (MyStack*)malloc(sizeof(MyStack));
	return obj;
}

我们会函数栈帧的形式进行解释：

 main函数调用栈的创建函数，然后我们函数返回，对应的栈帧销毁，返回对应的参数的地址。

 接下来，我们调用其他的函数：

 但是myStackPush1函数覆盖了原来的区域，所以对应的参数的值也发生改变，这时候的st的值已经不再是原来的值了。

越界问题：

越界读几乎不会产生问题：

#include
int main()
{
	int a[10];
	printf("%d", a[11]);
	printf("%d", a[10]);
	printf("%d", a[12]);
}

 这些越界访问都没有报错，但是假如我们进行越界写呢？

#include
int main()
{
	int a[10];
	printf("%d", a[11]);
	printf("%d", a[10]);
	printf("%d", a[12]);
	a[10] = 1;
	a[11] = 2;
	a[12] = 3;
}

我们进行编译：

 这里报错了，那是不是所有的越界写都会报错呢？

答案是不：

int main()
{
	int a[10];
	printf("%d", a[11]);
	printf("%d", a[10]);
	printf("%d", a[12]);
	a[12] = 3;
}

我们进行编译：

发现这里并没有报错。

总结：越界的检查其实是一种抽查。

我们画图进行分析：

 越界是这样检查的，我们进行编译，编译器会检查粉色的区域是否被我们覆盖，假如没有覆盖时，我们不报错，假如覆盖的话，我们报错，所以假如我们越界访问的区域并不在粉色的区域，那我们进行越界写也不会报错。

栈的创建

MyStack* myStackCreate() {
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

动态内存开辟一个栈的空间，然后对我们自己构建的栈中的两个队列进行初始化。

栈的插入：

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else{
        QueuePush(&obj->q2,x);
    }
}

分析：如果队列1不为空时，我们向队列1插入元素x，否则向队列2插入元素。

栈的首位

int myStackTop(MyStack* obj) {
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

分析：

 对于栈，我们要取出栈的首位，也就是4，所以对于队列，我们要取出队列队尾的数据。

如果队列1不为空的话，我们返回队列1的末尾数据

如果队列2不为空的话，我们返回队列2的末尾数据：

栈的删除

int myStackPop(MyStack* obj) {
	Queue*Empty = &obj->q1;
	Queue*nonEmpty = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		Empty = &obj->q2;
		nonEmpty = &obj->q1;
	}
	while (QueueSize(nonEmpty) > 1)
	{
		QueuePush(Empty, QueueFront(nonEmpty));
		QueuePop(nonEmpty);
	}
	int top = QueueFront(nonEmpty);
	QueuePop(nonEmpty);
}

我们画图来分析：

 我们要对栈进行删除，对栈删除时要首先删除4，所以我们要删除队列中的4.

Queue*empty=&obj->q1;
    Queue*nonEmpty=&obj->q2;

我们假设队列1为空，队列2不为空。

if(!QueueEmpty(&obj->q1))
    {
        empty=&obj->q2;
        nonEmpty=&obj->q1;
    }

假设队列1不为空的话，我们就设队列2为空，队列1不为空。

 while(QueueSize(nonEmpty)>1)
    {
        QueuePush(empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }

我们进行循环，当不为空的队列元素大于1时进入循环，我们把不为空的队列的头元素，插入到空队列，然后我们删除掉不为空队列，删除的是队头的元素。

int top = QueueFront(nonEmpty);
	QueuePop(nonEmpty);

我们已经删除到最后一个元素，QueueFront和QueueBack取出的结果都相同，我们把它赋给top，删除掉队列中的元素。

栈的判空：

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

栈为空的条件是两个队列都必须为空。

栈的销毁

许多人会这样写：

void myStackFree(MyStack* obj) {
    free(obj);
}

这样写是不对的，如图所示：

 假如我们把obj置为空指针，那么q1和q2指向的队列就没有释放，就造成了内存泄漏

所以我们首先要把两个队列进行释放，再释放obj

正确的写法是这样：

void myStackFree(MyStack* obj) {
    QueueDestory(q1);
    QueueDestory(q2);
    free(obj);
}

下一道题目：

力扣

用栈实现队列：

我们用图像进行分析：

 假设我们向栈1push四个元素1，2，3，4.结果为：

 对于队列来说，我们pop出的元素是1，而对于栈来说，我们pop出的元素为4，所以我们可以把栈1的元素导入到栈2中去：

 我们栈2pop出的元素是4：

 这时候，再pop的话，栈2pop的结果为3，和栈pop的结果是相同的。

但是这里我们需要注意一点，就是这时候push元素的话，该怎么处理：

我们可以push到栈1

然后push完毕栈2的元素

 当栈2的元素为空时，把栈1的元素导入到队列2中去：

 然后我们pop出栈2的数据

 

 所以我们可以把栈1和栈2分别起另外一个名字：

 其中，st1代表我们push数据到st1，st2代表我们pop数据到st2.

我们开始用代码编写：

队列的定义：

typedef struct {
    Stack pushST;
    Stack popST;
} MyQueue;

这里代表我们的队列是由两个栈组成的。

队列的创建：

MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->pushST);
    StackInit(&obj->popST);
    return obj;
}

我们首先动态内存开辟一部分空间，供以结构体指针使用，然后通过结构体初始化两个栈，然后返回队列的指针。

插入队列元素

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST,x);
}

非常简单，我们只需要往用于push的栈中push即可，与栈为空不为空没有任何关系。

接下来，我们来分析，假如我们要写删除队列的某个元素：

如图所示，逻辑是这样的，假如栈2不为空时，我们就逐步删除栈2的元素，假如栈2为空时，我们需要把栈1的全部元素push到栈2中去，然后删除栈1的元素，再逐步删除栈2的元素，所以我们的代码如图所示：

所以我们首先要首先当栈为空时，对应的代码：

我们需要创建一个函数

转化函数：

void pushSTToPopst(MyQueue*obj)
{
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
}

接下来，我们来实现

队列元素的删除：

int myQueuePop(MyQueue* obj) {
    pushSTToPopst(obj)；
    int front=StackTop(&obj->popST);
    StackPop(&obj->popSt);
    return front;
}

我们对代码进行分析：首先调用转化函数，调用完毕之后，栈2一定不为空，所以我们直接取出

栈2的栈顶元素，栈顶元素就是栈要删除的元素，我们把它赋给front,然后调用删除栈元素函数删除掉这个栈顶元素，然后返回这个栈顶元素。

找出栈顶的元素：

int myQueuePeek(MyQueue* obj) {
    pushSTToPopst(obj);
    int front=StackTop(&obj->popST);
    return front;
}

找出栈顶的元素和删除队列的元素的对象都是栈2中的栈顶元素，无非就是找出栈顶的元素不需要删除，而删除队列的元素需要删除。

判断队列是否为空

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST)
    &&StackEmpty(&obj->popST);
}

队列为空的条件是两个栈都必须为空。

队列销毁：

void myQueueFree(MyQueue* obj) {
    StackDestory(&obj->pushST);
    StackDestory(&obj->popST);
    free(obj);
}

不能直接释放obj，原因是这样：

 我们的obj指向的是两个结构体指针，假如我们释放obj的话，是不能够把结构体指针指向的栈释放的，所以就会导致内存泄漏。

力扣

设计循环队列：

我们首先画图分析一下思路：

 如图就是对应的环形缓冲器：

因为我们的队列要保持先进先出：

 假如我们要删除元素，首先要删除front，假如我们删除两个元素：

 front也随着删除的移动而移动。

假设我们要添加元素呢？

假设我们添加两个元素：

 back也随添加元素移动而移动。

虽然我们画图画的是环形的，但是我们实际上要写的代码要是线性的，我们提供两种不同的思路：

首先，用数组的形式写：

 假设我们的数组位移动到6的后面时，我们直接指向1，形成这样的环

第二种，链表的形式：

最后的尾节点指向头，形成链表

对于数组而言：假设我们要输入数据：

 

 假如我们要删除两个数据：

 

 假如我们这里再输入元素5

 对于链表，形式也是相同的。

但是对于我们当前的链表和数组的问题是什么？

不知道如何判断空和判断满

例如：

对于空数组：

 假设数组位空时：头指针和尾指针指向同一个位置：

而对于满数组：

我们进行逐渐输入元素来看数组内部指针的指向：

 

 

 

 可以发现，无论是空数组还是满数组，他们的首尾指针指向的位置都是相同的。

对于链表也是相同的结果：

假如我们删除两个元素呢？

我们删除的是队头的元素：

 我们再插入两个元素：5 ，6

 back和front又指向了同一个位置。

所以，无论是空数组还是满数组又或者是空链表还是满链表，头尾指针指向的位置都是相同的。

这种问题有两种解决方法：

1：加一个参数size，表示数组或者链表的元素个数，假如元素个数为0，就表示为空数组或者空链表，假如元素为创建的空间数：表示满数组和满链表。

2：额外开辟一个空间，放在原空间的最后位置：

原空间：

 新空间：

 我们进行输入元素

 当back的下一位指向首位，就说明数组已经满了，当back等于首位，就说明数组空了。

我们用数组的写法写：

数组名：

typedef struct {
    int*a;
    int front;
    int back;
    int N;
} MyCircularQueue;

我们创建一个结构体，有四个成员变量，一起形成一个数组。

分别表示数组名，数组头，数组位，和要创建的空间数：

接下来，我们写数组的创建：

MyCiMyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->back=0;
    obj->N=k+1;
    return obj;
}

k表示的数组元素个数，我们需要先开辟空间，这里必须开辟动态空间，假如开辟静态空间时，退出函数，对应的空间就销毁了。

我们创建一个结构体指针obj，通过obj修改成员变量。

我们要为数组开辟额外的空间，开辟的空间大小为k+1个整型空间，数组首元素的地址指向对应的空间。

然后我们把成员变量中的头和尾初始化为0.把成员变量中要扩建的空间个数赋值为k+1.

数组判空

数组判空非常简单，就是我们之前分析的，假如数组头和数组尾重合时，数组就为空。

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->back;
}

 当数组头和数组尾重合时，就表示数组为空。

数组判满

数组判满也非常简单，当back的下一位为头，就表示数组满了

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back+1)==obj->front;
}

这样的写法对吗？是错误的：

有特殊情况：

 这时候，back的下一位并不与front重合，所以我们可以使用余数的方法：

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back+1)%obj->N==obj->front;
}

入队列：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->back]=value;
    obj->back++;
    obj->back%=obj->n;
    return true;
}

入队列时，我们要判断数组是否满了，假如数组满了的话，入队列失败。

然后我们把输入的值valu赋给back指向的位置，然后back向后移，但是back也不能一直往后移动，当我们入队列到最后一位时，back要回到头位置。处理完毕，返回true。

出队列：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return false;
    obj-
    obj->front%=obj->n;
    return true;
}

假如数组为空时，不能删除元素，所以返回false

数组不为空：在这里我们删除数组的元素，其实就是让front指针跳过这个元素即可，所以我们让front++，但是注意和上面相同的问题，当front到末位时，它的下一位是队头，所以我们要取余数，返回true。

取队头的数据：

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    else
    return obj->a[obj->front];
}

如果数组中元素满了，我们返回-1.

否则，我们返回front指向指向的数组元素。

去队尾的数据：

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    else if(obj->back==0)
    return obj->a[obj->N-1];
    else
    return obj->a[obj->back-1];
}

我们的思路是返回back前一位的数组元素，但是还是有意外的情况：

 back在首位，back的前一位是末尾，我们如何取到末尾呢，所以我们就需要分情况讨论。

对代码进行分析：假如数组为空，返回-1，退出函数

假如数组不为空：假如我们的back在头，我们需要返回尾的元素，也就是下标obj->n-1对应的元素

假如我们的back不在头，我们只需要返回obj->back-1对应的元素即可。

接下来是

数组的释放：

我们释放空间需要分两部分，一部分是动态开辟赋给obj的空间，另一部分是动态开辟赋给obj->a的空间。

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

接下来，我们对代码整体分析：

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

1：数组的命名：

typedef struct {
    int*a;
    int front;
    int back;
    int N;
} MyCircularQueue;

我们需要创建的是一个数组，a表示数组名，front表示数组头的下标，back表式数组尾的下一个的下标，N表示需要开辟多少空间。

这里我们采用额外开辟一个空间的判空判满的方法：

2：数组的创建:

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->back=0;
    obj->N=k+1;
    return obj;
}

我们需要开辟两块空间，而且需要用动态内存开辟的方法，我们开辟一个空间给我们的结构体，然后我们再开辟一块空间给我们的数组，数组元素为k个时，我们需要开辟k+1个字节的空间

然后我们顺表实现以下初始化，把数组头和数组尾赋为0，然后把N赋值为k+1.

3：数组的判空：

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->back;
}

我们使用bool类型，当front和back的下标相同，就表示数组为空。

4：数组是否满的判定：

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back+1)%obj->N==obj->front;
}

数组满时基本的判定条件是back的下一位的坐标是front，我们可以采用取余数的方法实现。

5：数组插入元素：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->back]=value;
    obj->back++;
    obj->back%=obj->N;
    return true;
}

首先，我们要判定数组是否已经满了，假如数组满了的话，返回false。

然后我们把value的值放在数组尾部的元素，然后数组尾往后移，取余数，执行完毕，返回true

6：数组删除元素：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return false;
    obj->front++;
    obj->front%=obj->N;
    return true;
}

如果链表为空时，无法删除，返回false

我们删除元素只需要让front的下标往后移即可，然后再取余数，返回true。

7：数组的头位置查找：

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    else
    return obj->a[obj->front];
}

我们首先进行判断：数组是否为空，如果为空的话，直接退出函数，不为空，返回front的下标对应的数组元素。

8：数组尾元素的查找：

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    else if(obj->back==0)
    return obj->a[obj->N-1];
    else
    return obj->a[obj->back-1];
}

我们要先进性判断：数组是否为空，如果不为空的话，退出函数，然后当back在第一位元素时，我们返回数组最后一位元素。

当back不在第一位元素时，返回back-1下标对应的元素。

9：数组的释放：

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

我们需要先释放数组，然后再释放结构体，否则就会造成内存泄漏。