一、隊列的定義

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 鏈式結構：表示隊列
typedef int  QDataType;
typedef struct QListNode
{struct QListNode* _pNext;QDataType _data;
}QNode;
// 隊列的結構
typedef struct Queue
{QNode* _front;QNode* _rear;int size;
}Queue;
// 初始化隊列
void QueueInit(Queue* q);
// 隊尾入隊列
void QueuePush(Queue* q, QDataType data);
// 隊頭出隊列
void QueuePop(Queue* q);
// 獲取隊列頭部元素
QDataType QueueFront(Queue* q);
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q);
// 獲取隊列中有效元素個數
int QueueSize(Queue* q);
// 檢測隊列是否為空，如果為空返回非零結果，如果非空返回0 
int QueueEmpty(Queue* q);
// 銷毀隊列
void QueueDestroy(Queue* q);

void QueueInit(Queue* q)
{assert(q);q->_front = NULL;q->_rear = NULL;q->size = 0;
}

void QueueDestroy(Queue* q)
{QNode* tmp = q->_front;while (tmp!=NULL){QNode* next = tmp->_pNext;free(tmp);tmp = next;}q->_front = q->_rear = NULL;q->size = 0;
}

?3、插入

void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* tmp = (QNode*)malloc(sizeof(QNode));if (tmp == NULL){perror("malloc fail");return;}else {tmp->_data = data;tmp->_pNext = NULL;}if (q->_rear == NULL){q->_front = q->_rear = tmp;}else{q->_rear->_pNext = tmp;q->_rear = tmp;}q->size++;
}

4、出列

void QueuePop(Queue* q)
{assert(q);assert(q->_front);assert(q->size != 0);if (q->_front->_pNext == NULL)//只有一個節點{free(q->_front);q->_front = q->_rear = NULL;}else{QNode* next = q->_front->_pNext;free(q->_front->_pNext);q->_front = next;}q->size--;
}

5、訪問頭數據

QDataType QueueFront(Queue* q)
{assert(q);assert(q->_front);return q->_front->_data;
}

6、訪問尾數據

QDataType QueueBack(Queue* q)
{assert(q);assert(q->_rear);return q->_rear->_data;
}

7、判斷是否為空和獲取數據個數

// 獲取隊列中有效元素個數
int QueueSize(Queue* q)
{assert(q);return q->size;
}
// 檢測隊列是否為空，如果為空返回非零結果，如果非空返回0 
int QueueEmpty(Queue* q)
{assert(q);return q->size == 0;
}

四、用隊列實現棧

1、分析

我們知道棧是先出后進，而隊列是先進先出；

為了操作簡單，我們在一個隊列中存儲數據；當我們需要插入時，我們可以直接插入，將隊列的隊尾當做棧頂，而當我們要出數據時，我們可以將前n個數據移動到第二個隊列中，最后一個在原隊列中出（此時最后一個數據為第一個數據，符合先進先出）；

有了以上的思路，那么這道題就非常容易解決了：

2、實現

這里要注意力扣上關于這個函數

它返回的是一個棧這個與初始化不一樣。不能再函數內部直接創建棧變量，而是malloc申請一塊空間后返回該指針（因為局部變量出函數就自動銷毀了）

typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack*psk=(MyStack*)malloc(sizeof(MyStack));QueueInit(&(psk->q1));QueueInit(&(psk->q2));return psk;
}void myStackPush(MyStack* obj, int x) 
{if(!QueueEmpty(&(obj->q1))){QueuePush(&(obj->q1),x);}else{QueuePush(&(obj->q2),x);}
}int myStackPop(MyStack* obj) 
{Queue* tmp=&(obj->q1);//假設p1為空Queue* ntmp=&(obj->q2);//p2不為空if(!QueueEmpty(&(obj->q1))){tmp=&(obj->q2);ntmp=&(obj->q1);//假設p1為空}while(QueueSize(ntmp)>1){QueuePush(tmp,QueueFront(ntmp));QueuePop(ntmp);}int top=QueueFront(ntmp);QueuePop(ntmp);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);
}