数据结构-栈、队列-相关练习

1.用队列实现栈

用队列实现栈

• 题目概述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

这里只讲大致思路，如下图：

互相倒就行了，下面讲个具体过程：

• 第一步：入队
  
• 第二步：倒数据
  留下的那个，就是最后的一个数据。
  
• 第三步：出队/出栈
  符合后入先出。
  
  我写的：
  
  队列的数据结构CV一下就行。

2.用栈实现队列

用栈实现队列

题目概述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

总体思路：

讲个具体过程：

• 第一步：入栈
  
• 第二步：倒数据
  倒后顺序也倒了，此时stackpop出栈时，数据满足先入先出。
  
• 第三步：出栈/出队
  
• 如果又有数据入栈
  
• 什么时候再倒数据？
  stackpop为空的时候再倒。
  

我写的：

其中，栈的数据结构，同样CV过去。

3.设计循环队列

设计循环队列

题目概述：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

一看到循环，我首先想到了链表：

但这样并不便于实现：
在队列为空时，队首等于队尾；在队列为满时，队首还是等于队尾。
有三个解决方法：

• 加一个size
• 多一个结点，避免冲突
• 不用链表

我选第三个方法，用了数组。

而主要问题转化为，如何用下标表示循环。

先建好结构体：

typedef struct {
    int* a;
    int head;
    int tail;
    int k;
} MyCircularQueue;

在初始化时，发现，如果创建k个元素大小的数组，在队列为空时，队首等于队尾；在队列为满时，队首还是等于队尾。
与链表相同的问题，但用数组解决就简单很多了：创建k+1个元素大小的数组就行。
此时，tail为队尾的下一个元素的下标。

在后续的处理中，需要面对主要的问题：如何处理循环？

• 判满：

总数为k+1，下标最大就为k，存满了就是这样：

判满时，可以用tail + 1==head

或者这样：

对于tail，此时，再+1就越界了，根据观察，可以用(tail + 1)%(k + 1) == head来模拟循环。

• 取尾：
  正常情况，tail-1就是尾部元素的下标，但下面这种情况就是不正常的：

此时，可以用a[ (tail + k) % (k + 1) ]来模拟循环。

我写的完整代码：

typedef struct {
    int* a;
    int head;
    int tail;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* ret = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    ret->a = (int*)malloc(sizeof(int)*(k+1));
    ret->head = ret->tail = 0;
    ret->k = k;
    return ret;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    return (obj->tail + 1)%(obj->k + 1) == obj->head;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->tail++] = value;
    obj->tail = obj->tail % (obj->k+1);
    return true;
}

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

int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else 
        return obj->a[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else 
        return obj->a[(obj->tail+obj->k)%(obj->k+1)];
}

希望本篇文章对你有所帮助！并激发你进一步探索数据结构的兴趣！

本人仅是个C语言初学者，如果你有任何疑问或建议，欢迎随时留言讨论！让我们一起学习，共同进步！

相关文章：
数据结构-栈、队列-详解