数据结构C语言练习(两个队列实现栈)

引入：

在算法和数据结构领域，栈和队列是两种基础且重要的数据结构。栈遵循后进先出（LIFO）原则，而队列遵循先进先出（FIFO）原则。有时候，我们会遇到一个有趣的问题：如何使用两个队列来实现栈的操作？本文将详细解释这个问题的解决方案，并对每一个栈操作函数进行深入讲解。

 练习题：

1. 力扣 225. 用二个队列实现栈

 

问题背景

栈是一种只能在一端进行插入和删除操作的数据结构，这一端被称为栈顶。而队列则是在一端插入元素（队尾），在另一端删除元素（队头）。现在，我们要使用两个队列来模拟栈的行为，实现栈的基本操作：入栈（push）、出栈（pop）、获取栈顶元素（top）以及判断栈是否为空（empty）。

数据结构定义

在开始实现栈操作之前，我们需要定义队列和栈的数据结构。以下是具体的代码：

typedef int QDataType;
typedef struct QListNode {struct QListNode* _next;QDataType _data;
} QListNode;typedef struct Queue {struct QListNode* _front;struct QListNode* _rear;
} Queue;typedef struct {Queue q1;Queue q2;
} MyStack;

• QListNode 是队列的节点结构，包含一个指向下一个节点的指针 _next 和存储的数据 _data。
• Queue 结构体包含两个指针，_front 指向队列的头节点，_rear 指向队列的尾节点。
• MyStack 结构体包含两个队列 q1 和 q2，我们将通过这两个队列来模拟栈的操作。

队列基础操作（详细队列讲解）

在实现栈操作之前，我们需要先实现队列的一些基础操作，如初始化、入队、出队、判断队列是否为空等。以下是这些基础操作的代码：

// 初始化队列 
void QueueInit(Queue* q) {assert(q);q->_front = q->_rear = NULL;
}// 队尾入队列 
void QueuePush(Queue* q, QDataType data) {assert(q);QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));if (newnode == NULL) {perror("Fail malloc");exit(1);}newnode->_data = data;newnode->_next = NULL;if (q->_front == NULL) {q->_front = q->_rear = newnode;}else {q->_rear->_next = newnode;q->_rear = newnode;} 
}// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q) {return q->_front == NULL;
}// 队头出队列 
void QueuePop(Queue* q) {assert(!QueueEmpty(q));if (q->_front == q->_rear) {free(q->_front);q->_front = q->_rear = NULL;}else {QListNode* next = q->_front->_next;free(q->_front);q->_front = next;}
}// 获取队列头部元素 
QDataType QueueFront(Queue* q) {assert(!QueueEmpty(q));return q->_front->_data;
}// 获取队列队尾元素 
QDataType QueueBack(Queue* q) {assert(!QueueEmpty(q));return q->_rear->_data;
}// 获取队列中有效元素个数 
int QueueSize(Queue* q) {assert(!QueueEmpty(q));QListNode* pcur = q->_front;int size = 0;while (pcur) {pcur = pcur->_next;size++;}return size;
}// 销毁队列 
void QueueDestroy(Queue* q) {assert(q);QListNode* pcur = q->_front;while (pcur) {QListNode* next = pcur->_next;free(pcur);pcur = next;}q->_front = q->_rear = NULL;
}

这些基础操作是实现栈操作的基础，我们将在后续的栈操作中使用它们。

栈操作实现

1. myStackCreate：创建栈

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

• 功能：创建一个新的栈实例。
• 步骤：
  1. 使用 malloc 函数为 MyStack 结构体分配内存。
  2. 调用 QueueInit 函数分别初始化 q1 和 q2 两个队列。
  3. 返回指向新创建的栈实例的指针。

2. myStackPush：入栈操作

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

• 功能：将元素 x 压入栈中。
• 步骤：
  1. 检查 q1 是否为空。
  2. 如果 q1 不为空，则将元素 x 插入到 q1 队列的队尾。
  3. 如果 q1 为空，则将元素 x 插入到 q2 队列的队尾。

3. myStackPop：出栈操作

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

 

 

• 功能：弹出栈顶元素并返回其值。
• 步骤：
  1. 确定哪个队列为空（emp），哪个队列不为空（noneEmp）。
  2. 将 noneEmp 队列中除最后一个元素外的所有元素依次转移到 emp 队列中。
  3. 保存 noneEmp 队列中最后一个元素的值。
  4. 弹出 noneEmp 队列中的最后一个元素。
  5. 返回保存的元素值。

4. myStackTop：获取栈顶元素

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

• 功能：返回栈顶元素的值，但不弹出该元素。
• 步骤：
  1. 检查 q1 是否为空。
  2. 如果 q1 不为空，则返回 q1 队列的队尾元素的值。
  3. 如果 q1 为空，则返回 q2 队列的队尾元素的值。

5. myStackEmpty：判断栈是否为空

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

• 功能：判断栈是否为空。
• 步骤：
  1. 检查 q1 和 q2 两个队列是否都为空。
  2. 如果两个队列都为空，则返回 true，表示栈为空；否则返回 false。

6. myStackFree：释放栈内存

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

• 功能：释放栈实例占用的内存。
• 步骤：
  1. 调用 QueueDestroy 函数分别销毁 q1 和 q2 两个队列。
  2. 使用 free 函数释放 MyStack 结构体占用的内存。

总结

通过使用两个队列，我们成功地模拟了栈的基本操作。这种实现方式虽然在时间复杂度上可能不如直接使用栈高效，但它展示了如何通过组合不同的数据结构来实现特定的功能。在实际应用中，我们可以根据具体的需求选择合适的数据结构和算法。

希望本文能够帮助你理解如何使用两个队列来实现栈操作，以及每个函数的具体实现原理。如果你有任何疑问或建议，欢迎在评论区留言。