2026-07-09 22:34:16

C语言中的循环队列与栈、队列之间的转换实现

引言在数据结构的学习中，栈（Stack）和队列（Queue）是两个非常重要的概念。它们分别遵循着后进先出（LIFO）和先进先出（FIFO）的原则。在某些情况下，我们可能需要通过栈来模拟队列，或者通过队列来模拟栈的行为。本文将详细介绍这两种数据结构，并提供相应的C语言实现代码和图解。

一、栈（Stack）栈是一种后进先出（LIFO）的数据结构，只允许在一端进行操作，这一端被称为栈顶（top）。栈的基本操作包括入栈（push）和出栈（pop）。

C语言实现栈：

代码语言：javascript复制// 支持动态增长的栈

typedef int STDataType;

typedef struct Stack

{

STDataType* _a;

int _top; // 栈顶

int _capacity; // 容量

}Stack;

// 初始化栈

void StackInit(Stack* ps)

{

assert(ps);

ps->_a = NULL;

//top指向栈顶数据的下一个位置

ps->_top = 0;

//top指向栈顶数据

//ps->_top = -1;

ps->_capacity = 0;

}

// 入栈

void StackPush(Stack* ps, STDataType data)

{

assert(ps);

if (ps->_top == ps->_capacity)

{

int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;

STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * (sizeof(STDataType)));

if (tmp == NULL)

{

perror("realloc fail");

return;

}

ps->_a = tmp;

ps->_capacity = newcapacity;

}

ps->_a[ps->_top] = data;

ps->_top++;

}

// 出栈

void StackPop(Stack* ps)

{

assert(ps);

assert(ps->_top > 0);

ps->_top--;

}

// 获取栈顶元素

STDataType StackTop(Stack* ps)

{

assert(ps);

assert(ps->_top > 0);

return ps->_a[ps->_top - 1];

}

// 获取栈中有效元素个数

int StackSize(Stack* ps)

{

assert(ps);

return ps->_top;

}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0

int StackEmpty(Stack* ps)

{

assert(ps);

return ps->_top == 0;

}

// 销毁栈

void StackDestroy(Stack* ps)

{

assert(ps);

free(ps->_a);

ps->_a = NULL;

ps->_top = ps->_capacity = 0;

}栈的图解：

（可以想象一个竖直的容器，新元素从顶部加入，也是从顶部取出。）

二、队列（Queue）队列是一种先进先出（FIFO）的数据结构，只允许在两端进行操作，一端为队头（front），另一端为队尾（rear）。队列的基本操作包括入队（enqueue）和出队（dequeue）。C语言实现队列：

代码语言：javascript复制#include

#include

#define MAX_SIZE 100

typedef struct

{

int data[MAX_SIZE];

int front, rear;

} Queue;

void initQueue(Queue *q)

{

q->front = q->rear = -1;

}

int isFull(Queue *q)

{

return (q->rear + 1) % MAX_SIZE == q->front;

}

int isEmpty(Queue *q)

{

return q->front == -1;

}

void enqueue(Queue *q, int value)

{

if (!isFull(q))

{

q->data[++q->rear] = value;

}

else

{

printf("Queue is full!\n");

}

int dequeue(Queue *q)

{

if (!isEmpty(q))

{

int value = q->data[q->front++];

if (q->front > q->rear) q->front = q->rear = -1; // 处理队列为空的情况

return value;

} else

{

printf("Queue is empty!\n");

return -1;

}

// ... 其他队列操作函数 ...队列的图解：

（可以想象一个水平的容器，新元素从尾部加入，从头部取出。）

三、循环队列循环队列是对普通队列的一种改进，通过取模运算实现队首和队尾的循环，从而更高效地利用存储空间。相当于队列头尾相接,同时容量固定.

（代码与上面的队列实现类似，主要区别在于isFull和isEmpty的判断，以及front和rear的更新方式。）

代码语言：javascript复制#include

#include

typedef struct

{

int* a;

int head; //指向头

int tail; //指向尾下一个

int k; //容量

} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k)

{

MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

if (obj == NULL)

{

return;

}

//多开一个解决假溢出问题

obj->a = (int*)malloc(sizeof(int)*(k + 1));

obj->head = 0;

obj->tail = 0;

obj->k = k;

return obj;

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)

{

return obj->head == obj->tail;

}

bool myCircularQueueIsFull(MyCircularQueue* obj)

{

return (obj->tail + 1) % (obj->k + 1) == obj->head;

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)

{

if (myCircularQueueIsFull(obj))

{

return false;

}

obj->a[obj->tail] = value;

obj->tail++;

obj->tail %= (obj->k + 1);

return true;

}

bool myCircularQueueDeQueue(MyCircularQueue* obj)

{

if (myCircularQueueIsEmpty(obj))

{

return false;

}

++obj->head;

obj->head %= (obj->k + 1);

return true;

}

int myCircularQueueFront(MyCircularQueue* obj)

{

if (myCircularQueueIsEmpty(obj))

{

return -1;

}

else

{

return obj->a[obj->head];

}

int myCircularQueueRear(MyCircularQueue* obj)

{

if (myCircularQueueIsEmpty(obj))

{

return -1;

}

else

{

return obj->a[(obj->tail + obj->k) % (obj->k + 1)];

}

void myCircularQueueFree(MyCircularQueue* obj)

{

free(obj->a);

free(obj);

}四、栈实现队列虽然栈是后进先出的数据结构，但我们可以通过两个栈（一个作为输入栈，一个作为输出栈）来模拟队列的先进先出特性。

代码实现：

（主要涉及两个栈的push和pop操作，以及如何在适当的时候交换两个栈的角色。）

代码语言：javascript复制// 支持动态增长的栈

typedef int STDataType;

typedef struct Stack

{

STDataType* _a;

int _top; // 栈顶

int _capacity; // 容量

}Stack;

// 初始化栈

void StackInit(Stack* ps)

{

assert(ps);

ps->_a = NULL;

//top指向栈顶数据的下一个位置

ps->_top = 0;

//top指向栈顶数据

//ps->_top = -1;

ps->_capacity = 0;

}

// 入栈

void StackPush(Stack* ps, STDataType data)

{

assert(ps);

if (ps->_top == ps->_capacity)

{

int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;

STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * (sizeof(STDataType)));

if (tmp == NULL)

{

perror("realloc fail");

return;

}

ps->_a = tmp;

ps->_capacity = newcapacity;

}

ps->_a[ps->_top] = data;

ps->_top++;

}

// 出栈

void StackPop(Stack* ps)

{

assert(ps);

assert(ps->_top > 0);

ps->_top--;

}

// 获取栈顶元素

STDataType StackTop(Stack* ps)

{

assert(ps);

assert(ps->_top > 0);

return ps->_a[ps->_top - 1];

}

// 获取栈中有效元素个数

int StackSize(Stack* ps)

{

assert(ps);

return ps->_top;

}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0

int StackEmpty(Stack* ps)

{

assert(ps);

return ps->_top == 0;

}

// 销毁栈

void StackDestroy(Stack* ps)

{

assert(ps);

free(ps->_a);

ps->_a = NULL;

ps->_top = ps->_capacity = 0;

}

//leetcode

typedef struct

{

Stack pushst;

Stack popst;

} MyQueue;

MyQueue* myQueueCreate()

{

MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));

if (obj == NULL)

{

return;

}

StackInit(&(obj->popst));

StackInit(&(obj->pushst));

return obj;

}

void myQueuePush(MyQueue* obj, int x)

{

StackPush(&(obj->pushst), x);

}

int myQueuePeek(MyQueue* obj)

{

if (StackEmpty(&(obj->popst)))

{

//倒数据

while (!StackEmpty(&(obj->pushst)))

{

int top = StackTop(&(obj->pushst));

StackPush(&(obj->popst), top);

StackPop(&(obj->pushst));

}

return StackTop(&(obj->popst));

}

int myQueuePop(MyQueue* obj)

{

int front = myQueuePeek(obj);

StackPop(&(obj->popst));

return front;

}

bool myQueueEmpty(MyQueue* obj)

{

return StackEmpty(&(obj->popst)) && StackEmpty(&(obj->pushst));

}

void myQueueFree(MyQueue* obj)

{

StackDestroy(&(obj->popst));

StackDestroy(&(obj->pushst));

free(obj);

}五、队列实现栈队列是先进先出的数据结构，但通过两个队列（或者一个队列和一个辅助栈）也可以模拟栈的后进先出特性。

代码实现：

代码语言：javascript复制typedef char QDataType;

typedef struct QueueNode

{

struct QueueNode* next;

QDataType val;

}QNode;

typedef struct Queue

{

QNode* phead;

QNode* ptail;

int size;

}Queue;

void QueueInit(Queue* pq)

{

assert(pq);

pq->phead = NULL;

pq->ptail = NULL;

pq->size = 0;

}

void QueueDestroy(Queue* pq)

{

assert(pq);

QNode* cur = pq->phead;

while (cur)

{

QNode* next = cur->next;

free(cur);

cur = next;

}

pq->phead = pq->ptail = NULL;

pq->size = 0;

}

// 队尾插入

void QueuePush(Queue* pq, QDataType x)

{

assert(pq);

QNode* newnode = (QNode*)malloc(sizeof(QNode));

if (newnode == NULL)

{

perror("malloc fail");

return;

}

newnode->next = NULL;

newnode->val = x;

if (pq->ptail == NULL)

{

pq->phead = pq->ptail = newnode;

}

else

{

pq->ptail->next = newnode;

pq->ptail = newnode;

}

pq->size++;

}

// 队头删除

void QueuePop(Queue* pq)

{

assert(pq);

assert(pq->size != 0);

/*QNode* next = pq->phead->next;

free(pq->phead);

pq->phead = next;

if (pq->phead == NULL)

pq->ptail = NULL;*/

// 一个节点

if (pq->phead->next == NULL)

{

free(pq->phead);

pq->phead = pq->ptail = NULL;

}

else // 多个节点

{

QNode* next = pq->phead->next;

free(pq->phead);

pq->phead = next;

}

pq->size--;

}

QDataType QueueFront(Queue* pq)

{

assert(pq);

assert(pq->phead);

return pq->phead->val;

}

QDataType QueueBack(Queue* pq)

{

assert(pq);

assert(pq->ptail);

return pq->ptail->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;

//leetcode

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* nonempty = &(obj->q2);

if (!QueueEmpty(&(obj->q1)))

{

nonempty = &(obj->q1);

empty = &(obj->q2);

}

//不为空前size-1导走,删除最后一个就是栈顶数据

while (QueueSize(nonempty) > 1)

{

QueuePush(empty, QueueFront(nonempty));

QueuePop(nonempty);

}

int top = QueueFront(nonempty);

QueuePop(nonempty);

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

}分享到这里,欢迎翻阅我的文章.

手机如何轻松设置横屏显示，提升使用体验
使用 iPod touch 远程控制您的家