用隊(duì)列實(shí)現(xiàn)棧?

思路

棧的特點(diǎn)：后進(jìn)先出? ?

隊(duì)列的特點(diǎn)：先進(jìn)先出

?使用兩個(gè)隊(duì)列實(shí)現(xiàn)棧：

?

我們可以使用兩個(gè)隊(duì)列，一個(gè)隊(duì)列為：空隊(duì)列，一個(gè)隊(duì)列為：非空隊(duì)列

當(dāng)我們要出隊(duì)列時(shí)：

將 size - 1個(gè)數(shù)據(jù)移動(dòng)到空隊(duì)列中，再將最后一個(gè)數(shù)據(jù)出隊(duì)列，如此往復(fù)就可以完成4 3 2 1的出隊(duì)列順序

代碼（c語言）：?

隊(duì)列的各種功能：

typedef int QDataType;
// 鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列 
typedef struct QListNode
{struct QListNode* _next;QDataType _data;
}QNode;// 隊(duì)列的結(jié)構(gòu) 
typedef struct Queue
{QNode* _front;QNode* _rear;int size;
}Queue;
// 初始化隊(duì)列 
void QueueInit(Queue* q) {assert(q);q->size = 0;q->_front = NULL;q->_rear = NULL;
}
// 隊(duì)尾入隊(duì)列 
void QueuePush(Queue* q, QDataType data) {assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("QueuePush()::malloc()");return;}newnode->_data = data;newnode->_next = NULL;//隊(duì)列為NULLif (q->_front == NULL){q->_front = q->_rear = newnode;}else{q->_rear->_next = newnode;q->_rear = q->_rear->_next;}q->size++;
}
// 隊(duì)頭出隊(duì)列 
void QueuePop(Queue* q) {assert(q);assert(q->size != 0);//單個(gè)節(jié)點(diǎn)if (q->_front == q->_rear){free(q->_front);q->_front = q->_rear = NULL;}//多個(gè)節(jié)點(diǎn)else{QNode* next = q->_front->_next;free(q->_front);q->_front = next;}q->size--;
}
// 獲取隊(duì)列頭部元素 
QDataType QueueFront(Queue* q) {assert(q);assert(q->_front);//隊(duì)頭不能為NULLreturn q->_front->_data;
}
// 獲取隊(duì)列隊(duì)尾元素 
QDataType QueueBack(Queue* q) {assert(q);assert(q->_rear);//隊(duì)尾不能為NULLreturn q->_rear->_data;
}
// 獲取隊(duì)列中有效元素個(gè)數(shù) 
int QueueSize(Queue* q) {return q->size;
}
// 檢測隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0 
int QueueEmpty(Queue* q) {assert(q);return q->size == 0;
}
// 銷毀隊(duì)列 
void QueueDestroy(Queue* q) {assert(q);QNode* cur = q->_front;while (cur){QNode* next = cur->_next;free(cur);cur = next;}q->_front = q->_rear = NULL;q->size = 0;}

具體實(shí)現(xiàn)：

//使用兩個(gè)隊(duì)列實(shí)現(xiàn)棧
typedef struct {Queue q1;Queue q2;} MyStack;//初始化棧
MyStack* myStackCreate() {//創(chuàng)建一個(gè)棧MyStack* newStk = (MyStack*)malloc(sizeof(MyStack));//初始化棧(即初始化兩個(gè)隊(duì)列)QueueInit(&(newStk->q1));QueueInit(&(newStk->q2));return newStk;
}//入棧
void myStackPush(MyStack* obj, int x) {//假設(shè)法找不為NULL的隊(duì)列Queue* noempty = &obj->q1;if(QueueSize(noempty) == 0){noempty = &obj->q2;}//往不為NULL隊(duì)列中插入QueuePush(noempty,x);
}//出棧
int myStackPop(MyStack* obj) {//假設(shè)法判斷NULL隊(duì)列，非NULL隊(duì)列Queue* empty = &obj->q1;Queue* noempty = &obj->q2;if(QueueSize(noempty) == 0){noempty = &obj->q1;empty = &obj->q2;}//將size - 1個(gè)數(shù)據(jù)移動(dòng)到NULL隊(duì)列中while(QueueSize(noempty) > 1){QueuePush(empty,QueueFront(noempty));QueuePop(noempty);}//出棧int pop = QueueBack(noempty);QueuePop(noempty);return pop;}//獲取棧頂元素
int myStackTop(MyStack* obj) {Queue* noempty = &obj->q1;if(QueueSize(noempty) == 0){noempty = &obj->q2;}//獲取棧頂數(shù)據(jù)，也就是隊(duì)尾的數(shù)據(jù)return QueueBack(noempty);}//判NULL
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}//銷毀棧
void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);}

用棧實(shí)現(xiàn)隊(duì)列

思路

使用兩個(gè)棧實(shí)現(xiàn)隊(duì)列：

固定兩個(gè)棧，1. 存數(shù)據(jù)棧（pushst） 2. 出數(shù)據(jù)棧（popst）

當(dāng)我們要出數(shù)據(jù)時(shí)，把存數(shù)據(jù)棧（pushst）導(dǎo)入到?出數(shù)據(jù)棧（popst）中，在對棧頂取數(shù)據(jù)，如此往復(fù)就可以實(shí)現(xiàn) 4 3 2 1 的出棧順序

代碼（c語言）：

棧的各種功能：

typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;// 初始化和銷毀
void STInit(ST* pst)
{assert(pst);pst->a = NULL;// top指向棧頂數(shù)據(jù)的下一個(gè)位置pst->top = 0;// top指向棧頂數(shù)據(jù)//pst->top = -1;pst->capacity = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}// 入棧  出棧
void STPush(ST* pst, STDataType x)
{assert(pst);// 擴(kuò)容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--;
}// 取棧頂數(shù)據(jù)
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}// 判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}// 獲取數(shù)據(jù)個(gè)數(shù)
int STSize(ST* pst)
{assert(pst);return pst->top;
}
typedef struct {ST pushst;//用來存儲(chǔ)數(shù)據(jù)ST popst;//用來導(dǎo)出數(shù)據(jù)} MyQueue;

具體實(shí)現(xiàn)

//用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
MyQueue* myQueueCreate() {MyQueue* new = (MyQueue*)malloc(sizeof(MyQueue));STInit(&new->pushst);STInit(&new->popst);return new;
}//入隊(duì)列
void myQueuePush(MyQueue* obj, int x) {STPush(&obj->pushst,x);//插入至數(shù)據(jù)棧（pushst）中}//查看隊(duì)頭元素
int myQueuePeek(MyQueue* obj) {//查看出數(shù)據(jù)棧（popst），中是否有數(shù)據(jù)，有則直接查看棧頂數(shù)據(jù)，沒有就把存數(shù)據(jù)棧（pushst）導(dǎo)入到?出數(shù)據(jù)棧（popst）中if(STEmpty(&obj->popst)){//把pushst數(shù)據(jù)全部導(dǎo)入popstwhile(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}//返回出數(shù)據(jù)棧（popst）棧頂數(shù)據(jù)return STTop(&obj->popst);}//出隊(duì)列
int myQueuePop(MyQueue* obj) {//它會(huì)幫我們導(dǎo)數(shù)據(jù)到popst中，popst棧頂?shù)臄?shù)據(jù)就是我們要?jiǎng)h除的數(shù)據(jù)int pop = myQueuePeek(obj);STPop(&obj->popst);return pop;
}//判空
bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->pushst) && STEmpty(&obj->popst);//兩個(gè)棧為NULL則隊(duì)列為NULL}//銷毀隊(duì)列
void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);
}

設(shè)計(jì)循環(huán)隊(duì)列

????????

?思路

利用數(shù)組來創(chuàng)建循環(huán)隊(duì)列

代碼：

typedef struct {int* a;int head;int rear;//指向最后一個(gè)數(shù)據(jù)的下一個(gè)空間int k;
} MyCircularQueue;//初始化循環(huán)隊(duì)列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* new = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//多開一個(gè)空間，用來解決數(shù)據(jù)為滿與空的矛盾問題，當(dāng)然也可以在結(jié)構(gòu)體多加個(gè)size解決new->a = (int*)malloc(sizeof(int) * (k + 1));new->head = 0;new->rear = 0;//尾數(shù)據(jù)的下一個(gè)位置new->k = k;return new;
}//插入隊(duì)列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//判斷循環(huán)隊(duì)列滿沒有，滿則不能繼續(xù)插入if((obj->rear + 1) % (obj->k + 1) == obj->head)//當(dāng)尾數(shù)據(jù)指針 + 1 = 頭指針時(shí)，隊(duì)列滿return false;obj->a[obj->rear] = value;obj->rear++;obj->rear %= obj->k + 1;//循環(huán)return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//判斷隊(duì)列是否為空，為空則不能繼續(xù)刪除if(obj->head == obj->rear)//當(dāng)尾指針 = 頭指針時(shí)，隊(duì)列為空return false;obj->head++;obj->head %= obj->k + 1; //循環(huán)return true;
}//返回隊(duì)列頭數(shù)據(jù)
int myCircularQueueFront(MyCircularQueue* obj) {if(obj->head == obj->rear)return -1;return obj->a[obj->head];
}//返回隊(duì)列尾數(shù)據(jù)，即找尾指針指向的上一個(gè)地方
int myCircularQueueRear(MyCircularQueue* obj) {if(obj->head == obj->rear)return -1;return obj->a[(obj->k + obj->rear) % (obj->k + 1)];//往前繞k-1去找rear之前的一個(gè)數(shù)據(jù)}//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//空return obj->head == obj->rear;
}//判滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1) % (obj->k + 1) == obj->head;}//銷毀隊(duì)列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}