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

引言

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

一、栈（Stack）

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

C语言实现栈：

// 支持动态增长的栈
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);
	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语言实现队列：

#include <stdio.h>  
#include <stdlib.h>  
#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的更新方式。）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
 
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操作，以及如何在适当的时候交换两个栈的角色。）

// 支持动态增长的栈
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);
	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);
}

五、队列实现栈

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

代码实现：

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

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