队列的顺序表实现收尾栈和队列"/>
【数据结构】队列的顺序表实现收尾栈和队列
每一个不曾起舞的日子,都是对生命的辜负。
队列的顺序表实现&&收尾栈和队列
- 1. 队列的概念及结构
- 2. 队列的实现
- Queue.h
- Queue.c
- Test.c
- 3. 栈和队列LeetCode.oj
- 1. 有效的括号
- 2.用队列实现栈
- 3. 用栈实现队列
- 4.设计循环队列
- 4. 总结
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. 有效的括号
20. 有效的括号
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 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.用队列实现栈
225. 用队列实现栈
请你仅使用两个队列实现一个后入先出(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. 用栈实现队列
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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.设计循环队列
622. 设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 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++里一并实现。
更多推荐
【数据结构】队列的顺序表实现收尾栈和队列
发布评论