备案控制台
开发者社区 开发与运维 文章 正文

【排排站：探索数据结构中的队列奇象】（下）

2024-01-22 22
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【排排站：探索数据结构中的队列奇象】

【排排站：探索数据结构中的队列奇象】（上）:https://developer.aliyun.com/article/1424895


四、队列面试题

1. 用队列实现栈。OJ链接


  • 栈是一种后进先出的数据结构，元素从顶端入栈，然后从顶端出栈。
  • 队列是一种先进先出的数据结构，元素从后端入队，然后从前端出队。


思路：


       为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，其中 queue1用于存储栈内的元素，queue2作为入栈操作的辅助队列。


       入栈操作时，首先将元素入队到 queue2 ，然后将 queue1的全部元素依次出队并入队到 queue2此时 queue2的前端的元素即为新入栈的元素，再将 queue1和 queue2 互换，则 queue1 的元素即为栈内的元素，queue1的前端和后端分别对应栈顶和栈底。


       由于每次入栈操作都确保 queue1的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除 queue1的前端元素并返回即可，获得栈顶元素操作只需要获得 queue1的前端元素并返回即可（不移除元素）。


       由于 queue1用于存储栈内的元素，判断栈是否为空时，只需要判断 queue1是否为空即可。

typedef struct {
    int* stk;
    int stkSize;
    int stkCapacity;
} Stack;
Stack* stackCreate(int cpacity) {
    Stack* ret = malloc(sizeof(Stack));
    ret->stk = malloc(sizeof(int) * cpacity);
    ret->stkSize = 0;
    ret->stkCapacity = cpacity;
    return ret;
}
void stackPush(Stack* obj, int x) {
    obj->stk[obj->stkSize++] = x;
}
void stackPop(Stack* obj) {
    obj->stkSize--;
}
int stackTop(Stack* obj) {
    return obj->stk[obj->stkSize - 1];
}
bool stackEmpty(Stack* obj) {
    return obj->stkSize == 0;
}
void stackFree(Stack* obj) {
    free(obj->stk);
}
typedef struct {
    Stack* inStack;
    Stack* outStack;
} MyQueue;
MyQueue* myQueueCreate() {
    MyQueue* ret = malloc(sizeof(MyQueue));
    ret->inStack = stackCreate(100);
    ret->outStack = stackCreate(100);
    return ret;
}
void in2out(MyQueue* obj) {
    while (!stackEmpty(obj->inStack)) {
        stackPush(obj->outStack, stackTop(obj->inStack));
        stackPop(obj->inStack);
    }
}
void myQueuePush(MyQueue* obj, int x) {
    stackPush(obj->inStack, x);
}
int myQueuePop(MyQueue* obj) {
    if (stackEmpty(obj->outStack)) {
        in2out(obj);
    }
    int x = stackTop(obj->outStack);
    stackPop(obj->outStack);
    return x;
}
int myQueuePeek(MyQueue* obj) {
    if (stackEmpty(obj->outStack)) {
        in2out(obj);
    }
    return stackTop(obj->outStack);
}
bool myQueueEmpty(MyQueue* obj) {
    return stackEmpty(obj->inStack) && stackEmpty(obj->outStack);
}
void myQueueFree(MyQueue* obj) {
    stackFree(obj->inStack);
    stackFree(obj->outStack);
}


2. 用栈实现队列。OJ链接


将一个栈当作输入栈，用于压入 push\ 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。每次 pop 或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

typedef struct {
    int* stk;
    int stkSize;
    int stkCapacity;
} Stack;
Stack* stackCreate(int cpacity) {
    Stack* ret = malloc(sizeof(Stack));
    ret->stk = malloc(sizeof(int) * cpacity);
    ret->stkSize = 0;
    ret->stkCapacity = cpacity;
    return ret;
}
void stackPush(Stack* obj, int x) {
    obj->stk[obj->stkSize++] = x;
}
void stackPop(Stack* obj) {
    obj->stkSize--;
}
int stackTop(Stack* obj) {
    return obj->stk[obj->stkSize - 1];
}
bool stackEmpty(Stack* obj) {
    return obj->stkSize == 0;
}
void stackFree(Stack* obj) {
    free(obj->stk);
}
typedef struct {
    Stack* inStack;
    Stack* outStack;
} MyQueue;
MyQueue* myQueueCreate() {
    MyQueue* ret = malloc(sizeof(MyQueue));
    ret->inStack = stackCreate(100);
    ret->outStack = stackCreate(100);
    return ret;
}
void in2out(MyQueue* obj) {
    while (!stackEmpty(obj->inStack)) {
        stackPush(obj->outStack, stackTop(obj->inStack));
        stackPop(obj->inStack);
    }
}
void myQueuePush(MyQueue* obj, int x) {
    stackPush(obj->inStack, x);
}
int myQueuePop(MyQueue* obj) {
    if (stackEmpty(obj->outStack)) {
        in2out(obj);
    }
    int x = stackTop(obj->outStack);
    stackPop(obj->outStack);
    return x;
}
int myQueuePeek(MyQueue* obj) {
    if (stackEmpty(obj->outStack)) {
        in2out(obj);
    }
    return stackTop(obj->outStack);
}
bool myQueueEmpty(MyQueue* obj) {
    return stackEmpty(obj->inStack) && stackEmpty(obj->outStack);
}
void myQueueFree(MyQueue* obj) {
    stackFree(obj->inStack);
    stackFree(obj->outStack);
}


3. 设计循环队列。OJ链接


顺序队列的假溢出问题

解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。当队首指针Q->front = MAXSIZE-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。


  • 初始时：Q->front = Q->rear=0。
  • 队首指针进1：Q->front = (Q->front + 1) % MAXSIZE。
  • 队尾指针进1：Q->rear = (Q->rear + 1) % MAXSIZE。
  • 队列长度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。


出队入队时，指针都按照顺时针方向前进1，如下图所示：


       那么，循环队列队空和队满的判断条件是什么呢？


显然，队空的条件是 Q->front == Q->rear 。若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针，如图( d1 ）所示，此时可以看出队满时也有 Q ->front == Q -> rear 。为了区分队空还是队满的情况，有三种处理方式：


（1）牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”，如图 ( d2 ）所示。


  • 队满条件： (Q->rear + 1)%Maxsize == Q->front
  • 队空条件仍： Q->front == Q->rear
  • 队列中元素的个数： (Q->rear - Q ->front + Maxsize)% Maxsize


（2）类型中增设表示元素个数的数据成员。这样，队空的条件为 Q->size == O ；队满的条件为 Q->size == Maxsize 。这两种情况都有 Q->front == Q->rear


（3）类型中增设tag 数据成员，以区分是队满还是队空。tag 等于0时，若因删除导致 Q->front == Q->rear ，则为队空；tag 等于 1 时，若因插入导致 Q ->front == Q->rear ，则为队满。

typedef struct {
    int front;
    int rear;
    int capacity;
    int *elements;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    obj->capacity = k + 1;
    obj->rear = obj->front = 0;
    obj->elements = (int *)malloc(sizeof(int) * obj->capacity);
    return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if ((obj->rear + 1) % obj->capacity == obj->front) {
        return false;
    }
    obj->elements[obj->rear] = value;
    obj->rear = (obj->rear + 1) % obj->capacity;
    return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (obj->rear == obj->front) {
        return false;
    }
    obj->front = (obj->front + 1) % obj->capacity;
    return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
    if (obj->rear == obj->front) {
        return -1;
    }
    return obj->elements[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
    if (obj->rear == obj->front) {
        return -1;
    }
    return obj->elements[(obj->rear - 1 + obj->capacity) % obj->capacity];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->rear == obj->front;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % obj->capacity == obj->front;
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->elements);
    free(obj);
}
文章标签：
前端开发
存储
关键词：
数据结构队列
排排站数据结构队列奇象
笨笨胡小巴
目录
相关文章
不摸鱼的程序员
|
6天前
|
存储 Java 容器
深入浅出 栈和队列（附加循环队列、双端队列）
深入浅出 栈和队列（附加循环队列、双端队列）
不摸鱼的程序员
28 4
过。
|
7天前
|
算法 Java
Java数据结构——队列
Java数据结构——队列
过。
22 4
TU^
|
11天前
|
存储 调度 索引
数据结构~~栈和队列
在计算机科学中，数据结构是构建高效程序的基础。栈和队列是两种重要且常用的线性数据结构，它们在解决各种问题中发挥着关键作用。
TU^
24 1
游客jajxe3foty4uc
|
6天前
栈与队列
栈与队列
游客jajxe3foty4uc
12 0
Sessy
|
7天前
＜数据结构＞栈和队列. 顺序表实现栈，单链表实现队列.
＜数据结构＞栈和队列. 顺序表实现栈，单链表实现队列
Sessy
18 3
兰雪簪轩
|
7天前
|
存储 测试技术 计算机视觉
栈和队列经典练习题
栈和队列经典练习题
兰雪簪轩
18 3
兰雪簪轩
|
7天前
数据结构之——队列详解
数据结构之——队列详解
兰雪簪轩
14 0
wishCoding
|
10天前
|
缓存 Java 编译器
JavaSE精选-栈和队列
JavaSE精选-栈和队列
wishCoding
18 1
八音盒coding
|
11天前
|
缓存 Java 编译器
栈和队列技术文章
栈和队列技术文章
八音盒coding
18 2
wan__cheng
|
11天前
数据结构（队列）
数据结构（队列）
wan__cheng
16 0