当前位置： 首页 > article >正文

栈和队列相关题 ， 用队列实现栈， 用栈实现队列 ，设计循环队列 C/C++双版本

article 2024/12/24 11:26:11

文章目录

  • 1.用队列实现栈
  • 2.用栈实现队列
  • 3. 设计循环队列

1.用队列实现栈

225. 用队列实现栈

在这里插入图片描述

思路：

使用两个队列，始终保持一个队列为空。

  • 当我们需要进行压栈操作时，将数据压入不为空的队列中（若两个都为空，则随便压入一个队列）。
  • 当需要进行出栈操作时，将不为空的队列中的数据导入空队列，仅留下一个数据，这时将这个数据返回并且删除即可。
  • 判断栈是否为空，即判断两个队列是否同时为空。

在这里插入图片描述
C 代码：

typedef int QDataType;//队列中存储的元素类型

typedef struct QListNode
{
	struct QListNode* next;//指针域
	QDataType data;//数据域
}QListNode;

typedef struct Queue
{
	QListNode* head;//队头
	QListNode* tail;//队尾
}Queue;
//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	//起始时队列为空
	pq->head = NULL;
	pq->tail = NULL;
}

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

	QListNode* cur = pq->head;//接收队头
	//遍历链表，逐个释放结点
	while (cur)
	{
		QListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;//队头置空
	pq->tail = NULL;//队尾置空
}

//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));//申请新结点
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;//新结点赋值
	newnode->next = NULL;//新结点指针域置空
	if (pq->head == NULL)//队列中原本无结点
	{
		pq->head = pq->tail = newnode;//队头、队尾直接指向新结点
	}
	else//队列中原本有结点
	{
		pq->tail->next = newnode;//最后一个结点指向新结点
		pq->tail = newnode;//改变队尾指针指向
	}
}

//检测队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//检测队列是否为空

	if (pq->head->next == NULL)//队列中只有一个结点
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;
	}
	else//队列中有多个结点
	{
		QListNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;//改变队头指针指向
	}
}

//获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//检测队列是否为空

	return pq->head->data;//返回队头指针指向的数据
}

//获取队列尾部元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//检测队列是否为空

	return pq->tail->data;//返回队尾指针指向的数据
}

//获取队列中有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);

	QListNode* cur = pq->head;//接收队头
	int count = 0;//记录结点个数
	while (cur)//遍历队列
	{
		count++;
		cur = cur->next;
	}
	return count;//返回队列中的结点数
}


/*---以上代码是队列的基本功能实现，以下代码是题解主体部分---*/


typedef struct {
    Queue q1;
    Queue 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) {
    Queue* pEmpty = &obj->q1;//记录空队列
	Queue* pNoEmpty = &obj->q2;//记录非空队列
	if (!QueueEmpty(&obj->q1))
	{
		pEmpty = &obj->q2;
		pNoEmpty = &obj->q1;
	}

    //将非空队列中的数据放入空队列中，只留下一个数据
    while(QueueSize(pNoEmpty) > 1)
    {
        QueuePush(pEmpty,QueueFront(pNoEmpty));
        QueuePop(pNoEmpty);
    }

    int front = QueueFront(pNoEmpty);//获取目标数据
    QueuePop(pNoEmpty);//删除目标数据
    return front;
}

int myStackTop(MyStack* obj) {
    //获取非空队列的队尾数据
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

bool myStackEmpty(MyStack* obj) {
    //两个队列均为空，则MyStack为空
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);//释放第一个队列
	QueueDestroy(&obj->q2);//释放第二个队列
	free(obj);//释放MyStack
}

C++ 代码：

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;

    MyStack() {

    }

    void push(int x) {
        if (!q1.empty())
        {
            q1.push(x);
        }
        else
        {
            q2.push(x);
        }
    }

    int pop() {
        queue<int>* qempty = &q1;
        queue<int>* qnoempty = &q2;
        if (!q1.empty())
        {
            qempty = &q2;
            qnoempty = &q1;
        }

        while (qnoempty->size() > 1)
        {
            qempty->push(qnoempty->front());
            qnoempty->pop();
        }
        int top = qnoempty->front();
        qnoempty->pop();

        return top;
    }

    int top() {
        if (!q1.empty())
        {
            return q1.back();
        }
        else
        {
            return q2.back();
        }
    }

    bool empty() {
        return q1.empty() && q2.empty();
    }
};

2.用栈实现队列

232. 用栈实现队列

在这里插入图片描述

思路：

使用两个栈，第一个栈只用于数据的输入，第二个栈只用于数据的输出。
当需要输出数据，但第二个栈为空时，先将第一个栈中的数据一个一个导入到第二个栈，然后第二个栈再输出数据即可。

在这里插入图片描述
C代码：

typedef int STDataType;//栈中存储的元素类型

typedef struct Stack
{
	STDataType* a;//栈
	int top;//栈顶
	int capacity;//容量，方便增容
}Stack;

//初始化栈
void StackInit(Stack* pst)
{
	assert(pst);

	pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);//初始化栈可存储4个元素
	pst->top = 0;//初始时栈中无元素，栈顶为0
	pst->capacity = 4;//容量为4
}

//销毁栈
void StackDestroy(Stack* pst)
{
	assert(pst);

	free(pst->a);//释放栈
	pst->a = NULL;//及时置空
	pst->top = 0;//栈顶置0
	pst->capacity = 0;//容量置0
}

//入栈
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);

	if (pst->top == pst->capacity)//栈已满，需扩容
	{
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity *= 2;//栈容量扩大为原来的两倍
	}
	pst->a[pst->top] = x;//栈顶位置存放元素x
	pst->top++;//栈顶上移
}

//检测栈是否为空
bool StackEmpty(Stack* pst)
{
	assert(pst);

	return pst->top == 0;
}

//出栈
void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));//检测栈是否为空

	pst->top--;//栈顶下移
}

//获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));//检测栈是否为空

	return pst->a[pst->top - 1];//返回栈顶元素
}

//获取栈中有效元素个数
int StackSize(Stack* pst)
{
	assert(pst);

	return pst->top;//top的值便是栈中有效元素的个数
}


/*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/

typedef struct {
    Stack pushST;//插入数据时用的栈
    Stack popST;//删除数据时用的栈
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));//申请一个队列类型
    StackInit(&obj->pushST);//初始化pushST
    StackInit(&obj->popST);//初始化popST

    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST, x);//插入数据，向pushST插入
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popST))//popST为空时，需先将pushST中数据导入popST
    {
        while(!StackEmpty(&obj->pushST))//将pushST数据全部导入popST
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);//返回popST栈顶的元素
}

int myQueuePop(MyQueue* obj) {
    int top = myQueuePeek(obj);
    StackPop(&obj->popST);//删除数据，删除popST中栈顶的元素
    return top;
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);//两个栈均为空，则“队列”为空
}

void myQueueFree(MyQueue* obj) {
    //先释放两个栈，再释放队列的结构体类型
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}

C++ 代码：

class MyQueue {
public:
    stack<int> pushST;
    stack<int> popST;
    MyQueue() {
        
    }
    
    void push(int x) {
        pushST.push(x);
    }
    
    int pop() {
        int top = this->peek();
        popST.pop();
        return top;
    }
    
    int peek() {
        if(popST.empty())
        {
            while(!pushST.empty())
            {
                popST.push(pushST.top());
                pushST.pop();
            }
        }
        
        return popST.top();
    }
    
    bool empty() {
        return pushST.empty() && popST.empty();
    }
};

3. 设计循环队列

622. 设计循环队列

在这里插入图片描述

思路：

在环形队列中，队列为空时，队头队尾指向同一个位置。当队列不为空时，队头指向插入的第一个数据，队尾指向最后一个数据的下一个位置。当tail+1等于front时，说明环形队列已满。
 
注意：
 环形队列的队尾不能像常规队列中队尾一样指向最后一个数据，如果这样的话，我们将不能区别环形队列的状态是空还是满，因为此时队头和队尾都指向同一个位置。这就意味着，我们必须留出一个空间，这个空间不能存放数据，这样我们才能很好的区别环形队列的状态是空还是满

在这里插入图片描述
我们如果用一个数组来实现这个环形队列的话，上面这三种状态就对应于以下三种状态：

在这里插入图片描述

可以看出，此时这个数组和环形完全扯不上关系，这其实很简单，我们只需注意判断两个地方：

  1. 当指针指向整个数组的后方的时候，让该指针重新指向数组的第一个元素。
  2. 当指针指向整个数组的前方的时候，让该指针直接指向数组最后一个有效元素的后面。

在这里插入图片描述
C 代码：

typedef struct {
    int* a;//数组模拟环形队列
    int k;//队列可存储的有效数据总数
    int front;//队头
    int tail;//队尾的后一个位置
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请一个环形队列
    obj->a = (int*)malloc(sizeof(int)*(k+1));//开辟队列空间
    //初始时，队头和队尾均为0
    obj->front = 0;
    obj->tail = 0;
    obj->k = k;//设置队列可存储的有效数据个数
    
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->tail;//当front和tail指向同一位置时，队列为空
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int tailnext = obj->tail+1;
    if(tailnext == obj->k+1)//当指针指到队列末尾时，指针返回队列开头，使队列循环
        tailnext = 0;
    return tailnext == obj->front;//当指针指到队列末尾时，指针返回队列开头，使队列循环
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))//队列已满，不能再插入数据
        return false;
    
    obj->a[obj->tail] = value;//插入数据
    obj->tail++;
    if(obj->tail == obj->k+1)//使队列循环
        obj->tail = 0;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))//当队列为空时，无法再删除数据
        return false;

    obj->front++;
    if(obj->front == obj->k+1)
        obj->front = 0;

    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//返回tail-1指向位置的数据
    {
        int tailPrev = obj->tail-1;

        if(tailPrev == -1)//使队列循环
            tailPrev = obj->k;
        
        return obj->a[tailPrev];
    }
}


void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);//先释放动态开辟的数组
    free(obj);//再释放动态开辟的结构体
}

C++ 代码：

class MyCircularQueue {
public:
    vector<int> _a;//数组模拟环形队列   
    int _k;//队列可存储的有效数据总数
    int _front;//队头
    int _tail;//队尾的后一个位置
    MyCircularQueue(int k) {
        _k = k;
        _front = _tail = 0;
        _a = vector<int>(k+1);
    }
    
    bool enQueue(int value) {
        if(isFull()) 
            return false;
        _a[_tail] = value;
        _tail++;
        _tail%=(_k+1);
        return true;
    }
    
    bool deQueue() {
        if(isEmpty())
            return false;
        _front++;
        _front%=(_k+1);
        return true;
    }
    
    int Front() {
        if(isEmpty())
            return -1;
        return _a[_front % (_k+1)];
    }
    
    int Rear() {
        if(isEmpty())
            return -1;
        int tailprev = _tail-1;
        return _a[tailprev == -1 ? _k : tailprev];
    }
    
    bool isEmpty() {
        return _front == _tail;
    }
    
    bool isFull() {
        return ((_tail+1) % (_k+1)) == _front;
    }
};

http://www.kler.cn/a/383384.html

相关文章：

  • vscode添加全局宏定义
  • 如何学习Trustzone
  • UWB无载波通信技术，UWB定位系统源码
  • Hadoop yarn安装
  • Day-03 Vue（生命周期、生命周期钩子八个函数、工程化开发和脚手架、组件化开发、根组件、局部注册和全局注册的步骤）
  • Idean 处理一个项目引用另外一个项目jar 但jar版本低的问题
  • C#字符串的不可变性：内存管理与线程安全的优势分析
  • 你要的增量更新来了：微软GraphRAG 0.4.0
  • DPDK(F-Stack) 实现UDP通信
  • 印刷质量检测笔记
  • TS（类 接口 泛型）
  • 【Python编程实例】-深入理解Python线程安全
  • 【机器学习】随机森林算法
  • 网页，app，微信小程序互相跳转
  • 传统的问答系统；；基于生成的问答系统；；基于检索增强生成的问答系统RAG
  • 工业4.0时代下的分布式IO模块
  • 第二话：JS中new操作符的原理
  • 如何将自己的程序文件上传至Github
  • Android——从相机/相册获取图片
  • 无人机避障——大疆与Airsim中的角速度信息订阅获取
  • [免费]SpringBoot+Vue(高校)学籍管理系统【论文+源码+SQL脚本】
  • 【原创】java+ssm+mysql收纳培训网系统设计与实现
  • 【Ajax】跨域
  • StarRocks 在 Shopee 数据产品的实践
  • 应用链风口下，一键发链该如何选择？
  • 数据结构模拟题[十]