> 文档中心 > <数据结构>刷题笔记——栈和队列篇(动图详解)

<数据结构>刷题笔记——栈和队列篇(动图详解)

文章目录

  • 1. 有效的括号
    • 【链接】
    • 【思路】
    • 【参考代码】
  • 2. 用队列实现栈
    • 【链接】
    • 【思路】
    • 【参考代码】
  • 3. 用栈实现队列
    • 【链接】
    • 【思路】
    • 【参考代码】
  • 4. 设计循环队列
    • 【链接】
    • 【思路】
    • 【参考代码】

目前在不断更新的知识总结,已经更新完了,未来我会系统地更新等内容。

本系列相关文章
<数据结构>你分得清栈和队列吗?
已完结系列文章总结
c语言自学教程——博文总结
我的gitee,欢迎来看看:gitee网址
想要一步步稳扎稳打,学习编程的小伙伴可以关注我,文章都是免费的,不错过这一个提升自己的机会!

1. 有效的括号

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

有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1:
输入:s = “()”
输出:true

示例 2:
输入:s = “()[]{}”
输出:true

示例 3:
输入:s = “(]”
输出:false

示例 4:
输入:s = “([)]”
输出:false

示例 5:
输入:s = “{[]}”
输出:true

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

【链接】

20. 有效的括号

【思路】

数括号能不能数出来呢?不行,"([)]"的数量符合要求但括号的种类不匹配。
让我们换一种思路,运用我们学到的栈。遇到左括号就入栈,遇到右括号就出栈,栈是后进先出的,出栈出的是最近入进去的括号,如果都可以匹配上,就返回“true”,否则返回“false”。
<数据结构>刷题笔记——栈和队列篇(动图详解)

思路就这捋顺了,接下来就要写代码了。但问题来了,从哪能搞来栈用呢?因为我们还没学到C++在这就只能憋屈得自己写个栈了,我上一篇文章<数据结构>你分得清栈和队列吗?写的栈直接复制过来用,这就是为什么参考代码那么长,其实新东西只有最后那一点。

在此强调一下,一定要保证栈的代码正确再使用,否则会bug重重,很难改。

【参考代码】

typedef int STDataType;typedef struct Stack{int* a;int top;//栈顶的位置int capacity;//容量}ST;void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;}void StackDestory(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;}void StackPush(ST* ps, STDataType x){assert(ps);//满了扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;ps->a = (STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));if (ps->a == NULL){printf("realloc fail");exit(-1);}ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;}void StackPop(ST* ps){assert(ps);assert(ps->top > 0);ps->top--;}bool StackEmpty(ST* ps){assert(ps);return ps->top == 0;}STDataType StackTop(ST* ps){assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];}int StackSize(ST* ps)//元素个数{assert(ps);return ps->top;}bool isValid(char * s){    ST st;    StackInit(&st);    while(*s)    { if(*s == '{'||*s == '['||*s == '(') {     StackPush(&st, *s);     s++; } else {     if(StackEmpty(&st))//防越界  return false;     char top = StackTop(&st);     StackPop(&st);     if((*s == '}' && top != '{')     ||(*s == ']' && top != '[')     ||(*s == ')' && top != '('))     {  StackDestory(&st);  return false;     }     s++; }    }    bool ret = StackEmpty(&st);    StackDestory(&st);    return ret;}

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 都保证栈不为空

进阶:你能否仅用一个队列来实现栈。

【链接】

225. 用队列实现栈

【思路】

用两个队列实现一个栈。两者的最大不同就是队列是先进先出的,栈是后进先出的。
实现入栈就随便把数据放到一个队列里
想要实现出栈,得先把挡在前面的数据放到另一个队列中,最后才能出栈
如果后续还要实现入栈就入到仍有数据的队列中
这是一个典型的接口型OJ题,你需要完善里面的函数。
队列和上一题一样,目前只能用自己写的复制到代码中

<数据结构>刷题笔记——栈和队列篇(动图详解)

【参考代码】

typedef int QDataType;//节点typedef struct QueueNode{QDataType data;struct QueueNode* next;}QNode;//找到头和尾typedef struct Queue{QNode* head;QNode* tail;}Queue;void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void QueuePush(Queue* pq, QDataType x);void QueuePop(Queue* pq);bool QueueEmpty(Queue* pq);size_t QueueSize(Queue* pq);QDataType QueueFront(Queue* pq);QDataType QueueBack(Queue* pq);void QueueInit(Queue* pq){assert(pq);pq->head = pq->tail = NULL;}void QueueDestory(Queue* pq){assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));assert(newnode);newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){assert(pq->head == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq){assert(pq);assert(pq->head && pq->tail);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}}bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}size_t QueueSize(Queue* pq){assert(pq);size_t size = 0;QNode* cur = pq->head;while (cur){size++;cur = cur->next;}return size;}QDataType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->data;}QDataType QueueBack(Queue* pq){assert(pq);assert(pq->tail);return pq->tail->data;}typedef struct {    Queue q1;    Queue q2;} MyStack;MyStack* myStackCreate() {    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));    assert(pst);    QueueInit(&pst->q1);    QueueInit(&pst->q2);    return pst;}void myStackPush(MyStack* obj, int x) {    assert(obj);    if(!QueueEmpty(&obj->q1))    { QueuePush(&obj->q1, x);    }    else    { QueuePush(&obj->q2, x);    }}int myStackPop(MyStack* obj) {    assert(obj);    Queue* emptyQ = &obj->q1;    Queue* nonEmptyQ = &obj->q2;    if(!QueueEmpty(&obj->q1))    { emptyQ = &obj->q2; nonEmptyQ = &obj->q1;    }    //把非空队列的前N个数据,导入空队列,只剩最后一个删掉    //就实现了后进先出    while(QueueSize(nonEmptyQ)>1)    { QueuePush(emptyQ, QueueFront(nonEmptyQ)); QueuePop(nonEmptyQ);    }    int top = QueueFront(nonEmptyQ);    QueuePop(nonEmptyQ);//记得pop掉    return top;}int myStackTop(MyStack* obj) {    assert(obj);    if(!QueueEmpty(&obj->q1))    { return QueueBack(&obj->q1);    }    else    { return QueueBack(&obj->q2);    }}bool myStackEmpty(MyStack* obj) {    assert(obj);    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) {    assert(obj);    QueueDestory(&obj->q1);    QueueDestory(&obj->q2);    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 操作)

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

【链接】

232. 用栈实现队列

【思路】

这跟上一题是姐妹题
但有些不同,因为从一个栈到另一个栈,内容的顺序会颠倒过来,这次我们规定一个固定的实行入队列的栈,和一个固定的出队列的栈。

后续请看动图
<数据结构>刷题笔记——栈和队列篇(动图详解)

【参考代码】

typedef int STDataType;typedef struct Stack{int* a;int top;//栈顶的位置int capacity;//容量}ST;void StackInit(ST* ps);//初始化void StackDestory(ST* ps);//销毁void StackPush(ST* ps, STDataType x);//入栈void StackPop(ST* ps);//出栈bool StackEmpty(ST* ps);//判断栈是否为空STDataType StackTop(ST* ps);//返回栈顶元素int StackSize(ST* ps);//栈里的元素个数void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;}void StackDestory(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;}void StackPush(ST* ps, STDataType x){assert(ps);//满了扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;ps->a = (STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));if (ps->a == NULL){printf("realloc fail");exit(-1);}ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;}void StackPop(ST* ps){assert(ps);assert(ps->top > 0);ps->top--;}bool StackEmpty(ST* ps){assert(ps);return ps->top == 0;}STDataType StackTop(ST* ps){assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];}int StackSize(ST* ps)//元素个数{assert(ps);return ps->top;}typedef struct {    ST pushST;    ST popST;} MyQueue;MyQueue* myQueueCreate() {    MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));    assert(pst);    StackInit(&pst->pushST);    StackInit(&pst->popST);    return pst;}void myQueuePush(MyQueue* obj, int x) {    assert(obj);    StackPush(&obj->pushST,x);}int myQueuePop(MyQueue* obj) {    assert(obj);    //空了再加进去    if(StackEmpty(&obj->popST))    { while(StackSize(&obj->pushST)) {     StackPush(&obj->popST, StackTop(&obj->pushST));     StackPop(&obj->pushST); }    } int head = StackTop(&obj->popST);    StackPop(&obj->popST);    return head;}int myQueuePeek(MyQueue* obj) {     assert(obj);    //空了再加进去    if(StackEmpty(&obj->popST))    { while(StackSize(&obj->pushST)) {     StackPush(&obj->popST, StackTop(&obj->pushST));     StackPop(&obj->pushST); }    } int head = StackTop(&obj->popST);    return head;}bool myQueueEmpty(MyQueue* obj) {    assert(obj);    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST) ;}void myQueueFree(MyQueue* obj) {    assert(obj);    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);*/

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 的范围内;
请不要使用内置的队列库。

【链接】

622. 设计循环队列

【思路】

为了能用head和tail判断队列是满还是空,我们想要存放n个数据得开辟n+1个空间。
这样的话front=tail时是空,tail+1=front时(不越界的情况)是满,能够区别开
这题用顺序表或链表都能实现,我为了更方便的找到尾元素就打算用顺序表(数组)实现一下,这个的要小心到了数组尾部要回到头部再走

<数据结构>刷题笔记——栈和队列篇(动图详解)

【参考代码】

typedef struct {    int* a;    int front;    int tail;    int k;} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));    obj->a = (int*)malloc(sizeof(int)*(k+1));    obj->front = obj->tail = 0;    obj->k = k;    return obj;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {    assert(obj);    if(myCircularQueueIsFull(obj)) return false;    obj->a[obj->tail] = value;    if(obj->tail == obj->k)    { obj->tail = 0;    }    else    { obj->tail++;    }    return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) {    assert(obj);    if(myCircularQueueIsEmpty(obj)) return false;    if(obj->front == obj->k)    { obj->front = 0;    }    else    { obj->front++;    }    return true;}int myCircularQueueFront(MyCircularQueue* obj) {    assert(obj);    if(!myCircularQueueIsEmpty(obj))    { return obj->a[obj->front];    }    else    { return -1;    }}int myCircularQueueRear(MyCircularQueue* obj) {    assert(obj);    if(!myCircularQueueIsEmpty(obj))    { if(obj->tail == 0) {     return obj->a[obj->k]; } else {     return obj->a[obj->tail-1]; }    }    else    { return -1;    }}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {    assert(obj);    return obj->front == obj->tail;}bool myCircularQueueIsFull(MyCircularQueue* obj) {    assert(obj);    if(obj->tail == obj->k)    { return obj->front == 0;    }    else    { return obj->front == obj->tail+1;    }}void myCircularQueueFree(MyCircularQueue* obj) {    assert(obj);    free(obj->a);    free(obj);    obj = NULL;}/** * 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);*/

动图花了我很多心思,希望对大家有所帮助。☀️
由于本人实力有限,如果文中出现错误❌请提出来。
如果觉得有所收获,还请点个赞❤️鼓励一下博主。😉
还不太懂的朋友也不要失落😔,先收藏起来,等到合适的时机再看一看,也许能够恍然大悟🌈,有所得。
系列还在不断更新,关注我,跟我一起一步一步学习数据结构把!😄