数据结构（栈和队列的实现）

1. 栈（Stack）

1.1 栈的概念与结构

  • 栈是一种特殊的线性表，其只允许固定的一段插入和删除操作；进行数据插入和删除的一段叫做栈顶，另一端叫栈底；栈中的元素符合后进先出LIFO（Last In First Out）的原则。
  • 入栈：入栈就是往栈里放入数据；
  • 出栈：出栈就是从栈里拿出数据；（注意这两个操作都是对栈顶的数据进行操作）；

2be032cadfd94a079a2bf58337718e8d.png

  • 栈底层结构选型：栈的实现选用的是数组；选用链表也可以，但在插入和删除操作更方便一些；因为链表尾插需要遍历找到尾结点，那么尾插的操作时间复杂度就为O(N)，不过我们可以优化一下，拿链表的头部作为栈顶，插入和删除就为O(1)了，但是由于我们可能还需要创建多个指针进行操作，所以最优还是选择数组，因为数据的尾插和尾删时间复杂度都为O(1)，而且找到尾部的位置不需要创建什么指针啥的，因为顺序表里本身就有一个size代表数组的大小，而最后一个位置则是下标为size-1的位置；

1.2 栈的实现

       --定义栈的模型

        由于栈底层可以使用顺序表实现，那就和之前顺序表一样，需要一个计算总空间有多大的capacity和一个储存有效元素个数的top（在顺序表其实就是size，但这里为了符合栈所以用top），还有一个储存整型类型的数组，但后面会出现增容的操作所以使用指针，STDateType* arr；如下代码所示：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int STDatetype;

typedef struct Stack
{
	STDatetype* arr;
	int capacity;  //栈空间大小
	int top;       //栈顶
}ST;

        --栈的初始化和销毁

void STInit(ST* st)
{
	assert(st);
	st->arr = NULL;
	st->capacity = st->top = 0;
}

void STDestory(ST* st)
{
	assert(st);
	if(st->arr)
		free(st->arr);
	st->arr = NULL;
	st->capacity = st->top = 0;
}

        --入栈操作的实现

        入栈的实现：首先我们要判空间是否足够，而判断空间是否足够的条件就是栈顶是不是等于整个数组空间的容量，如果等于就需要使用realloc进行扩容，那么我们就需要创建一个Newcapacity作为扩容的空间，我们按2倍进行扩容则：2* capacity， 但是如果说capacity为0的话那么就无法进行扩容，因为0 * 任何数都等于0，所以我们写一个三目运算符，如果说capacity等于0的话就让Newcapacity等于4，否则等于2* capacity；后面我们就需要创建一个新的指针指向扩容的空间，因为如果说扩容失败的话就会对整块空间造成影响，所以我们需要创建一个新的空间进行扩容；而入栈的实现其实就是在数组最后面插入元素；代码实现如下：

void StackPush(ST* ps, STDatetype x)
{
	assert(ps);
	if (ps->capacity == ps->top  )
	{
		int Newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDatetype* temp = (STDatetype*)realloc(ps->arr, Newcapacity *sizeof(STDatetype) );
		if (temp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = temp;
		ps->capacity = Newcapacity;
	}
	ps->arr[ps->top++] = x;
}

      

          --判断栈是否为空

        判空实现：其实就是看看栈顶是否为0，当栈顶都为0，那肯定就是没有数据了；代码实现如下：

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

        --出栈操作的实现

        出栈的实现：实际上其实就是顺序表进行尾删操作，那我们就直接让数组内的有效元素减少一个就可以，即size--；但是我们还需要判断栈是否为空，如果为空那就没有元素可以出；代码如下：

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	--ps->top;
}

        --取栈顶元素

        取栈顶元素：取栈顶元素则是直接返回数组的尾部元素即是：ps->arr[ps->top-1]；为什么要-1？因为top是有效元素的个数，但下标的起始位置是0，所以要-1；如下代码所示：

//取栈顶元素
STDatetype StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	
	return ps->arr[ps->top-1];
}

        --获得栈中有效元素的个数

        由上可知，有效元素的个数其实就是top，所以直接返回即可；如下代码所示：

//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

1.3 栈的完整代码

Stack.h

#pragma once

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int STDatetype;

typedef struct Stack
{
	STDatetype* arr;
	int capacity;  //栈空间大小
	int top;       //栈顶
}ST;

//首先创建这些都是要实现初始化
void STInit(ST* st);
void STDestory(ST* st);

//栈顶---入数据、出数据
void StackPush(ST* ps, STDatetype x);
void StackPop(ST* ps);

//取栈顶元素
STDatetype StackTop(ST* ps);

bool StackEmpty(ST* ps);

//获取栈中有效元素个数
int STSize(ST* ps);

Stack.cpp

#include"Stack.h"

void STInit(ST* st)
{
	assert(st);
	st->arr = NULL;
	st->capacity = st->top = 0;
}
void STDestory(ST* st)
{
	assert(st);
	if(st->arr)
		free(st->arr);
	st->arr = NULL;
	st->capacity = st->top = 0;
}

void StackPush(ST* ps, STDatetype x)
{
	assert(ps);
	if (ps->capacity == ps->top  )
	{
		int Newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDatetype* temp = (STDatetype*)realloc(ps->arr, Newcapacity *sizeof(STDatetype) );
		if (temp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = temp;
		ps->capacity = Newcapacity;
	}
	ps->arr[ps->top++] = x;
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	--ps->top;
}

//取栈顶元素
STDatetype StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	
	return ps->arr[ps->top-1];
}

//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

 

2. 队列（Queue）

2.1 队列的概念与结构

  • 概念：只允许在一端插入数据和从另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First In First Out）；
  • 入队列：进行插入操作的一端称为队尾；
  • 出队列：进行删除操作的一端称为队头；3752428e35374bd0b144a601c3255fd0.png
  • 队列的底层结构选型：队列底层结构选的是链表，因为要进行入队列和出队列的操作，如果说用顺序表的话，在进行出队列的操作的时候删除了头部数据那就得让后面数据往前走，那时间复杂度就为O(N)，所以我们使用链表；但使用链表的时候要注意，我们需要头结点出数据实现出队列操作，尾结点入数据实现入队列操作，不然的话我们要遍历到尾结点删除数据实现出队列 时间复杂度又为O(N)了；

2.2 队列的实现

        --定义队列的模型

        队列的底层实现就是用链表来实现，那么我们就要定义结点还有队列的模型；为什么要定义两个呢？因为我们还需要一个指向头结点和指向尾结点的指针，还有一个整型size记录队列内的数据；

#pragma once
#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;


typedef int QDataType;
//每个结点
typedef struct QueueNode
{
	QDataType data;
	QueueNode* next;
}QueueNode;

//队列
typedef struct Queue
{
	QueueNode* phead;
	QueueNode* tail;
	int size;
}Queue;

        --队列的初始化和销毁

        队列的销毁其实就和链表的销毁一样，首先创建一个指向头结点下一个节点的next指针，然后把头结点销毁掉，在让头结点指针指向next指针，next指针再走向头结点的下一个指针，一直循环到头结点为NULL的时候结束‘；代码如下：

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->tail = NULL;
	pq->size = 0;
}


void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->tail = NULL;
	pq->size = 0;
}

        --入队列的实现

        入队列的实现：需要结合链表的buynode（动态申请一个结点空间）来实现，首先我们先申请一个newnode的空间，让其指向空，data = x；再就要判断队列是否为空，如果说队列为空的话那就说明队列里面没有结点，那就需要让phead和ptail指针指向该结点，如果有结点的话就让ptail->next指针指向newnode，再让ptail走到newnode的位置，最后还要记得size++，因为size是计算队列内有效元素的个数；如下图和代码所示：

队列为空：c37f4e64bb334c14b62a998189b9f5f7.gif

队列不为空：0e56d732009c4c888509b140233e66ba.gif

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//说明链表为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
	pq->size++;
}

        --队列判空操作

        队列判空其实就是看头结点和尾结点的指针是否都指向NULL，如果都指向NULL就为空；代码如下：

//队列判空
bool QueueEmpty(Queue* pq)
{
	return pq->phead == NULL && pq->tail == NULL;
}

        --出队列的操作

        出队列的操作本质上就是链表删除头结点；我们只需要定义一个Del指针指向当前的头结点pcur，再让当前的头结点走到头结点的下一个结点pcur = pcur->next，然后free掉Del结点即可；图和代码如下：7ddc014d159a4d6dbcd5ae0c1584edb9.gif

// 出队列，队头
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//只有一个结点
	if (pq->tail == pq->phead)
	{
		free(pq->phead);
		pq->phead = NULL;
		pq->tail = NULL;
	}
	else
	{
		QueueNode* Del = pq->phead;
		pq->phead = pq->phead->next;
		free(Del);
	}
	--pq->size;
}

注意！！！我们还需要单独判断只有一个结点的时候，当ptail和phead都指向同一个空间的时候就代表队列中只有一个结点，那么这时候我们还进行phead = phead->next就是让phead走向一块未知的空间，进行非法访问；

        --取队头和队尾数据

        因为有指针指向队头和队尾，就不过多阐述了；注意一点就是我们要判断队列是否为空；代码如下所示：

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

        --取队列有效元素个数

        因为我们一开始就已经创建了一个size 对队列的有效元素个数进行记录，所以直接返回size即可；如下代码所示：

//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

2.3 队列的完整代码

Queue.h

#pragma once
#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;


typedef int QDataType;
//每个结点
typedef struct QueueNode
{
	QDataType data;
	QueueNode* next;
}QueueNode;

//队列
typedef struct Queue
{
	QueueNode* phead;
	QueueNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
// 出队列，队头
void QueuePop(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

//销毁队列
void QueueDestroy(Queue* pq);

Queue.cpp

#include"Queue.h"


void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//说明链表为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
	pq->size++;
}

//队列判空
bool QueueEmpty(Queue* pq)
{
	return pq->phead == NULL && pq->tail == NULL;
}

// 出队列，队头
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//只有一个结点
	if (pq->tail == pq->phead)
	{
		free(pq->phead);
		pq->phead = NULL;
		pq->tail = NULL;
	}
	else
	{
		QueueNode* Del = pq->phead;
		pq->phead = pq->phead->next;
		free(Del);
	}
	--pq->size;
}


//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->tail = NULL;
	pq->size = 0;
}

3.栈和队列的OJ题

3.1 有效的括号

原题链接：20. 有效的括号 - 力扣（LeetCode）

b1bbee2919574999a3acc186aef1318e.png

思路：我们可以创建一个栈，先把开口向右的括号全部入栈里面，当栈不为空的时候取栈顶元素；这步的操作其实就是实现当有｛【（ 这三个括号的时候能直接取到(，然后再和左开口的括号进行比较，如果说取出的栈顶元素是“(”，并且数组的下一个元素是“）”的话就是匹配上了，然后pos++；当不符合的时候直接返回false；如果不返回false一直到循环结束的时候就返回true，因为这说明全部括号都匹配上了；如下图和代码所示：f4d7dd70d5814d8eb8423f96547662e9.gif

#include<stdbool.h>
typedef char STDateType;
typedef struct Stack
{
    STDateType* arr;
    int top ;
    int capacity;
}ST;

void STInit(ST* st)
{
    st->arr=NULL;
    st->top = 0;
    st->capacity = 0;
}

void STPush(ST* st, STDateType x)
{
    if(st->capacity==st->top)
    {
        int Newcapacity = st->capacity==0?4:2*st->capacity;
        STDateType* temp = (STDateType*)realloc(st->arr, Newcapacity* sizeof(STDateType));
        if(temp==NULL)
        {
            perror("realloc fails!");
            exit(1);
        }
        st->arr = temp;
        st->capacity = Newcapacity;
    }
    st->arr[st->top++] = x;
}

bool STempty(ST* st)
{
    return st->top==0;
}

STDateType StackTop(ST* st)
{
    return st->arr[st->top-1];
}


void STPop(ST* st)
{
    assert(!STempty(st));
    --st->top;
}

void STDestory(ST* st)
{
    free(st->arr);
    st->arr = NULL;
    st->capacity = 0;
    st->top = 0;
}

bool isValid(char* s) 
{
    ST st;
    STInit(&st);
    char* ps = s;
    while(*ps!='\0')
    {
        if(*ps=='('||*ps=='{'||*ps=='[')
        {
            STPush(&st, *ps);
        }
        else
        {
            if(STempty(&st))
            {
                return false;
            }
            char ch = StackTop(&st);
            if((*ps==')'&&ch=='(')
            ||(*ps==']'&&ch=='[')
            ||(*ps=='}'&&ch=='{'))
            {
                STPop(&st);
            }
            else
            {
            STDestory(&st);
            return false;
            }
        }
        ps++;
    }
    bool ret = STempty(&st)==true;
    STDestory(&st);
    return ret;
}

这里还有几个需要注意的点是：

  1. 当栈为空的时候就代表没有开口向右的括号，那就没有意义再进行下去了，因为没有括号可以匹配；
  2. 在我们取栈顶元素比较完后要删除比较过的元素，因为取栈顶元素只是取值，并没有实现取并删；
  3. 到最后我们需要判断栈是否为空，栈不为空则说明多出了一个开口向右的括号例如"{ [ ( ) ]"这样是不符合的；

3.2 用队列实现栈

原题链接：225. 用队列实现栈 - 力扣（LeetCode）

2962997933e54fe2b04fb5d672f7fcf5.png

思路：首先我们先分析，队列是先进先出，栈是后进先出，那我们就先来使用1234进行模拟；如果把1234放到栈里面再取出来的话就是4321；8c7bb546caad4b6cba109aa25e5aee7b.png

那么如果说我们想用两个队列来实现的话就得换一种思路，因为队列是先进先出，那么我们就可以尝试先把数据放到一个队列里面，然后把size-1个数据放到另一个空队列里面，再把剩下的那个数据取出来，一直这样循环；如下图所示：fb6a1132c7964153b78083ce41209d1e.gif

typedef int QDataType;
typedef struct QueueNode 
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

//队列
typedef struct Queue
{
	QueueNode* phead;
	QueueNode* tail;
	int size;
}Queue;
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//说明链表为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
	pq->size++;
}

//队列判空
bool QueueEmpty(Queue* pq)
{
	return pq->phead == NULL && pq->tail == NULL;
}

// 出队列，队头
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//只有一个结点
	if (pq->tail == pq->phead)
	{
		free(pq->phead);
		pq->phead = NULL;
		pq->tail = NULL;
	}
	else
	{
		QueueNode* Del = pq->phead;
		pq->phead = pq->phead->next;
		free(Del);
	}
	--pq->size;
}


//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->tail = NULL;
	pq->size = 0;
}


typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;

//初始化
MyStack* myStackCreate() 
{
    MyStack* temp = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&temp->q1);
    QueueInit(&temp->q2);
    return temp;
}

void myStackPush(MyStack* obj, int x) 
{
    //首先我们找哪个队列为空
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
        QueuePush(&obj->q2,x);
}

int myStackPop(MyStack* obj) 
{
    Queue* empQ = &obj->q1;
    Queue* noneQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        noneQ = &obj->q1;
        empQ = &obj->q2;
    }
    while(QueueSize(noneQ)>1) //大于1的原因是要留一个数据
    {
        int front = QueueFront(noneQ);
        QueuePush(empQ, front);
        QueuePop(noneQ);
    }
    int pop = QueueFront(noneQ);
    QueuePop(noneQ);
    return pop;
}

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(obj);
    obj = NULL;

}

3.3 用栈实现队列

原题链接：232. 用栈实现队列 - 力扣（LeetCode）

e3654c89fadb41f695fbe27e6ee1f3d2.png

思路：首先我们分析，用两个栈实现队列的话，栈是先进后出，而队列是先进先出，我们使用1234来进行模拟；

队列是怎么进怎么出，1234进1234出；092b5c2eed7f462b81c50d77e4a8cb14.png

那么我们来看一下首先是堆，如果说我们直接把1234放进去，再取出来的话那就是4321，但是我们通过两个堆可以改变这个先让1234入一个名为pushST的堆，然后再让pushST堆的数据堆顶数据入一个名为popST的堆，这时候popST的堆的数据就为1234了；再取出来即可；那么用栈实现队列push数据到队列末尾的则只需要直接把数据放到堆顶即可；删除数据就如刚刚上面所说，取堆顶然后把最后一个数据留下来再把该数据删除就可以实现；取队头元素的实现也是如此；判空则是看两个堆是否都为空，都为空返回1即可；如下图和代码所示：652ea7dd28794dab9f01cff6063f0614.gif

typedef int STDatetype;

typedef struct Stack
{
	STDatetype* arr;
	int capacity;  //栈空间大小
	int top;       //栈顶
}ST;

void STInit(ST* st)
{
	st->arr = NULL;
	st->capacity = st->top = 0;
}
void STDestory(ST* st)
{
	if(st->arr)
		free(st->arr);
	st->arr = NULL;
	st->capacity = st->top = 0;
}

void StackPush(ST* ps, STDatetype x)
{
	if (ps->capacity == ps->top  )
	{
		int Newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDatetype* temp = (STDatetype*)realloc(ps->arr, Newcapacity *sizeof(STDatetype) );
		if (temp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = temp;
		ps->capacity = Newcapacity;
	}
	ps->arr[ps->top++] = x;
}

bool StackEmpty(ST* ps)
{
	return ps->top == 0;
}

void StackPop(ST* ps)
{
	assert(!StackEmpty(ps));

	--ps->top;
}

//取栈顶元素
STDatetype StackTop(ST* ps)
{
	
	return ps->arr[ps->top-1];
}

//获取栈中有效元素个数
int STSize(ST* ps)
{
	return ps->top;
}



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


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

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

int myQueuePop(MyQueue* obj) 
{
    if(StackEmpty(&obj->popST))
    {
        //为空就把pushST的数据放到popST里面来
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    int top = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return top;
}

int myQueuePeek(MyQueue* 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) 
{
    return StackEmpty(&obj->pushST) &&  StackEmpty(&obj->popST);
}

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

END!

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/888079.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

C++——模拟实现vector

C++——模拟实现vector

1.查看vector的源代码 2.模拟实现迭代器 #pragma oncenamespace jxy {//模板尽量不要分离编译template <class T>class vector{public:typedef T* iterator;//typedef会受到访问限定符的限制typedef const T* const_iterator;//const迭代器是指向的对象不能修改&#xf…
阅读更多...
透明物体的投射和接收阴影

透明物体的投射和接收阴影

1、让透明度测试Shader投射阴影 &#xff08;1&#xff09;同样我们使用FallBack的形式投射阴影&#xff0c;但是需要注意的是&#xff0c;FallBack的内容为&#xff1a;Transparent / Cutout / VertexLit&#xff0c;该默认Shader中会把裁剪后的物体深度信息写入到 阴影映射纹…
阅读更多...
毕业设计_基于springboot+ssm+bootstrap的旅游管理系统【源码+SQL+教程+可运行】【41001】.zip

毕业设计_基于springboot+ssm+bootstrap的旅游管理系统【源码+SQL+教程+可运行】【41001】.zip

毕业设计_基于springbootssmbootstrap的旅游管理系统【源码SQL教程可运行】【41001】.zip 下载地址&#xff1a; https://download.csdn.net/download/qq_24428851/89828190 管理系统 url: http://localhost:8080/managerLoginPageuser: admin password: 123 用户门户网站…
阅读更多...
【设计模式-解释模式】

【设计模式-解释模式】

定义 解释器模式是一种行为设计模式&#xff0c;用于定义一种语言的文法&#xff0c;并提供一个解释器来处理该语言的句子。它通过为每个语法规则定义一个类&#xff0c;使得可以将复杂的表达式逐步解析和求值。这种模式适用于需要解析和执行语法规则的场景。 UML图 组成角色…
阅读更多...
SPDK从安装到运行hello_world示例程序

SPDK从安装到运行hello_world示例程序

SPDK从安装到运行示例程序 #mermaid-svg-dwdwvhrJiTcgTkVf {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-dwdwvhrJiTcgTkVf .error-icon{fill:#552222;}#mermaid-svg-dwdwvhrJiTcgTkVf .error-text{fill:#552222;s…
阅读更多...
android compose ScrollableTabRow indicator 指示器设置宽度

android compose ScrollableTabRow indicator 指示器设置宽度

.requiredWidth(30.dp) Box(modifier Modifier.background(Color.LightGray).fillMaxWidth()) {ScrollableTabRow(selectedTabIndex selectedTabIndex, // 默认选中第一个标签containerColor ColorPageBg,edgePadding 1.dp, // 内容与边缘的距离indicator { tabPositions…
阅读更多...
【本地缓存】Java 中的 4 种本地缓存

【本地缓存】Java 中的 4 种本地缓存

目录 1、手写一个简单的本地缓存1.1、封装缓存实体类1.2、创建缓存工具类1.3、测试 2、Guava Cache2.1、Guava Cache 简介2.2、入门案例2.2.1、引入 POM 依赖2.2.2、创建 LoadingCache 缓存 2.3、Guava Cache 的优劣势和适用场景 3、Caffeine3.1、Caffeine 简介3.2、对比 Guava…
阅读更多...
图的基本概念 - 离散数学系列（五）

图的基本概念 - 离散数学系列（五）

目录 1. 图的定义 节点与边 2. 度与路径 节点的度 路径与圈 3. 图的连通性 连通图与非连通图 强连通与弱连通 连通分量 4. 实际应用场景 1. 社交网络 2. 城市交通系统 3. 网络结构 5. 例题与练习 例题1&#xff1a;节点的度 例题2&#xff1a;判断连通性 练习题…
阅读更多...
linux基础 超级笔记

linux基础 超级笔记

1.Linux系统的组成 Linux系统内核&#xff1a;提供系统最核心的功能&#xff0c;如软硬件和资源调度。 系统及应用程序&#xff1a;文件、任务管理器。 2.Linux发行版 通过修改内核代码自行集成系统程序&#xff0c;即封装。比如Ubuntu和centos这种。不过基础命令是完全相…
阅读更多...
【瑞昱RTL8763E】刷屏

【瑞昱RTL8763E】刷屏

1 显示界面填充 用户创建的各个界面在 rtk_gui group 中。各界面中 icon[]表对界面进行描述&#xff0c;表中的每个元素代表一 个显示元素&#xff0c;可以是背景、小图标、字符等&#xff0c;UI_WidgetTypeDef 结构体含义如下&#xff1a; typedef struct _UI_WidgetTypeDef …
阅读更多...
vite学习教程03、vite+vue2打包配置

vite学习教程03、vite+vue2打包配置

文章目录 前言一、修改vite.config.js二、配置文件资源/路径提示三、测试打包参考文章资料获取 前言 博主介绍&#xff1a;✌目前全网粉丝3W&#xff0c;csdn博客专家、Java领域优质创作者&#xff0c;博客之星、阿里云平台优质作者、专注于Java后端技术领域。 涵盖技术内容&…
阅读更多...
【深度强化学习基础】（一）基本概念

【深度强化学习基础】（一）基本概念

【深度强化学习基础】&#xff08;一&#xff09;基本概念 一、概率论基础知识二、强化学习领域术语三、强化学习中两个随机性的来源&#xff1a;四、rewards以及returns五、Value Functions1.Action-Value Function Q π ( s , a ) Q_\pi(s,a) Qπ​(s,a)2.State-Value Funct…
阅读更多...
【高等数学学习记录】函数的极限

【高等数学学习记录】函数的极限

一、知识点 &#xff08;一&#xff09;知识结构 #mermaid-svg-Dz0Ns0FflWSBWY50 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-Dz0Ns0FflWSBWY50 .error-icon{fill:#552222;}#mermaid-svg-Dz0Ns0FflWSBWY50 .erro…
阅读更多...
影刀---如何进行自动化操作

影刀---如何进行自动化操作

本文不是广告&#xff0c;没有人给我宣传费&#xff0c;只是单纯的觉得这个软件很好用 感谢大家的多多支持哦 本文 1.基本概念与操作&#xff08;非标准下拉框和上传下载&#xff09;非标准对话框的操作上传对话框、下载的对话框、提示的对话框 2.综合案例3.找不到元素怎么办&a…
阅读更多...
Leecode刷题之路第12天之整数转罗马数字

Leecode刷题之路第12天之整数转罗马数字

题目出处 12-整数转罗马数字-题目出处 题目描述 个人解法 思路&#xff1a; todo 代码示例&#xff1a;&#xff08;Java&#xff09; todo复杂度分析 todo 官方解法 12-整数转罗马数字-官方解法 方法1&#xff1a;模拟 思路&#xff1a; 代码示例&#xff1a;&#xff08…
阅读更多...
class 032 位图

class 032 位图

这篇文章是看了“左程云”老师在b站上的讲解之后写的, 自己感觉已经能理解了, 所以就将整个过程写下来了。 这个是“左程云”老师个人空间的b站的链接, 数据结构与算法讲的很好很好, 希望大家可以多多支持左程云老师, 真心推荐. 左程云的个人空间-左程云个人主页-哔哩哔哩视频…
阅读更多...
SpringBoot项目：前后端打包与部署（使用 Maven）

SpringBoot项目：前后端打包与部署（使用 Maven）

文章目录 IDEA后端打包与部署&#xff08;使用 Maven&#xff09;1. 确保 Maven 已安装&#xff0c;并引入 pom 插件2. 清理并安装项目3. 定位生成的 JAR 包和配置文件4. 创建部署文件夹5. 上传到服务器 前端打包与部署&#xff08;使用 npm&#xff09;1. 确保 Node.js 和 npm…
阅读更多...
Oracle 数据库安装和配置详解

Oracle 数据库安装和配置详解

Oracle 数据库安装和配置详解 Oracle 数据库是一款功能强大、广泛使用的企业级关系数据库管理系统 (RDBMS)&#xff0c;适用于处理大型数据库和复杂事务。本文将介绍如何在 Linux 和 Windows 环境下安装 Oracle 数据库&#xff0c;并对其进行基本配置&#xff0c;帮助开发者快…
阅读更多...
深入理解MySQL InnoDB中的B+索引机制

深入理解MySQL InnoDB中的B+索引机制

目录 一、InnoDB中的B 树索引介绍 二、聚簇索引 &#xff08;一&#xff09;使用记录主键值的大小进行排序 页内记录排序 页之间的排序 目录项页的排序 &#xff08;二&#xff09;叶子节点存储完整的用户记录 数据即索引 自动创建 &#xff08;三&#xff09;聚簇索引…
阅读更多...
[ 蓝桥 ·算法双周赛 ] 第 19 场 小白入门赛

[ 蓝桥 ·算法双周赛 ] 第 19 场 小白入门赛

&#x1f525;博客介绍&#xff1a; EvLast &#x1f3a5;系列专栏&#xff1a; <<数据结构与算法>> << 算法入门>> << C项目>> &#x1f3a5; 当前专栏: << 算法入门>> 专题 : 帮助小白快速入门算法竞赛 &#x1f44d…
阅读更多...
最新文章

Copyright @ 2022~2023