題目

????用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列拧抖。隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead ，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能绑嘹。

若隊(duì)列中沒有元素，deleteHead 操作返回 -1

示例1

輸入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
輸出：[null,null,3,-1]

示例2

輸入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]

思路

????首先橘茉，要明確棧是一種只能在一端進(jìn)行插入和刪除操作的特殊線性結(jié)構(gòu)工腋，允許進(jìn)行插入和刪除操作的一端為棧頂，另外一段為棧底畅卓。而隊(duì)列是一種特殊的線性表擅腰，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作翁潘。

????由于隊(duì)列是在前端進(jìn)行刪除的趁冈，而棧底是不支持刪除的，因此拜马，我們可以通過將棧 A的數(shù)據(jù)壓入棧 B 渗勘，這樣棧A的棧底就變成了棧B 的棧頂，我們可以通過對(duì)棧 B的棧頂進(jìn)行刪除俩莽。

輸入為函數(shù)調(diào)用順序和參數(shù)旺坠，當(dāng) appendTail 時(shí)壓棧的數(shù)據(jù)，輸出為 deleteHead 函數(shù)返回值扮超。

代碼實(shí)現(xiàn)

1. 實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)和基本功能入棧取刃、出棧、棾鏊ⅲ空璧疗、獲取棧頂數(shù)據(jù)和釋放功能。

   typedef struct 
   {
       int top;
       int cpacity;
       int *data;
   }SeqStack;
   
   
   SeqStack* Init_seqStack(int cpacity){
       SeqStack *ret = (SeqStack *)malloc(sizeof(SeqStack));
       if (!ret)
       {
           return NULL;
       }else{
           ret->top = -1;
           ret->data = malloc(sizeof(int) * cpacity);
           return ret;
       }
   }
   
   /*
       壓棧
       */
   void push_stack(SeqStack *s,int value){
       //判斷是否棧滿
       if (s->top == s->cpacity - 1)
       {
           return;
       }
       s->top++;
       s->data[s->top] = value;
   }
   void pop_stack(SeqStack *s){
       if (s->top >= 0)
       {
          s->top--;
       }
   }
   bool isEmptyStack(SeqStack* s){
       return (s->top == -1);
   }
   
   int getStackTop(SeqStack *s){
       return s->data[s->top];
   }
   
   void stackFree(SeqStack* obj) {
       free(obj->data);
   }
   
   

2. 實(shí)現(xiàn)棧 A 數(shù)據(jù)壓入棧 B

   void atob(SeqStack *a馁龟，SeqStack *b) {
       while (!isEmptyStack(a)) {
           push_stack(b, getStackTop(a));
           pop_stack(a);
       }
   }
   

3. 定義隊(duì)列的數(shù)據(jù)結(jié)構(gòu)為兩個(gè)棧 inStack 和 outStack崩侠，實(shí)現(xiàn)appendTail 和 deleteHead

   typedef struct {
      SeqStack *inStack;
      SeqStack *outStack;
   } CQueue;
   CQueue* cQueueCreate() {
      CQueue *cqueue = (CQueue *)malloc(sizeof(CQueue));
      cqueue->inStack = Init_seqStack(10000);
      cqueue->outStack = Init_seqStack(10000);
      return cqueue;
   }
   
   void in2out(CQueue* obj) {
       while (!isEmptyStack(obj->inStack)) {
           push_stack(obj->outStack, getStackTop(obj->inStack));
           pop_stack(obj->inStack);
       }
   }
   
   
   void cQueueAppendTail(CQueue* obj, int value) {
         push_stack(obj->inStack, value);
   }
   
   int cQueueDeleteHead(CQueue* obj) {
       if (isEmptyStack(obj->outStack)) {
           if (isEmptyStack(obj->inStack)) {
               return -1;
           }
           in2out(obj);
       }
       int x = getStackTop(obj->outStack);
       pop_stack(obj->outStack);
       return x;
   }
   
   void cQueueFree(CQueue* obj) {
       stackFree(obj->inStack);
       stackFree(obj->outStack);
       free(obj);
   }