【数据结构】_栈与队列经典算法OJ：栈与队列的互相实现

目录

1. 用队列实现栈

1.1 题目链接及描述

1.2 解题思路

1.3 程序

2. 用栈实现队列

2.1 题目链接及描述

2.2 解题思路

2.3 程序

---

1. 用队列实现栈

1.1 题目链接及描述

1. 题目链接 ： 225. 用队列实现栈 - 力扣（LeetCode）

2. 题目描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

1.2 解题思路

队列的特点是先进先出，栈的特点是后进先出。

（1）分析出栈操作的实现：

令第一个队列入队4个元素：1、2、3、4；

此时出栈要求出4，而当前队列只能出1。

思路：依次从第一个队列出队1、2、3元素，并依次入队第二个队列；

（出队直至第一个队列只剩一个元素，该元素就是出栈要求的元素）：

（2）分析入栈操作的实现：
基于（1），现假设需入栈5、6，考虑下一个需出栈的情况，若为栈则需出6，为了实现该效果，将5、6入第二个队列，再类似（1）步骤，将2~5元素依次入队第一个队列，再出队第二队列的6以实现目标效果：

总结：保持一个存数据，一个为空；

入数据则入非空队列，出数据则将前面若干个数据入队至另一空队列；

1.3 程序

由于C语言并未提供实现有队列的库，故队列需自行实现。

相关代码见下文：

【数据结构】_队列的结构与实现-CSDN博客文章浏览阅读495次，点赞8次，收藏4次。队列：只允许在一端进行数据的插入操作，在另一端进行数据的删除操作的特殊线性表，队列具有先进先出FIFO（First In First Out）的特点。（2）若队列仅剩一个元素，按当前无特殊情况处理的方法实现，则pq->ptail未置空，使得其成为野指针，故需对其进行单独处理。注：若采取设有头结点的单链表，可传一级指针，但仍然需传队尾结点指针，仍需要传递两个参数，总体而言依然较为麻烦。若将数组头视为队头，数组尾视为队尾，则插入对应尾插实现方便，但删除对应头删实现麻烦；出队列：进行删除操作的一端称为队头；https://blog.csdn.net/m0_63299495/article/details/145443895https://blog.csdn.net/m0_63299495/article/details/145443895完整解答程序如下：

typedef int QDataType;
typedef struct QueueNode {QDataType val;struct QueueNode* next;
}QNode;
typedef struct Queue {QNode* phead;QNode* ptail;int size;
}Queue;
// 初始化
void QueueInit(Queue* pq);
// 销毁
void QueueDestory(Queue* pq);
// 队尾插入
void QueuePush(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);
// 计算列表元素个数；
int QueueSize(Queue* pq);
// 取队头/队尾数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
// 判空
bool QueueEmpty(Queue* pq);// 初始化
void QueueInit(Queue* pq) {assert(pq);pq->phead = NULL;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->val = x;newNode->next = NULL;// 情况1：队列为空if (pq->ptail == NULL) {pq->phead = pq->ptail = newNode;}// 情况2：队列不为空：队尾插入else {pq->ptail->next = newNode;pq->ptail = newNode;}pq->size++;
}
// 队头删除
void QueuePop(Queue* pq) {assert(pq);assert(QueueSize(pq)!=0);// 情况1：队列仅一个结点if (pq->phead->next == NULL) {free(pq->phead);pq->phead = pq->ptail = NULL;}// 情况2：队列有多个结点else {QNode* pheadNext = pq->phead->next;free(pq->phead);pq->phead = NULL;pq->phead = pheadNext;}pq->size--;
}
// 计算列表元素个数；
int QueueSize(Queue* pq) {return pq->size;
}
// 取队头/队尾数据
QDataType QueueFront(Queue* pq) {assert(pq);assert(pq->phead);return pq->phead->val;
}
QDataType QueueBack(Queue* pq) {assert(pq);assert(pq->phead);return pq->ptail->val;
}
// 判空
bool QueueEmpty(Queue* pq) {assert(pq);return pq->size == 0;
}
// 销毁
void QueueDestory(Queue* pq) {assert(pq);QNode* cur = pq->phead;while (cur) {QNode* curNext = cur->next;free(cur);cur = NULL;cur = curNext;}pq->phead = pq->ptail = NULL;
}typedef struct {Queue q1;Queue q2;   
} MyStack;MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));if(pst == NULL){perror("malloc fail");return NULL;}QueueInit(&(pst->q1));QueueInit(&(pst->q2));return pst;
}void myStackPush(MyStack* obj, int x) {assert(obj);// 入队不为空的队列if(!QueueEmpty(&(obj->q1))){QueuePush(&(obj->q1),x);}else{QueuePush(&(obj->q2),x);}
}int myStackPop(MyStack* obj) {assert(obj);// 假设法确定空队列与非空队列Queue* empty=&(obj->q1);Queue* nonEmpty=&(obj->q2);if(!QueueEmpty(&(obj->q1))){empty=&(obj->q2);nonEmpty=&(obj->q1);}// 将非空队列前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) {QueueDestory(&(obj->q1));QueueDestory(&(obj->q2));free(obj);
}

注：关于本题中各结构体及指针的指向关系：

同时也由于结构体指针又作为另一结构体的成员变量，进行free时需要全部释放，防止因为需要释放空间的遗漏导致内存泄漏；

2. 用栈实现队列

2.1 题目链接及描述

题目链接：232. 用栈实现队列 - 力扣（LeetCode）

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true；否则，返回 false；

2.2 解题思路

栈的特点是后进先出，队列的特点是先进先出。

（1）分析出队列操作：

令第一个栈入栈1、2、3、4四个元素，此时队列要求出队1，但当前栈只能出栈4，

思路：依次从第一个栈出栈4、3、2，并令其入栈第二个栈，再出栈第一个栈的元素1即可；

（2）分析入队列操作：

令要实现的队列入队列5、6，将其入栈到第一个栈，而后将第一个栈视为push栈，仅用于入数据；将第二个栈视为pop栈，仅用于出数据。当pop栈为空但还要进行pop操作时，将push栈的元素依次出栈并入栈pop栈；

2.3 程序

由于C语言并未提供实现有栈的库，故栈需自行实现。

相关代码见下文：

【数据结构】_栈的结构与实现-CSDN博客文章浏览阅读296次，点赞3次，收藏7次。若top表示栈顶元素的下标，则初始化时(栈内无元素)，top=-1，插入时在a[top++]处入栈元素；若top表示栈顶元素的下一个元素的下标，则初始化时top为0，插入时在a[top]处入栈元素。1、若采用数组实现栈，则可将数组头视为栈底，数组尾视为栈顶，出入栈都在数组尾进行操作。3、若采用双链表实现栈，则无论将哪端视为栈底，出栈、入栈等方法的实现都非常方便；1、栈：一种特殊的线性表，只允许在固定的一端插入和删除数据；2、压栈：栈的插入操作叫做进栈、压栈、入栈。3、出栈：栈的删除操作叫做出栈。https://blog.csdn.net/m0_63299495/article/details/145428244https://blog.csdn.net/m0_63299495/article/details/145428244完整程序如下：

typedef int STDataType;
typedef struct Stack {// 动态开辟数组STDataType* a;// top表示栈顶元素的下一个元素的下标int top;int capacity;
}ST;
void STInit(ST* pst);
void STDestory(ST* pst);
// 压栈
void STPush(ST* pst,STDataType x);
// 出栈
void STPop(ST* pst);
// 获取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst);
// 获取栈元素个数
int STSize(ST* pst);typedef struct {ST pushst;ST popst;
}MyQueue;MyQueue* myQueueCreate();
void myQueuePush(MyQueue* obj, int x);
int myQueuePop(MyQueue* obj);
int myQueuePeek(MyQueue* obj);
bool myQueueEmpty(MyQueue* obj);
void myQueueFree(MyQueue* obj);// 初始化
void STInit(ST* pst) {assert(pst);pst->a = NULL;// top表示栈顶元素的下一个元素的下标pst->top = 0;// capacity表示栈内元素个数（等价于栈顶元素的下一个元素的下标）pst->capacity = 0;
}
// 销毁
void STDestory(ST* pst) {assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}
// 压栈
void STPush(ST* pst, STDataType x) {assert(pst);// 满则扩容if (pst->top == pst->capacity) {int newCapacity = pst->capacity == 0? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * (sizeof(STDataType)));if (tmp == NULL) {perror("realloc fail");return;}pst->a = tmp;pst->capacity = newCapacity;}// 入栈数据pst->a[pst->top] = x;pst->top++;
}
// 出栈
void STPop(ST* pst) {assert(pst);// 判栈非空assert(pst->top>0);pst->top--;
}
// 获取栈顶数据
STDataType STTop(ST* pst) {assert(pst);assert(pst->top>0);return pst->a[pst->top - 1];
}
// 判空
bool STEmpty(ST* pst) {if (pst->top == 0) {return true;}return false;//return pst->top == 0;
}
// 获取栈元素个数
int STSize(ST* pst) {assert(pst);return pst->top;
}MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));STInit(&(obj->pushst));STInit(&(obj->popst));return obj;
}void myQueuePush(MyQueue* obj, int x) {assert(obj);STPush(&(obj->pushst),x);
}int myQueuePop(MyQueue* obj) {assert(obj);// 借用myQueuePeek保证popst有数据int front=myQueuePeek(obj);STPop(&(obj->popst));return front;
}int myQueuePeek(MyQueue* obj) {assert(obj);// pop栈为空：倒数据if(STEmpty(&(obj->popst))){while(!STEmpty(&(obj->pushst))){STDataType top = STTop(&(obj->pushst));STPop(&(obj->pushst));STPush(&(obj->popst),top);}}return STTop(&(obj->popst));
}bool myQueueEmpty(MyQueue* obj) {assert(obj);return STEmpty(&(obj->pushst))&&STEmpty(&(obj->popst));
}void myQueueFree(MyQueue* obj) {assert(obj);STDestory(&(obj->popst));STDestory(&(obj->pushst));free(obj);
}