爆肝两万字，我爷爷都看的懂的《栈和队列》，建议各位观众姥爷先收藏下-阿里云开发者社区

三、栈和队列面试题

💦 括号匹配问题 <难度系数⭐>

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

有效字符串需满足：

1️⃣ 左括号必须用相同类型的右括号闭合。

2️⃣ 左括号必须以正确的顺序闭合。

💨 示例1：

输入：s = “()”

输出：true

💨 示例2：

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

输出：true

💨 示例3：

输入：s = “(]”

输出：false

💨 示例4：

输入：s = “([)]”

输出：false

💨 示例5：

输入：s = “{[]}”

输出：true

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：这里我们自己实现一个栈(具体看下图)

leetcode原题

//结构体
typedef char STDatatype;
typedef struct Stack
{
  STDatatype* a; //指向动态开辟的空间
  int top; //栈顶
  int capacicy; //容量
}ST;
//函数 
//注意链表和顺序表我们写Print，但是栈不写，因为如果栈可以Print的话，就不符合后进先出了
  //初始化
void StackInit(ST* ps);
  //插入
void StackPush(ST* ps, STDatatype x);
  //判空
bool StackEmpty(ST* ps);
  //删除
void StackPop(ST* ps);
  //长度
int StackSize(ST* ps);
  //栈顶
STDatatype StackTop(ST* ps);
  //销毁
void StackDestory(ST* ps);
bool isValid(char* s){
    ST st;
    StackInit(&st); 
    //match记录真假
    bool match = true;
    while(*s)
    {
        //如果*s等于左括号其中一个则入栈
        if(*s == '[' || *s == '(' || *s == '{')
        {
            StackPush(&st, *s);
            ++s;
        }
        //否则*s等于右括号，出栈里的数据进行匹配
        else
        {
            //如果字符串里只有右括号时，返回false
            if(StackEmpty(&st))
            {
                match = false;
                break;
            }
            //取栈顶的数据 (ch是已经入栈的数据，*s是还未入栈的数据) 
            char ch = StackTop(&st);
            //出栈 '{[]}'为了取上一个数据
            StackPop(&st); 
            //比较
                //不匹配
            if((*s == ']' && ch != '[') 
            || (*s == '}' && ch != '{')
            || (*s == ')' && ch != '('))
            {
                match = false;
                break;                
            }
                //匹配
            else
            {
                ++s;
            }
        }
    }
    if (match == true)
    {
        //如果字符串只有一个左括号时，StackEmpty会返回false
        match = StackEmpty(&st);
    }
    //统一回收
    StackDestory(&st);
    return match;
}
void StackInit(ST* ps)
{
  assert(ps);
  //初始化
  ps->a = NULL;
  ps->top = 0;
  ps->capacicy = 0;
}
void StackPush(ST* ps, STDatatype x)
{
  assert(ps);
  //检查空间，满了就增容
  if (ps->top == ps->capacicy)
  {
    //第一次开辟空间容量为4，其它次容量为当前容量*2
    int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;
    //第一次开辟空间，a指向空，realloc的效果同malloc
    STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);
    //检查realloc
      //realloc失败
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
      //realloc成功
    ps->a = tmp;
    ps->capacicy = newcapacity;
  }
  //插入数据 
  ps->a[ps->top] = x;
  ps->top++;
}
bool StackEmpty(ST* ps)
{
  assert(ps); 
  //等于0是真，否则为假
  return ps->top == 0;
}
void StackPop(ST* ps)
{
  assert(ps);
  //删除的话得保证指向的空间不为空
  assert(!StackEmpty(ps));
  //删除
  --ps->top;
}
STDatatype StackTop(ST* ps)
{
  assert(ps);
  //找栈顶的话得保证指向的空间不为空
  assert(!StackEmpty(ps));
  //此时的top-1就是栈顶数据
  return ps->a[ps->top - 1];
}
void StackDestory(ST* ps)
{
  assert(ps);
  //a为真代表它指向动态开辟的空间
  if (ps->a)
  {
    free(ps->a);
  }
  ps->a = NULL;
  ps->top = 0;
  ps->capacicy = 0;
}
int main()
{
  char arr[] = "{[]}";
  printf("%d\n", isValid(arr));
  return 0;
}

💦 用队列实现栈 <难度系数⭐>

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

实现 MyStack 类：

1️⃣ void push(int x) 将元素 x 压入栈顶。

2️⃣ int pop() 移除并返回栈顶元素。

3️⃣ int top() 返回栈顶元素。

4️⃣ boolean empty() 如果栈是空的，返回 true ；否则，返回 false

⚠ 注意

1️⃣ 你只能使用队列的基本操作——也就是push to back、peek/pop from front、size和is empty这些操作。

2️⃣ 你所使用的语言也许不支持队列。你可以使用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️⃣ 1 <= x <= 9

2️⃣ 最多调用100 次 push、pop、top 和 empty

3️⃣ 每次调用 pop 和 top 都保证栈不为空

⚜ 进阶

你能否实现每种操作的均摊时间复杂度为 O(1) 的栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：队列的数据是不能从队尾出的，只能从队头出，而这里要实现的是队列实现栈，所以只能遵循栈的特性——后进先出。这里就需要另外一个队列，具体步骤如下：

1、一个队列有数据，一个队列没数据

2、入数据时向不为空的那个入

3、出数据时，就将不为空的队列的前 size-1 个拷贝至另一个队列，然后再Pop掉剩下的一个数据

leetcode原题

//声明
    //结构体
typedef int QDataType;
typedef struct QueueNode
{
  struct QueueNode* next; //指向下一个节点
  QDataType data; //存储整型数据
}QueueNode;
typedef struct Queue
{
  QueueNode* phead;//头指针
  QueueNode* ptail;//尾指针
}Queue;
    //函数
void QueueInit(Queue* pq); 
void QueuePush(Queue* pq, QDataType x); 
bool QueueEmpty(Queue* pq);
void QueuePop(Queue* pq);
QDataType QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueDestory(Queue* pq);
//函数实现
void QueueInit(Queue* pq)
{
  assert(pq);
  //把2个指针置空
  pq->phead = pq->ptail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  //malloc空间,如果需要频繁的开辟空间建议再实现一个BuyQueueNode用于malloc
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  //第一次插入
  if (pq->phead == NULL)
  {
    pq->phead = pq->ptail = newnode;
  }
  //非第一次插入
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  //空链表返回true，非空链表返回false
  return pq->phead == NULL;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  //链表为空时不能删除
  assert(!QueueEmpty(pq));
  //只有一个节点的情况
  if (pq->phead->next == NULL)
  {
    free(pq->phead);
    pq->phead = pq->ptail = NULL;
  }
  //多个节点的情况
  else
  {
    QueueNode* next = pq->phead->next;
    free(pq->phead) ;
    pq->phead = next;
  }
}
QDataType QueueSize(Queue* pq)
{
  assert(pq);
  //如果需要频繁的调用QueueSize这个接口，可以在Queue这个结构体中增加一个成员用于记录长度
  int sz = 0;
  QueueNode* cur = pq->phead;
  while (cur)
  {
    sz++;
    cur = cur->next;
  }
  return sz;
}
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  //链表为空时不能取头
  assert(!QueueEmpty(pq));
  return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  //链表为空时不能取尾
  assert(!QueueEmpty(pq));
  return pq->ptail->data;
}
void QueueDestory(Queue* pq)
{
  assert(pq);
  QueueNode* cur = pq->phead;
  //遍历链表
  while (cur)
  {
    QueueNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->phead = pq->ptail = NULL;
}
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
/** Initialize your data structure here. */
MyStack* myStackCreate() {
    //malloc空间
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    //Init两个队列
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}
/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    assert(obj);
    //QueueEmpty为空时返回true，不为空时返回false
        //往不为空的那个队列里插入数据(q1不为空往q1插入，q2不为空往q2插入)
    if(!QueueEmpty(&obj->q1))
    {
        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) {
    assert(obj);
    //先默认q1为空，q2不为空
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    //q1不为空，重新赋值
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    //拷贝 - 将非空队列的size-1个数据拷贝
    while(QueueSize(nonemptyQ) > 1)
    {
        //将非空的队列拷贝至空的队列
        QueuePush(emptyQ, QueueFront(nonemptyQ));
        //删除迭代
        QueuePop(nonemptyQ);
    }
    //top记录非空队列的剩下一个值
    int top = QueueFront(nonemptyQ);
    //删除非空队列的剩下一个数据，这个数据就是栈顶的数据
    QueuePop(nonemptyQ);
    //返回
    return top;
}
/** Get the top element. */
int myStackTop(MyStack* obj) {
    assert(obj);
    //q1不为空，取q1的数据
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    //q2不为空，取q2的数据
    else
    {
        return QueueBack(&obj->q2);
    }
}
/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
    assert(obj);
    //q1和q2一定有一个为空
    //q1为空返回真，q2为空返回真，mystackEmpty为空返回真;
    //q1为空返回真，q2为非空返回假，myStackEmpty为非空，返回假
    //q1为非空返回假，q2为空返回真，myStackEmpty为非空，返回假
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
    assert(obj);
    //结合上面的代码分析我们需要回收两个队列和myStackcreate里malloc的空间
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
}
/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 * int param_2 = myStackPop(obj);
 * int param_3 = myStackTop(obj);
 * bool param_4 = myStackEmpty(obj);
 * myStackFree(obj);
*/

💦 用栈实现队列 <难度系数⭐>

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

实现 MyQueue 类：

1️⃣ void push(int x) 将元素 x 推到队列的末尾。

2️⃣ int pop() 从队列的开头移除并返回元素。

3️⃣ int top() 返回队列开头的元素。

4️⃣ boolean empty() 如果队列是空的，返回 true ；否则，返回 false

⚠ 注意

1️⃣ 你只能使用标准的栈操作 —— 也就是只有push to top，peek/pop from top，和 is empty 操作是合法的。

2️⃣ 你所使用的语言也许不支持栈。你可以使用 list 或者 deque (双端队列) 来模拟一个栈，只要是标准的栈操作即可。

⚜ 进阶

你能否实现每个操作均摊时间复杂度为0(1)的队列?换句话说，执行 n 个操作的总时间复杂度为o(n)，即使其中一个操作可能花费较长时间。

💨 示例：

输入：

[“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️⃣ 1 <= x <= 9

2️⃣ 最多调用100 次 push、pop、top 和 empty

3️⃣ 假设所有操作都是有效的 (例如，一个空的队列不会调用 pop 或者 peek 操作)

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

1、入数据，进 pushst

2、出数据，看 popst 是否为空，如果为空，就先把 pushst 的数据倒过来，然后出数据；如果不为空，则直接出 popst 的数据

leetcode原题

//一、声明
    //结构体
typedef int STDatatype;
typedef struct Stack
{
  STDatatype* a; //指向动态开辟的空间
  int top; //栈顶
  int capacicy; //容量
}ST;
    //函数 
      //初始化
void StackInit(ST* ps);
      //插入
void StackPush(ST* ps, STDatatype x);
      //判空
bool StackEmpty(ST* ps);
      //删除
void StackPop(ST* ps);
      //长度
int StackSize(ST* ps);
  //栈顶
STDatatype StackTop(ST* ps);
      //销毁
void StackDestory(ST* ps);
//二、实现
void StackInit(ST* ps)
{
  assert(ps);
  //初始化
  ps->a = NULL;
  ps->top = 0;
  ps->capacicy = 0;
}
void StackPush(ST* ps, STDatatype x)
{
  assert(ps);
  //检查空间，满了就增容
  if (ps->top == ps->capacicy)
  {
    //第一次开辟空间容量为4，其它次容量为当前容量*2
    int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;
    //第一次开辟空间，a指向空，realloc的效果同malloc
    STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);
    //检查realloc
      //realloc失败
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
      //realloc成功
    ps->a = tmp;
    ps->capacicy = newcapacity;
  }
  //插入数据 
  ps->a[ps->top] = x;
  ps->top++;
}
bool StackEmpty(ST* ps)
{
  assert(ps); 
  //等于0是真，否则为假
  return ps->top == 0;
}
void StackPop(ST* ps)
{
  assert(ps);
  //删除的话得保证指向的空间不为空
  assert(!StackEmpty(ps));
  //删除
  --ps->top;
}
int StackSize(ST* ps)
{
  assert(ps);
  //此时的top就是长度
  return ps->top;
}
STDatatype StackTop(ST* ps)
{
  assert(ps);
  //找栈顶的话得保证指向的空间不为空
  assert(!StackEmpty(ps));
  //此时的top-1就是栈顶数据
  return ps->a[ps->top - 1];
}
void StackDestory(ST* ps)
{
  assert(ps);
  //a为真代表它指向动态开辟的空间
  if (ps->a)
  {
    free(ps->a);
  }
  ps->a = NULL;
  ps->top = 0;
  ps->capacicy = 0;
}
typedef struct {
    ST pushST;
    ST popST;
} MyQueue;
/** Initialize your data structure here. */
//malloc空间
MyQueue* myQueueCreate() {
    //malloc一块MyQueue类型大小的空间
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    //初始化
    StackInit(&q->pushST);
    StackInit(&q->popST);
    //返回MyQueue这块空间的地址 
    return q;
}
/** Push element x to the back of queue. */
//插入
void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    //往pushST这个结构体里插入
    StackPush(&obj->pushST, x);
}
/** Get the front element. */
//取队头
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    //如果popST为空，则倒pushST的数据，再取队头
    if(StackEmpty(&obj->popST))
    {
        //popST内有数据，返回false，再非
        while(!StackEmpty(&obj->pushST))
        {
            //把pushST栈顶的数据插入至popST
            StackPush(&obj->popST, StackTop(&obj->pushST));
            //迭代
            StackPop(&obj->pushST); 
        }
    }
    //如果popST不为空，直接取队头
    return StackTop(&obj->popST);
}
/** Removes the element from in front of queue and returns that element. */
//删除
int myQueuePop(MyQueue* obj) {
    assert(obj);
    //如果popST为空，则倒pushST的数据，再出数据
    if(StackEmpty(&obj->popST))
    {
        //popST内有数据，返回false，再非
        while(!StackEmpty(&obj->pushST))
        {
            //把pushST栈顶的数据插入至popST
            StackPush(&obj->popST, StackTop(&obj->pushST));
            //迭代
            StackPop(&obj->pushST); 
        }
    }
        //备份popST内栈顶的数据，用于返回
    int front = StackTop(&obj->popST);
    //如果popST不为空，直接出数据
    StackPop(&obj->popST);
    //返回popST栈顶的数据
    return front;
}
/** Returns whether the queue is empty. */
//判空
bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    //pushST和popST同时为空，才为空
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
//回收
void myQueueFree(MyQueue* obj) {
    assert(obj);
    //上面的代码中，我们先malloc了一块MyQueue类型的空间，在插入的操作接口中又malloc了pushST和popST
    StackDestory(&obj->pushST);
    StackDestory(&obj->popST);
    free(obj);
}
/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 * int param_2 = myQueuePop(obj);
 * int param_3 = myQueuePeek(obj);
 * bool param_4 = myQueueEmpty(obj);
 * myQueueFree(obj);
*/

💦 设计循环队列 <难度系数⭐⭐>

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

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

你的实现应该支持如下操作：

1️⃣ MyCircularQueue(k): 构造器，设置队列长度为 k 。

2️⃣ Front: 从队首获取元素。如果队列为空，返回 -1 。

3️⃣ Rear: 获取队尾元素。如果队列为空，返回 -1 。

4️⃣ enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

5️⃣ deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

6️⃣ isEmpty(): 检查循环队列是否为空。

7️⃣ 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

🍳 提示

1️⃣ 所有的值都在 0 至 1000 的范围内；

2️⃣ 操作数将在 1 至 1000 的范围内；

3️⃣ 请不要使用内置的队列库。

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

问题一，使用数组还是链表 ❔❓

这里使用数组和链表都可以，但是使用数组的缓存利用率更高，且用链表(单链表)实现某些接口时会很恶心

问题二，数组和链表怎么构成环形 ❔❓

1、需要两个指针，head指向下标0，tail指向下标3，tail只要超过数组长度，就回到head的位置

2、让链表的最后一个节点不再指向空，而是指向第一个节点

问题三，怎么判断满与不满，空与非空， head 和 tail 一开始都是指向起始位置，说明为空；当最后一块空间插入数据后，tail 回到起始位置，说明为满。这就形成了矛盾) ❔❓

无论是数组还是链表都额外给一块空间。  (注意这里只是形象的说法) 如果 tail == head 则为空；如果 tail + 1 == head 则为满

leetcode原题

typedef struct {
    int* a;//指向开辟的空间
    int front;//首
    int rear;//尾
    int k; //记录当前有效数据个数
} MyCircularQueue;
//开辟空间
MyCircularQueue* myCircularQueueCreate(int k) {
    //先malloc一块MyCircularQueue类型的空间
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //再malloc指定的k个int类型的空间(注意这里需要额外一块空间)
    q->a = (int*)malloc(sizeof(int) * (k + 1));
    //初始化
    q->front = 0;
    q->rear = 0;
    q->k = k;
    //返回结构体的地址
    return q;
}
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    //当front等于rear时，队列为空
    return obj->front == obj->rear;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    //当front等于rear+1时则为满(但要防止rear+1越界)
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
//插入数据 - 不能插入返回false，能插入返回true
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    //myCircularQueueIsFull判断队列是否为满
        //满了，返回真
    if(myCircularQueueIsFull(obj))
        return false;
        //不满，插入数据
    obj->a[obj->rear] = value;
    obj->rear++;    
        //当数组的最后一块空间插入数据时，rear++会越界
    if(obj->rear == obj->k+1)
        obj->rear = 0;
        //至此，返回真
    return true;
}
//删除数据 - 不能删除返回false，能删除返回true
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    //myCircularQueueIsEmpty判断队列是否为空
        //空了，返回真，
    if(myCircularQueueIsEmpty(obj))
        return false;   
        //不空，删除数据，(这里只需要让front往后走即可)
    obj->front++;
        //当数组的最后一块空间删除数据时，front++会越界
    if(obj->front == obj->k+1)
        obj->front = 0;
        //至此，返回真
    return true;
}
//获取队头的数据 
int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    //如果队列为空返回-1
    if(myCircularQueueIsEmpty(obj))
        return -1;
    //返回队头
    return obj->a[obj->front];
}
//获取队尾的数据 
int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    //如果队列为空返回-1
    if(myCircularQueueIsEmpty(obj))
        return -1;
    //获取队尾(这里myCircularQueueEnQueue插入数据后tail++，所以队尾是tail)
    //prevRear记录前一个
    int prevRear = obj->rear - 1;
    //当rear是下标为0的那块空间时，prevRear就是k
    if(obj->rear == 0)
        prevRear = obj->k;
    //返回队尾
    return obj->a[prevRear];
}
//回收空间
void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);
    //在上面的代码中我们malloc了两次的空间，先回收结构体内成员的空间，再回收结构体
    free(obj->a);
    free(obj);
}
/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 * bool param_2 = myCircularQueueDeQueue(obj);
 * int param_3 = myCircularQueueFront(obj);
 * int param_4 = myCircularQueueRear(obj);
 * bool param_5 = myCircularQueueIsEmpty(obj);
 * bool param_6 = myCircularQueueIsFull(obj);
 * myCircularQueueFree(obj);
*/

四、概念选择题

💦 1

1、一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是 ( )

A. 12345ABCDE

B. EDCBA54321

C. ABCDE12345

D. 54321EDCBA

📝 解析：B，根据栈的特点 —— 后进先出，先进后出，可以得到正确答案

💦 2

2、若进栈的序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是 ( )

A. 1，4，3，2

B. 2，3，4，1

C. 3，1，4，2

D. 3，4，2，1

📝 解析：C，本题需要注意的是进栈过程中可以出栈，这也导致了多种情况的出现：

进栈顺序：1 2 3 4

出栈顺序：1 2 3 4

4 3 2 1

… …

💦 3

3、循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后， front=rear=99 ，则循环队列中的元素个数为（）

A. 1

B. 2

C. 99

D. 0

📝 解析：D，当循环队列进行一系列操作后，front == rear 说明为空；front == rear+1 说明为满

💦 4

4、以下( )不是队列的基本运算？

A. 从队尾插入一个新元素

B. 从队列中删除第i个元素

C. 判断一个队列是否为空

D. 读取队头元素的值

📝 解析：B，从队列的特性先进先出，后进后出即可知道答案

💦 5

5、现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N，实际最多存储 N - 1 个数据。其队内有效长度为？（）

A. (rear - front + N) % N + 1

B. (rear - front + N) % N

C. (ear - front) % (N + 1)

D. (rear - front + N) % (N - 1)

📝 解析：B，

这里分为两种情况：

1️⃣ 队列的有效长度是 (rear - front + N) % N == 3

对于第 1 种情况来说只需要 rear - front 即可，为什么还需要 +N 再 % N ❓❔

因为这里还有第 2 种情况，而仅仅是 rear - front 这个公式是不能满足第 2 种情况的

2️⃣ 队列的有效长度是 (rear - front + N) % N == 4

对于第 2 种情况来说只需要 rear + N - front 即可，为什么还需要 +N 再 % N ❓❔

因为本题是只有 1 个正确答案，所以还要顾虑到第 1 种情况，需要寻找能同时适用于两种情况的 1 个公式

爆肝两万字，我爷爷都看的懂的《栈和队列》，建议各位观众姥爷先收藏下

三、栈和队列面试题

💦 括号匹配问题 <难度系数⭐>

💦 用队列实现栈 <难度系数⭐>

💦 用栈实现队列 <难度系数⭐>

💦 设计循环队列 <难度系数⭐⭐>

四、概念选择题

💦 1

💦 2

💦 3

💦 4

💦 5

热门文章

最新文章

相关课程

相关电子书

相关实验场景

爆肝两万字，我爷爷都看的懂的《栈和队列》，建议各位观众姥爷先收藏 下

三、栈和队列面试题

💦 括号匹配问题 <难度系数⭐>

💦 用队列实现栈 <难度系数⭐>

💦 用栈实现队列 <难度系数⭐>

💦 设计循环队列 <难度系数⭐⭐>

四、概念选择题

💦 1

💦 2

💦 3

💦 4

💦 5

热门文章

最新文章

相关课程

相关电子书

相关实验场景

爆肝两万字，我爷爷都看的懂的《栈和队列》，建议各位观众姥爷先收藏下