【算法题】29. 用两个栈实现队列

题目

    用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。

若队列中没有元素，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]

思路

    首先，要明确栈是一种只能在一端进行插入和删除操作的特殊线性结构，允许进行插入和删除操作的一端为栈顶，另外一段为栈底。而队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。

    由于队列是在前端进行删除的，而栈底是不支持删除的，因此，我们可以通过将栈 A的数据压入栈 B ，这样栈A的栈底就变成了栈B 的栈顶，我们可以通过对栈 B的栈顶进行删除。

输入为函数调用顺序和参数，当 appendTail 时压栈的数据，输出为 deleteHead 函数返回值。

代码实现

1. 实现栈的数据结构和基本功能入栈、出栈、栈空、获取栈顶数据和释放功能。

   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. 实现栈 A 数据压入栈 B

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

3. 定义队列的数据结构为两个栈 inStack 和 outStack，实现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);
   }