习题1 用队列实现栈
225. 用队列实现栈 - 力扣（LeetCode）
1.把有数据队列的内容，传到没数据的队列中，传一个之后，再原队列中删一个
2.等q1中剩一个元素的时候，让这个元素出队
这样就可以达到栈的效果，1，2，3，4，5，让5先出栈，之后再按照同样的方法把q1看作空（压栈的时候要往有元素的队里压），开始倒数据即可 
队列的实现
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode *head; QNode* tail; size_t size; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void QueuePush(Queue *pq, QDataType x); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); bool QueueEmpty(Queue* pq); int QueueSize(Queue* pq); void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); del = NULL; } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QDataType x) { QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode); newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; }//如果只剩一个节点，单独处理，防止tail变为野指针 else { QNode* cur = pq->head; pq->head = pq->head->next; free(cur); cur = NULL; } pq->size--; } QDataType QueueFront(Queue* pq)//取头数据 { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq)//取尾数据 { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head==NULL && pq->tail==NULL; } int QueueSize(Queue* pq) { return pq->size; }
通过队列实现栈
结构体的建立
typedef struct { Queue q1; //建立俩个 Queue q2; } MyStack; //也可用Queue*，但是这样的话要用malloc给q1和q2开辟空间
初始化
MyStack* myStackCreate() { MyStack*obj=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; }//直接传参即可
压栈
void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); }//如果q1不是空，把元素压到q1 else { QueuePush(&obj->q2,x); } }
出栈
int myStackPop(MyStack* obj) { Queue *empty=&obj->q1;//假设q1为空 Queue *noempty=&obj->q2;//假设q2不是空 if(!QueueEmpty(&obj->q1)) { noempty=&obj->q1; empty=&obj->q2; while(QueueSize(noempty)>1) //将有元素的队列的数据，倒到只剩最后一个元素 { QueuePush(empty,QueueFront(noempty)); QueuePop(noempty); } int top=QueueFront(noempty);//该元素就是栈顶 QueuePop(noempty); 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(obj)，因为q1和q2是链表，链表的内存不连续，如果释放掉boj,则q1和q2没有释放，会造成内存泄漏
用队列实现栈
232. 用栈实现队列 - 力扣（LeetCode）
若队列中是1 2 3 4 5，则按照栈的规则，此时出栈顺序应该是 5 4 3 2 1，我们可以用俩个队列来实现栈
1.把PushST里面的数据倒到PopST
2.出栈的时候，我们只需要出PopST里面的元素就可以，当有元素要填充时，填充到PushST就行
栈的实现
typedef int STDdtaTtype; typedef struct Stcak { STDdtaTtype* data; int top; int capacity; }ST; void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps, STDdtaTtype x); void StackPop(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST* ps); STDdtaTtype StackTop(ST* ps); void StackInit(ST* ps) { assert(ps); ps->data = NULL; ps->capacity = ps->top = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->data); ps->capacity = ps->top = 0; ps->data = NULL; } void StackPush(ST* ps, STDdtaTtype x)//注意要看top的位置是0还是-1 { assert(ps); int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; if (ps->capacity == ps->top)//判断是否满了 { STDdtaTtype* tmp = realloc(ps->data, sizeof(ps) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->data = tmp; ps->capacity = newcapacity; } ps->data[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; } STDdtaTtype StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->data[ps->top - 1]; } bool StackEmpty(ST* ps)//判断是否为空栈 { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; }
结构体创建
typedef struct { ST PushST; ST PopST; } MyQueue;
结构体的初始化
MyQueue* myQueueCreate() { MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue)); StackInit(&obj->PushST); StackInit(&obj->PopST); return obj; }
