栈和队列面试题（C 语言）

🕗 发布于 2024-11-08 15:20 c语言 数据结构 经验分享

1. 有效的括号

题目描述： 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”
输出：true

示例 2：

输入：s = “()[]{}”
输出：true

示例 3：

输入：s = “(]”
输出：false

示例 4：

输入：s = “([])”
输出：true

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

题目OJ链接： link

解题思路： 分析题目可得，每次出现的右括号总是和离得最近的左括号匹配。那么可以把左括号都压入栈中，遇到右括号就拿出来匹配，不匹配就返回 false。直到遍历完整个字符串，如果栈中元素为空，那么就返回 true，否则返回 false。

由于本题是使用 C 语言答题，需要手搓一个栈出来，还是比较考验答题者的代码水平。

当然也可以使用数组模拟栈，但是其中有一些需要注意的地方。

代码如下：

// 栈

// 类型声明
typedef char DataType;

// 常量声明
#define CAPACITY_INIT 8

// 栈结构声明
typedef struct Stack
{
    DataType* pdata;  // 指向数据的指针
    size_t top;  // 当前栈中元素个数和下一个入栈的位置
    size_t capacity;  // 当前栈的容量
}Stack;

// 方法

// 初始化栈
void StackInit(Stack* sk)
{
    assert(sk);
    // 申请空间
    sk->pdata = (DataType*)malloc(sizeof(DataType)*CAPACITY_INIT);
    if (NULL == sk->pdata)
    {
        perror("StackInit::malloc: ");
        exit(-1);
    }
    // 成员初始化
    sk->capacity = CAPACITY_INIT;
    sk->top = 0;
}

// 入栈
void StackPush(Stack* sk, DataType data)
{
    assert(sk);
    // 增容判断
    if (sk->top == sk->capacity)
    {
        DataType* tmp = (DataType*)realloc(sk->pdata, sizeof(DataType)*sk->capacity*2);
        if (NULL == tmp)
        {
            perror("StackPush::realloc: ");
            exit(-1);
        }
        // 更新成员
        sk->pdata = tmp;
        sk->capacity *= 2;
    }
    // 入栈
    sk->pdata[sk->top++] = data;
}

// 出栈
void StackPop(Stack* sk)
{
    assert(sk);
    // 空栈判duan
    if (0 == sk->top)
    {
        printf("Empty Stack!\n");
        exit(-1);
    }
    // 出栈
    --sk->top;
}

// 返回栈顶元素
DataType StackTop(const Stack* sk)
{
    assert(sk);
    // 空栈判断
    if (0 == sk->top)
    {
        printf("Empty Stack!\n");
        exit(-1);
    }
    // 返回
    return sk->pdata[sk->top-1];
}

// 返回栈中当前元素个数
size_t StackSize(const Stack* sk)
{
    assert(sk);
    return sk->top;
}

// 空栈判断
bool StackEmpty(const Stack* sk)
{
    assert(sk);
    return (0 == sk->top);
}

// 销毁栈
void StackDestory(Stack* sk)
{
    assert(sk);
    // 释放空间
    free(sk->pdata);
    sk->pdata = NULL;
    // 成员置零
    sk->top = sk->capacity = 0;
}

bool isValid(char* s) {
    // 创建并初始化栈
    Stack sk;
    StackInit(&sk);
    // 遍历字符串
    const char* cur = s;
    while (*cur)
    {
        // 左括号入栈
        if ('(' == *cur || '[' == *cur || '{' == *cur)
        {
            StackPush(&sk, *cur);
        }
        else
        {
            // 空栈判断
            if (StackEmpty(&sk))
                return false;
            // 获得栈顶元素
            char top = StackTop(&sk);
            StackPop(&sk);
            // 匹配判断
            if ((')' == *cur && '(' != top)
            || (']' == *cur && '[' != top) 
            || ('}' == *cur && '{' != top))
                return false;
        }
        // 下一个字符
        ++cur;
    }
    // 空栈判断
    if (StackEmpty(&sk))
        return true;
    else
        return false;
}

2. 用队列实现栈

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

实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：
你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：
输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

题目OJ链接： link

解题思路： 使用两个队列——q1 和 q2。当需要入栈的时候，往两个队列中不为空的队列入数据；当需要出栈的时候，把不为空的队列的数据除了队尾的数据，其他全部导入另一个空队中，然后把队尾的数据出队，也就完成了出栈的操作。那么剩下的操作就非常简单了。

本题也可以使用一个队列来完成，入栈的时候入队就行，出栈的时候需要把除队尾以外的所有元素全部出队再入队，然后队尾的元素就在队头的，然后把它出队，这样就完成了出栈的操作。

代码如下：
（1）两个队列

// 队列

// 类型声明
typedef int DataType;

// 节点结构声明
typedef struct Node
{
    DataType val;  // 数据
    struct Node* next;  // 下一个结点的位置
}Node;

// 队列结构声明
typedef struct Queue
{
    Node* head;  // 队头位置
    Node* tail;  // 队尾位置
    size_t size;  // 当前队列元素个数
}Queue;

// 方法

// 初始化队列
void QueueInit(Queue* q)
{
    assert(q);
    q->head = q->tail = NULL;
    q->size = 0;
}

// 入队
void QueuePush(Queue* q, DataType data)
{
    assert(q);
    // 申请新节点
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (NULL == new_node)
    {
        perror("QueuePush::malloc: ");
        exit(-1);
    }
    // 赋值
    new_node->val = data;
    new_node->next = NULL;
    // 入队
    // 头插判断
    if (NULL == q->head)
    {
        q->head = q->tail = new_node;
    }
    else  // 尾插
    {
        q->tail->next = new_node;
        q->tail = new_node;
    }
    // 元素个数 +1
    ++q->size;
}

// 出队
void QueuePop(Queue* q)
{
    assert(q);
    // 空队判断
    if (0 == q->size)
    {
        printf("Empty Queue!\n");
        exit(-1);
    }
    // 出队
    // 尾删判断
    if (NULL == q->head->next)
    {
        free(q->head);
        q->head = q->tail = NULL;
    }
    else  // 头删
    {
        // 存储下一个节点的位置
        Node* next = q->head->next;
        // 删除头节点
        free(q->head);
        // 新的头节点
        q->head = next;
    }
    // 元素个数 -1
    --q->size;
}

// 返回队头元素
DataType QueueFront(const Queue* q)
{
    assert(q);
    // 空队判断
    if (0 == q->size)
    {
        printf("Empty Queue!\n");
        exit(-1);
    }
    // 返回
    return q->head->val;
}

// 返回队尾元素
DataType QueueBack(const Queue* q)
{
    assert(q);
    // 空队判断
    if (0 == q->size)
    {
        printf("Empty Queue!\n");
        exit(-1);
    }
    // 返回
    return q->tail->val;
}

// 空队判断
bool QueueEmpty(const Queue* q)
{
    assert(q);
    return (0 == q->size);
}

// 返回当前队列的元素个数
size_t QueueSize(const Queue* q)
{
    assert(q);
    return q->size;
}

// 销毁队列
void QueueDestory(Queue* q)
{
    assert(q);
    Node* cur = q->head;
    while (cur)
    {
        // 存储下一个节点
        Node* next = cur->next;
        // 释放当前节点
        free(cur);
        // 下一个节点
        cur = next;
    }
    // 成员置零
    q->head = q->tail = NULL;
}

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


MyStack* myStackCreate() {
    // 申请空间
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    if (NULL == obj)
    {
        perror("myStackCreate::malloc: ");
        exit(-1);
    }
    // 成员初始化
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    // 返回
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    // 往非空队列入元素
    if (QueueEmpty(&obj->q1))
        QueuePush(&obj->q2, x);
    else
        QueuePush(&obj->q1, x);
}

int myStackPop(MyStack* obj) {
    assert(obj);
    // 找到空队
    Queue* empty = &obj->q1;
    Queue* non_empty = &obj->q2;
    if (QueueEmpty(&obj->q2))
    {
        empty = &obj->q2;
        non_empty = &obj->q1;
    }
    // 把非空队除队尾元素以外全部入到空队
    int n = (int)QueueSize(non_empty) - 1;
    int i = 0;
    for (i = 0; i < n; ++i)
    {
        QueuePush(empty, QueueFront(non_empty));
        QueuePop(non_empty);
    }
    // 出队尾元素并返回
    DataType ret = QueueFront(non_empty);
    QueuePop(non_empty);
    return ret;
}

int myStackTop(MyStack* obj) {
    assert(obj);
    // 返回非空队的队尾元素
    if (QueueEmpty(&obj->q1))
        return QueueBack(&obj->q2);
    else
        return QueueBack(&obj->q1);
}

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    // 判断两个队列是否都为空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    // 释放两个队列
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    // 释放栈
    free(obj);
}

（2）一个队列

// 队列

// 类型声明
typedef int DataType;

// 节点结构声明
typedef struct Node
{
    DataType val;  // 数据
    struct Node* next;  // 下一个节点的位置
}Node;

// 队列结构声明
typedef struct Queue
{
    Node* head;  // 队头位置
    Node* tail;  // 队尾位置
    size_t size;  // 队列元素个数
}Queue;

// 方法

// 初始化队列
void QueueInit(Queue* q)
{
    assert(q);
    q->head = q->tail = NULL;
    q->size = 0;
}

// 入队
void QueuePush(Queue* q, DataType data)
{
    assert(q);
    // 申请新节点
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (NULL == new_node)
    {
        perror("QueuePush::malloc: ");
        exit(-1);
    }
    // 赋值
    new_node->val = data;
    new_node->next = NULL;
    // 头插判断
    if (NULL == q->head)
    {
        q->head = q->tail = new_node;
    }
    else  // 尾插
    {
        q->tail->next = new_node;
        q->tail = new_node;
    }
    // 元素个数 +1
    ++q->size;
}

// 出队
void QueuePop(Queue* q)
{
    assert(q);
    // 空队判断
    if (0 == q->size)
    {
        printf("Empty Queue!\n");
        exit(-1);
    }
    // 尾删判断
    if (NULL == q->head->next)
    {
        free(q->head);
        q->head = q->tail = NULL;
    }
    else  // 头删
    {
        // 存储下一个节点
        Node* next = q->head->next;
        // 释放头结点
        free(q->head);
        // 新的头节点
        q->head = next;
    }
    // 元素个数 -1
    --q->size;
}

// 返回队头元素
DataType QueueFront(const Queue* q)
{
    assert(q);
    // 空队判断
    if (0 == q->size)
    {
        printf("Empty Queue!\n");
        exit(-1);
    }
    // 返回
    return q->head->val;
}

// 返回队尾元素
DataType QueueBack(const Queue* q)
{
    assert(q);
    // 空队判断
    if (0 == q->size)
    {
        printf("Empty Queue!\n");
        exit(-1);
    }
    // 返回
    return q->tail->val;
}

// 空队判断
bool QueueEmpty(const Queue* q)
{
    assert(q);
    return (0 == q->size);
}

// 返回当前队列中元素个数
size_t QueueSize(const Queue* q)
{
    assert(q);
    return q->size;
}

// 销毁队列
void QueueDestory(Queue* q)
{
    assert(q);
    Node* cur = q->head;
    while (cur)
    {
        // 存储下一个结点的位置
        Node* next = cur->next;
        // 删除当前节点
        free(cur);
        // 下一个节点
        cur = next;
    }
    // 成员置零
    q->head = q->tail = NULL;
    q->size = 0;
}


typedef struct {
    Queue q;
} MyStack;


MyStack* myStackCreate() {
    // 申请空间
    MyStack* sk = (MyStack*)malloc(sizeof(MyStack));
    if (NULL == sk)
    {
        perror("myStackCreate::malloc: ");
        exit(-1);
    }
    // 成员初始化
    QueueInit(&sk->q);
    // 返回
    return sk;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    // 直接入队
    QueuePush(&obj->q, x);
}

int myStackPop(MyStack* obj) {
    assert(obj);
    // 把除队尾以外所有元素重新入队
    int n = (int)QueueSize(&obj->q) - 1;
    while (n--)
    {
        QueuePush(&obj->q, QueueFront(&obj->q));
        QueuePop(&obj->q);
    }
    // 返回队头元素并出队
    DataType ret = QueueFront(&obj->q);
    QueuePop(&obj->q);
    return ret;
}

int myStackTop(MyStack* obj) {
    assert(obj);
    return QueueBack(&obj->q);
}

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&obj->q);
}

void myStackFree(MyStack* obj) {
    assert(obj);
    // 释放队列
    QueueDestory(&obj->q);
    // 释放栈
    free(obj);
    obj = NULL;
}

3. 用栈实现队列

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

实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

题目OJ链接： link

解题思路： 一个栈专门用来入数据，另一个栈专门用来出数据。当出数据的栈为空时，就把入数据栈中的数据导入到出数据的栈中。

代码如下：

// 栈

// 类型声明
typedef int DataType;

// 常量声明
#define CAPACITY_INIT 8

// 栈结构声明
typedef struct Stack
{
    DataType* pdata;  // 数据的位置
    size_t top;  // 下一个入栈位置和当前栈中的元素个数
    size_t capacity;  // 当前栈的容量
}Stack;

// 方法

// 初始化栈
void StackInit(Stack* sk)
{
    assert(sk);
    // 申请空间
    sk->pdata = (DataType*)malloc(sizeof(DataType)*CAPACITY_INIT);
    if (NULL == sk->pdata)
    {
        perror("StackInit::malloc: ");
        exit(-1);
    }
    // 成员初始化
    sk->capacity = CAPACITY_INIT;
    sk->top = 0;
}

// 入栈
void StackPush(Stack* sk, DataType data)
{
    assert(sk);
    // 增容判断
    if (sk->top == sk->capacity)
    {
        DataType* tmp = (DataType*)realloc(sk->pdata, sizeof(DataType)*sk->capacity*2);
        if (NULL == tmp)
        {
            perror("StackPush::realloc: ");
            exit(-1);
        }
        // 增容成功，更新成员
        sk->pdata = tmp;
        sk->capacity *= 2;
    }
    // 入栈
    sk->pdata[sk->top++] = data;
}

// 出栈
void StackPop(Stack* sk)
{
    assert(sk);
    // 空栈判断
    if (0 == sk->top)
    {
        printf("Empty Stack!\n");
        exit(-1);
    }
    // 出栈
    --sk->top;
}

// 返回栈顶元素
DataType StackTop(const Stack* sk)
{
    assert(sk);
    // 返回
    return sk->pdata[sk->top-1];
}

// 返回栈中当前元素个数
size_t StackSize(const Stack* sk)
{
    assert(sk);
    // 返回
    return sk->top;
}

// 栈空判断
bool StackEmpty(const Stack* sk)
{
    assert(sk);
    // 返回
    return (0 == sk->top);
}

// 销毁栈
void StackDestory(Stack* sk)
{
    assert(sk);
    // 释放数据
    free(sk->pdata);
    sk->pdata = NULL;
    // 成员置零
    sk->top = sk->capacity = 0;
}

typedef struct {
    // 两个栈，分别出入数据
    Stack push;
    Stack pop;
} MyQueue;


MyQueue* myQueueCreate() {
    // 申请空间
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    if (NULL == q)
    {
        perror("myQueueCreat::malloc: ");
        exit(-1);
    }
    // 成员初始化
    StackInit(&q->push);
    StackInit(&q->pop);
    // 返回
    return q;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->push, x);
}

int myQueuePop(MyQueue* obj) {
    assert(obj);
    // 导数据判断
    if (StackEmpty(&obj->pop))
    {
        while (!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop, StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    // 出数据
    DataType ret = StackTop(&obj->pop);
    StackPop(&obj->pop);
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    // 导数据判断
    if (StackEmpty(&obj->pop))
    {
        while (!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop, StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    // 返回
    return StackTop(&obj->pop);
}

bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
}

void myQueueFree(MyQueue* obj) {
    assert(obj);
    // 释放栈
    StackDestory(&obj->push);
    StackDestory(&obj->pop);
    // 释放队列
    free(obj);
    obj = NULL;
}

4. 设计循环队列

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

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

提示：
所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。

解题思路： 本题的解题思路在我的栈和队列的博客当中，其中的循环队列讲解了如何实现的思路。博客链接如下：
link

代码如下：
（1）额外开辟一个空间

// 类型声明
typedef int DataTpye;

typedef struct {
    DataTpye* pdata;  // 数据的位置
    size_t head;  // 队头下标
    size_t tail;  // 队尾下标
    size_t k;  // 环形队列的大小
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    // 申请空间
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (NULL == q)
    {
        perror("myCircularQueueCreate::malloc: ");
        exit(-1);
    }
    // 成员初始化
    q->pdata = (DataTpye*)malloc(sizeof(DataTpye)*(k+1));
    if (NULL == q->pdata)
    {
        perror("myCircularQueueCreate::malloc: ");
        exit(-1);
    }
    q->k = k;
    q->head = q->tail = 0;
    // 返回
    return q;
}

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->pdata[obj->tail] = value;
    obj->tail = (obj->tail+1)%(obj->k+1);
    // 入队成功
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    // 空队判断
    if (myCircularQueueIsEmpty(obj))
        return false;
    // 出队
    obj->head = (obj->head+1)%(obj->k+1);
    // 出队成功
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    // 空队判断
    if (myCircularQueueIsEmpty(obj))
        return -1;
    // 返回
    return obj->pdata[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
     assert(obj);
    // 空队判断
    if (myCircularQueueIsEmpty(obj))
        return -1;
    // 返回
    if (obj->tail)
        return obj->pdata[obj->tail-1];
    else
        return obj->pdata[obj->k];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);
    // 释放数据
    free(obj->pdata);
    obj->pdata = NULL;
    // 成员置零
    obj->head = obj->tail = 0;
    obj->k = 0;
    // 释放队列
    free(obj);
    obj = NULL;
}

（2）额外使用一个 size_t 类型的变量 size 存储当前队列元素个数

// 类型声明
typedef int DataType;

typedef struct {
    DataType* pdata;  // 数据位置
    size_t head;  // 队头下标
    size_t tail;  // 队尾下标
    size_t size;  // 当前队列元素个数
    size_t k;  // 队列大小
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    // 申请队列空间
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (NULL == q)
    {
        perror("myCircularQueueCreate::malloc: ");
        exit(-1);
    }
    // 申请数据空间
    q->pdata = (DataType*)malloc(sizeof(DataType)*(k+1));
    if (NULL == q->pdata)
    {
        perror("myCircularQueueCreate::malloc: ");
        exit(-1);
    }
    // 成员初始化
    q->head = q->tail = 0;
    q->size = 0;
    q->k = k;
    // 返回
    return q;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    // 满队判断
    if (obj->size == obj->k)
        return false;
    // 入队
    obj->pdata[obj->tail] = value;
    obj->tail = (obj->tail+1)%(obj->k+1);
    ++obj->size;
    // 入队成功
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    // 空队判断
    if (0 == obj->size)
    {
        return false;
    }
    // 出队
    obj->head = (obj->head+1)%(obj->k+1);
    --obj->size;
    // 出队成功
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    // 空队判断
    if (0 == obj->size)
        return -1;
    // 返回
    return obj->pdata[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    // 空队判断
    if (0 == obj->size)
        return -1;
    // 返回
    if (obj->tail)
        return obj->pdata[obj->tail-1];
    else
        return obj->pdata[obj->k];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return (0 == obj->size);
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    return (obj->size == obj->k);
}

void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);
    // 释放数据
    free(obj->pdata);
    // 释放队列
    free(obj);
    obj = NULL;
}

原文地址：https://blog.csdn.net/weixin_70742989/article/details/143612352

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Hive面试题-- 查询各类型专利 top10 申请人及专利申请数
下一篇：Ceph MDS高可用架构探索：从零到一构建多主一备MDS服务

【C++】list 类深度解析：探索双向链表的奇妙世界
本文深度解析了 C++ 标准库中的 list 类。首先阐述学习 list 类的原因，其具有高效插入删除操作优势，如双向链表结构使插入删除只需调指针，时间复杂度常数级；内存管理灵活，节点分散存储避免内存
阅读更多2024-11-16
常用List工具类（取交集、并集等等）
【代码】常用List工具类（取交集、并集等等）
阅读更多2024-11-16
宝塔面板从 Nginx 切换到 Caddy：详细教程
宝塔面板从 Nginx 切换到 Caddy
阅读更多2024-11-16
计算机网络中的数据包传输机制详解
数据包是网络通信的基本单位，它包含了控制信息（如源地址、目的地址等）和用户数据（即有效载荷）。根据不同的网络协议，数据包的结构会有所不同。数据包的传输机制是计算机网络的核心内容之一，它涉及到数据的封装
阅读更多2024-11-16
LinkedList 源码分析
仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的平均时间复杂度都是 O(n)。底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现。是一
阅读更多2024-11-16
【泛型 Plus】Kotlin 的加强版类型推断：@BuilderInference
视频先行下面是视频内容的脚本文案原稿分享。小剧场面试官：「既然协程和泛型你都熟悉，flow() 函数是怎么实现类型推断的有了解过吗？」求职者：「嗯……」求职者：「嗯……在Kotlin协程中，flow
阅读更多2024-11-16
20.UE5UI预构造，开始菜单
如果我们直接再画布上设计我们的按钮，我们需要为每一个按钮进行编辑，复用性太差，能不能在其他的UI蓝图中编辑好，随后就好像其他元素（文本，button）一样，直接放入到我们的画布中？为了在复用时，可以自
阅读更多2024-11-16
支持向量机SVM——基于分类问题的监督学习算法
支持向量机SVM是一种常用于分类问题的监督学习算法。文章主要从基础公式角度讲解它的基本原理，涉及线性和非线性情况。
阅读更多2024-11-16
鸿蒙生态下的安全隐私保护：打造用户信任的应用体验
作为开发者，在享受鸿蒙生态系统带来的广阔市场机遇的同时，也面临着保障用户数据安全和隐私保护的重要责任。同时，开发者需要向用户提供清晰的信息收集和使用的说明，让用户了解自己的数据如何被使用。总的来说，在
阅读更多2024-11-16
基本数据类型：Kotlin、Dart (Flutter)、Java 和 C++ 的比较
本文比较了 Kotlin、Dart (Flutter)、Java 和 C++ 中的基本数据类型，并探讨了有符号和无符号整数的区别。文章还详细解释了二进制补码的计算方式和其在计算机系统中的应用。理解这些
阅读更多2024-11-16

栈和队列面试题（C 语言）

目录

1. 有效的括号

2. 用队列实现栈

3. 用栈实现队列

4. 设计循环队列

相关文章