队列的顺序表实现&&收尾栈和队列
1. 队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
- 队列与栈的区别是出的顺序恰好相反
2. 队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，需要将后面的元素覆盖到前面，复杂度为O(N)，效率会比较低。
结构体的封装：
typedef int QDataType; typedef struct QueueNode//定义节点 { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue//通过定义此结构体记录队列的头、尾、大小 { QNode* head; QNode* tail; int size; }Queue;
Queue.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode { QDataType* data; struct Queue* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; void QueueInit(Queue* pq);// 初始化队列 void QueueDestory(Queue* pq);// 销毁队列 void QueuePush(Queue* pq,QDataType x);// 队尾入队列 void QueuePop(Queue* pq);// 队头出队列 QDataType QueueFront(Queue* pq);// 获取队列头部元素 QDataType QueueBack(Queue* pq);// 获取队列队尾元素 bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueSize(Queue* pq);// 获取队列中有效元素个数
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } else { newnode->data = x; newnode->next = NULL; } if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* del = pq->head; pq->head = pq->head->next; free(del); } pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL && pq->tail == NULL; } int QueueSize(Queue* pq) { assert(pq); return pq->size; }
Test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void TestQueue() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); printf("%d ", QueueFront(&q)); QueuePop(&q); printf("%d ", QueueFront(&q)); QueuePop(&q); QueuePush(&q, 4); QueuePush(&q, 5); QueuePush(&q, 6); printf("\n"); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); }printf("\n"); } int main() { TestQueue(); return 0; }
3. 栈和队列LeetCode.oj
由于此语言为C语言，因此我们在实现oj之前需要将之前的代码复制进去，否则没有对应封装好的函数
1. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 1.左括号必须用相同类型的右括号闭合。
- 2.左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}" 输出：true
示例 3：
输入：s = "(]" 输出：false
示例 4：
输入：s = "([)]" 输出：false
示例 5：
输入：s = "{[]}" 输出：true
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
思路：这是一道利用栈解决的问题，即下一个进来的如果是左括号则储存，是右括号则看与栈顶的元素是否匹配，若匹配，栈顶元素弹出，继续执行，若不匹配，则返回false。需要注意的是，若所有的元素都分配完毕，此时栈仍不为空，这说明不匹配，返回false.
typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps, STDataType x); void StackPop(ST* ps); STDataType StackTop(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST* ps); void StackInit(ST* ps) { ps->a = NULL; ps->top = ps->capacity = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; } STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } 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); } else { if(StackEmpty(&st)) return false; STDataType obj = StackTop(&st); if((obj == '{' && *s == '}')|| (obj == '[' && *s == ']')|| (obj == '(' && *s == ')')) { StackPop(&st); } else { return false; } } s++; } if(st.top!=0) return false; return true; }
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 都保证栈不为空
**进阶：**你能否仅用一个队列来实现栈。
思路：很明显的是，栈的特点是先进后出，队列的特点是先进先出，那么如何用先进先出的队列实现先进后出的栈呢？这就不仅仅依靠一个队列了，而是两个队列元素之间的相互转换，如：q1 : 1 、2、3、4、5
q2:NULL;那么如何将其Top时变成5、4、3、2、1？
这就需要画图去思考：
按正常逻辑，对于队列应该是1->2->3->4->5的顺序弹出队列，但要其相反，我们就要：将q1的前4个元素移到q2,再弹出q1的时候就是最后进的元素了。
于是这个步骤就可以反复执行，直到两个队列均变成空。
代码实现：
typedef int QDataType; typedef struct QueueNode { QDataType* data; struct Queue* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; void QueueInit(Queue* pq);// 初始化队列 void QueueDestory(Queue* pq);// 销毁队列 void QueuePush(Queue* pq,QDataType x);// 队尾入队列 void QueuePop(Queue* pq);// 队头出队列 QDataType QueueFront(Queue* pq);// 获取队列头部元素 QDataType QueueBack(Queue* pq);// 获取队列队尾元素 bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueSize(Queue* pq);// 获取队列中有效元素个数 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } else { newnode->data = x; newnode->next = NULL; } if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* del = pq->head; pq->head = pq->head->next; free(del); } pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL && pq->tail == NULL; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { Queue* empty = &obj->q1; Queue* nonempty = &obj->q2; if(!QueueEmpty(&obj->q1)) { nonempty = &obj->q1; empty = &obj->q2; } while(QueueSize(nonempty)>1) { QueuePush(empty,QueueFront(nonempty)); QueuePop(nonempty); } int top = QueueFront(nonempty); QueuePop(nonempty); return top; } int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { 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); */
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) ，即使其中一个操作可能花费较长时间。
思路：对于这道题，思想与上道题一样，只是变化了对象，用两个先进后出实现先进先出，但值得注意的是， 由于栈先进后出的特点，经过调换，没必要像上道题一样来回反复移动，而是定义一个专门用来push的，另一个专门用来Top的：
输出的时候将pushST的全部导入popST：
这样就可以实现队列的先进先出的原则。
代码：
typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void StackInit(ST* ps);//ʼ void StackDestory(ST* ps);// void StackPush(ST* ps, STDataType x); void StackPop(ST* ps); STDataType StackTop(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST* ps); void StackInit(ST* ps) { ps->a = NULL; ps->top = ps->capacity = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } void StackPush(ST* ps, STDataType x) { if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; } STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; } typedef struct{ ST pushST; ST popST; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&obj->pushST); StackInit(&obj->popST); return obj; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushST,x); } int myQueuePop(MyQueue* obj) { if(StackEmpty(&obj->popST)) { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } int front = StackTop(&obj->popST); StackPop(&obj->popST); return front; } int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popST)) { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } return StackTop(&obj->popST); } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST); } void myQueueFree(MyQueue* 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 的范围内；
请不要使用内置的队列库。
对于此题，是队列，但是并不像前几道题一样，需要我们将之前的函数代码放到里面，而是需要自己去实现。上述已经说过，队列既可以由链表实现，也可以由数组实现，而在上述中的创建空间的接口中用的是链表实现，对于此题，如果用链表实现的话，则需要不断地开辟新节点来构造此空间，而用数组一步malloc就可以创建，相比较，前者较为麻烦，因此，在这里，我们采用数组。
既然是循环数组，我们有两种方式判断其是否满或者空，一是创建时用一个size来记录数量，二是利用循环的特性，设置两个下标，head代表头，tail代表尾，为了凸显循环的特性，我们采用后者。那么，如何利用这两个下标指针判断其是否为空为满呢？
这时大概率会想到：当head与tail重合的时候，是否就可以看成满了呢？好，那顺着这个来，当我们定义head=tail=0的时候，内部没有元素，head与tail都在起始位置，即head = tail = 0,然而此时却是空，这代表着我们之前构建的大思路错误了吗？当然不是，大家也会猜到，如果都是错误的，何必这么大费周章呢？既然大思路没错，我们就想一想如何改善这个判断空和满的条件，这里也就不卖关子了，可以进行如下改善：让malloc出来的空间比需要的空间多一个，但这最后一个并不存储数据，恰恰作为一个条件，当尾指针走到这里，就说明满，当尾指针与头指针重合就可以代表空 ，但是利用数组的话，如何让其尾指针走到头的位置呢？这里采用的是取模，即tail%N。
举个例子：当我们需要构建四个空间放置元素，此时我们应多开辟一个空间即N = 5
此时，数组的空间已满,由于head和tail都是数组下标，默认从0开始，而tail到图中的位置时tail恰好等于4，可以看出，当（tail+1)%N == head时，就代表满。
接下来看看如何判空：
由于是循环队列，每次tail改变我们都需要让tail = tail%N，目的是让其的指向可以循环，通过上图可以看出head == tail时即可判空，（或者tail%N == head%N)。
那么，最关键的接口我们的逻辑已经推演完成，接下来看看代码吧！(注：这里的头和尾分别用的是front和back)
typedef struct { int* a; int front; int back; int N; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a = (int*)malloc(sizeof(int)*(k+1)); obj->front = obj->back = 0; obj->N = k+1; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->back == obj->front; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->back+1) % obj->N == obj->front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->a[obj->back] = value; obj->back++; obj->back %= obj->N; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->front++; obj->front %=obj->N; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[(obj->back-1+obj->N)%obj->N]; } void myCircularQueueFree(MyCircularQueue* obj) { 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); */
4. 总结
到这里，栈和队列的讲解基本上就完成了，但这里由于我们用的C语言实现，接口都需要自己提供，因此只是让大家了解以及能够面对一些oj题，更加复杂的内容将会在C++里一并实现。
