1. Implement stack with queue

graphic

Since two queues are used to implement the stack, it must be related to the nature of the queue. It must be changed back and forth. Let's take a look at this process.

code implementation

typedef struct {
    Queue* q1;
    Queue* q2;
} MyStack;

/** Initialize your data structure here. */

MyStack* myStackCreate() {
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    obj->q1=NULL;
    obj->q2=NULL;
    return obj;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
   if(QueueEmpty(&obj->q1)!= NULL)
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
    Queue** empty=&obj->q2,**nonempty=&obj->q1;
    if(obj->q2!=NULL)
    {
        empty=&obj->q1;
        nonempty=&obj->q2;
    }
    while(QueueSize(*nonempty)>1)
    {
        QueuePush(empty,Queuetake(nonempty));
        QueuePop(nonempty);
    }
    int ret=Queuetake(nonempty);
    QueuePop(nonempty);
    return ret;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
    Queue* empty=obj->q2,*nonempty=obj->q1;
    if(obj->q2!=NULL)
    {
        empty=obj->q1;
        nonempty=obj->q2;
    }
    return QueuetakeBack(&nonempty);  
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
      return QueueEmpty(obj->q1)&&QueueEmpty(obj->q2);
}

void myStackFree(MyStack* obj) {
     QueueDestory(&obj->q1);
     QueueDestory(&obj->q2);
     free(obj);
     obj=NULL;
}

2. Implement queue with stack

graphic

code implementation

typedef struct {
    Stack a;
    Stack b;
} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    Stackinit(&obj->a);
    Stackinit(&obj->b);
    return obj;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->a,x);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
  if(StackEmpty(&obj->b)==1)
  {
      while(StackEmpty(&obj->a)!=1)
      {
          StackPush(&obj->b,Stacktake(&obj->a));
          StackPop(&obj->a);
      }
  }
  int ret=Stacktake(&obj->b);
  StackPop(&obj->b);
  return ret;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
 if(StackEmpty(&obj->b)==1)
  {
      while(StackEmpty(&obj->a)!=1)
      {
          StackPush(&obj->b,Stacktake(&obj->a));
          StackPop(&obj->a);
      }
  }
  return Stacktake(&obj->b);
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->a)&&StackEmpty(&obj->b);
}

void myQueueFree(MyQueue* obj) {
  StackDestory(&obj->a);
  StackDestory(&obj->b);
  free(obj);
  obj=NULL;

Comparison of the two questions

After writing these two questions, you will find that implementing a stack with two queues is obviously much more troublesome than implementing a queue with two stacks. If you implement a queue with two stacks, you only need to fill the elements of the push stack into the pop stack and then go out of the pop stack. However, it is not so simple to implement a stack with two queues. It requires you to output only one element every time and then drop that element, This is caused by the nature of stacks and queues.

3. Circular queue

Array or linked list

If you use a linked list, you need to create a k-node linked list at the beginning, and it's troublesome when you finally write the program to release the k nodes. Therefore, you should still use arrays. They are relatively simple to create and destroy, and the space size has been given, so there is no need to expand.

Attention

1. If it is judged to be empty or full?

2. Pay attention to the problem of index crossing

When you use an array to write a circular queue, you should note that if the rear exceeds the range of the array, you should return it to the beginning. The same is true for front. If you write with a linked list, you point the next of the tail node to the head node.

resolvent

In this case, we only need to create one more space. Note that the created space does not store nodes

code implementation

typedef struct {
    int * arr;
    int front;
    int rear;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr=(int *)malloc(sizeof(int)*(k+1));
    obj->front=0;
    obj->rear=0;
    obj->k=k;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->arr[obj->rear++]=value;
    if(obj->rear==obj->k+1)
    {
        obj->rear=0;
    }
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    ++obj->front;
    if(obj->front==obj->k+1)
    {
        obj->front=0;
    }
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->arr[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
   if(myCircularQueueIsEmpty(obj))
   {
       return -1;
   }
   if(obj->rear==0)
   {
       return obj->arr[obj->k];
   }
   else
   {
      return obj->arr[obj->rear-1];
   }
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->rear==obj->front;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
   return (obj->rear+1)%(obj->k+1)==obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    free(obj);
}