网站设计特色,酒泉百度做网站多少钱,电子商务网站开发的基本要求,国际网站建设工具目录
1. 用队列实现栈
1.1 题目链接及描述
1.2 解题思路
1.3 程序
2. 用栈实现队列
2.1 题目链接及描述
2.2 解题思路
2.3 程序 1. 用队列实现栈
1.1 题目链接及描述
1. 题目链接 #xff1a; 225. 用队列实现栈 - 力扣#xff08;LeetCode#xff09;
2. 题目描…目录
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次。队列只允许在一端进行数据的插入操作在另一端进行数据的删除操作的特殊线性表队列具有先进先出FIFOFirst 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 topQueueFront(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-top0);pst-top--;
}
// 获取栈顶数据
STDataType STTop(ST* pst) {assert(pst);assert(pst-top0);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 frontmyQueuePeek(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);
}
