欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

在线OJ之用队列实现栈及设计循环队列

2026-03-11 分类：服务器技术 阅读(23) 评论(0)

1.用队列去实现栈

https://leetcode.cn/problems/implement-stack-using-queues/description/ 在这里插入图片描述 整体思路：

  • 我们使用两个队列 q1 和 q2 来模拟栈。核心思想是在出栈时调整顺序：

  • 入栈：直接将元素放入非空队列（如果两个都空，则放入 q2）。这样所有元素都按入栈顺序排列在同一个队列中，且队尾就是最后入栈的元素（栈顶）。

  • 出栈：需要弹出最后一个入队的元素（队尾），但队列只能从队头出。所以我们将非空队列中除了最后一个元素外的所有元素移到另一个空队列中，然后弹出最后一个元素。这样，原来的空队列变成了新的存储队列，原来的非空队列变空，角色互换。

  • 取栈顶：直接返回非空队列的队尾元素（因为队尾就是栈顶）。

  • 判空：两个队列都空则栈空。

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

typedef intQDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;

typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//插入
void QueuePush(Queue* qp, QDataType data);
//删除
void QueuePop(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);
//获取元素个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);

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

void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* curr = pq->head;
while (curr)
{
QNode* next = curr->next;
free(curr);
curr = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}

void QueuePush(Queue* pq, QDataType data)
{
assert(pq);
QNode* newhead = (QNode*)malloc(sizeof(QNode));
if (newhead == NULL)
{
perror("malloc fail");
return;
}
newhead->next = NULL;
newhead->val = data;
//无节点
if (pq->tail == NULL)
{
pq->head = pq->tail = newhead;
}
else
{
pq->tail->next = newhead;
pq->tail = newhead;
}
pq->size++;
}

void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
{
pq->tail = NULL;
}
pq->size—;
}

QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
return pq->head->val;
}

QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
return pq->tail->val;
}

int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}

bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}

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* empty = &obj->q1;
Queue* noempty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
noempty = &obj->q1;
}
while(QueueSize(noempty)>1)
{
QueuePush(empty,QueueFront(noempty));
QueuePop(noempty);
}
int top = QueueFront(noempty);
QueuePop(noempty);
return top;
}

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);
}

/**
* Your MyStack struct will be instantiated and called as such:
* MyStack* obj = myStackCreate();
* myStackPush(obj, x);

* int param_2 = myStackPop(obj);

* int param_3 = myStackTop(obj);

* bool param_4 = myStackEmpty(obj);

* myStackFree(obj);
*/

代码分块详解：

1.1队列的实现

typedef int QDataType;
typedef struct QueueNode {
struct QueueNode* next;
QDataType val;
} QNode;

typedef struct Queue {
QNode* head; // 队头指针
QNode* tail; // 队尾指针
int size; // 元素个数
} Queue;

队列的常用操作：

  • QueueInit：初始化队列，头尾置空，size=0。

  • QueueDestroy：释放所有节点内存。

  • QueuePush：在队尾插入元素。

  • QueuePop：从队头删除元素。

  • QueueFront：返回队头元素。

  • QueueBack：返回队尾元素。

  • QueueSize：返回元素个数。

  • QueueEmpty：判断队列是否为空。

1.2栈的结构定义

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

1.3创建栈

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

  • 动态分配一个 MyStack 结构体。

  • 初始化两个队列。

  • 返回指针

1.4入栈

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

  • 如果 q1 非空，则将新元素入队到 q1。

  • 否则（即 q1 为空，可能 q2 非空或两个都空），将新元素入队到 q2。

  • 这样，所有元素始终只存在于一个队列中，另一个队列为空。这个非空队列的队尾就是最后入栈的元素（栈顶）

总之，核心策略为： 总是将新元素放入当前非空队列（如果两个都空，则放入q2）。它保证了所有元素都在同一个队列中。

1.5出栈

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

步骤解析：

  • 找出空队列和非空队列：先假设 q1 是空队列，q2 是非空队列。然后检查 q1 是否真的非空？如果是，则交换：让 empty 指向 q2，noempty 指向 q1。这样 empty 总是指向当前的空队列，noempty 指向当前存储元素的队列。

  • 将非空队列的前 n-1 个元素移到空队列：循环将 noempty 的队头元素取出，放入 empty，然后从 noempty 中弹出该元素。直到 noempty 只剩下一个元素（即栈顶元素）。

  • 记录并弹出栈顶元素：此时 noempty 中唯一的元素就是栈顶，用 QueueFront 获取其值，然后 QueuePop 将其弹出。

  • 返回栈顶值。

关键点：

循环结束后，noempty 变为空，而 empty 中包含了除栈顶外的所有元素，且顺序与原顺序一致（因为我们是按原顺序依次移过去的）。这样，原来的空队列现在变成了新的存储队列，而原来的非空队列变成了空。下一次 push 时，就会将新元素放入这个新的非空队列。

1.6取栈顶

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

判断哪个队列非空，然后返回该队列的队尾元素（因为队尾就是最后入栈的元素）。

1.7判空

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

两个队列都空时，栈为空。

1.8释放栈

void myStackFree(MyStack* obj) {
QueueDestroy(&(obj->q1));
QueueDestroy(&(obj->q2));
free(obj);
}

先销毁两个队列（释放链表节点），再释放栈结构体本身。

1.9示例模拟

以题目给的例子：push 1, push 2, top, pop, empty 来演示。

1.初始化：q1 = [], q2 = [], size=0。

2.push(1)：q1空，所以放入q2。q2 = [1], q1空。

3.push(2)：q1仍空，放入q2。q2 = [1,2], q1空。

4.top()：q1空，q2非空，返回q2队尾 2。

pop()：

  • empty指向q1，noempty指向q2（因为q1空，不交换）。

  • while循环：q2有2个元素，大于1，所以将q2队头1移到q1，然后弹出1。此时q2=[2]，q1=[1]。

  • 循环结束，noempty=q2只有一个元素2，记录top=2，弹出它。q2变为空。

  • 返回2。此时q1=[1]，q2空。

  • empty()：q1非空，返回false。

2.设计循环队列

https://leetcode.cn/problems/design-circular-queue/description/ 在这里插入图片描述

typedef struct {
int* arr;
int head;
int tail;
int size;
int capacity;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->size == 0;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
return obj->size == obj->capacity;
}

MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->arr = (int*)malloc(sizeof(int)*k);
obj->head = obj->tail = obj->size = 0;
obj->capacity = k;
return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->arr[obj->tail] = value;
obj->tail = (obj->tail+1)%(obj->capacity);
obj->size++;
return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->head = (obj->head+1)%(obj->capacity);
obj->size—;
return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return –1;
}
return obj->arr[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return –1;
}
return (obj->tail == 0)? (obj->arr[obj->capacity–1]):(obj->arr[obj->tail–1]);
}

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

/**
* Your MyCircularQueue struct will be instantiated and called as such:
* MyCircularQueue* obj = myCircularQueueCreate(k);
* bool param_1 = myCircularQueueEnQueue(obj, value);

* bool param_2 = myCircularQueueDeQueue(obj);

* int param_3 = myCircularQueueFront(obj);

* int param_4 = myCircularQueueRear(obj);

* bool param_5 = myCircularQueueIsEmpty(obj);

* bool param_6 = myCircularQueueIsFull(obj);

* myCircularQueueFree(obj);
*/

常见方法是额外使用一个变量 size 来记录当前队列中的元素个数。费，数组容量直接等于用户指定的 k。判断空和满的条件非常简单：

  • 空：size == 0

  • 满：size == k

指针 head 和 tail 的含义：

  • head：指向队首元素的位置

  • tail：指向队尾元素的下一个位置（即下一个要插入的位置） 各操作详解：

2.1 创建队列

MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->arr = (int*)malloc(sizeof(int) * k);
obj->head = 0;
obj->tail = 0;
obj->size = 0;
obj->capacity = k;
return obj;
}

  • 分配 k 个整型空间，不需要多开。

  • 初始化头尾指针为0，size 为0。

2.2 判断队列是否为空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->size == 0;
}

这个还是蛮简单的，就是如果obj->size == 0，那么就条件为真，返回true，反之亦然。

2.3判断队列是否已满

bool myCircularQueueIsFull(MyCircularQueue* obj) {
return obj->size == obj->capacity;
}

这个和上面的那个同理。

2.4入队

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj)) {
return false;
}
obj->arr[obj->tail] = value;
obj->tail = (obj->tail + 1) % obj->capacity;
obj->size++;
return true;
}

  • 先检查是否已满。

  • 将值放入当前 tail 位置，然后 tail 后移一位（绕回）。

  • size 加1

2.5出队

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj)) {
return false;
}
obj->head = (obj->head + 1) % obj->capacity;
obj->size—;
return true;
}

  • 先检查是否为空。

  • 直接将 head 后移一位，逻辑上删除队首元素。

  • size 减1

2.6获取队首元素

int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj)) {
return –1;
}
return obj->arr[obj->head];
}

没啥好说。

2.7获取队尾元素

int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj)) {
return –1;
}
// 注意：tail 指向的是下一个插入位置，所以队尾是 tail 的前一个位置
// 需要处理 tail == 0 的情况，此时前一个位置是 capacity-1
int prev = (obj->tail – 1 + obj->capacity) % obj->capacity;
return obj->arr[prev];
}

这里要注意一点，因为 tail 始终指向空位，所以队尾元素在 tail 的前一个位置，需要取模处理。 或者我们用三目操作符也可，如下：

int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return –1;
}
return (obj->tail == 0)? (obj->arr[obj->capacity–1]):(obj->arr[obj->tail–1]);
}

2.8释放队列

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

赞(0)
未经允许不得转载：171主机测评 » 在线OJ之用队列实现栈及设计循环队列
分享到： 更多 (0)
标签：

相关推荐

评论 抢沙发

取消

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

热门标签

#人工智能(59412)#python(20142)#开发语言(16889)#java(15496)#运维(15377)#linux(14964)#大数据(14591)#服务器(13075)#算法(11793)#前端(10919)#网络(9385)#ai(8938)#数据库(8909)#c++(8181)#课程设计(6804)#学习(6780)#机器学习(6720)#区块链(5924)#OpenClaw(5390)#后端(5163)#spring boot(5014)#深度学习(4957)#c语言(4382)#毕业设计(4294)#数据结构(4205)#安全(4074)#docker(3933)#架构(3864)#javascript(3810)#大模型(3658)

热门文章

最新文章

归档

分类