队列及笔试题

队列

先进先出

使用单链表进行队尾插入 队头删除

其中带头结点直接尾插，不带头结点第一次操作要判断一下

但是带头结点需要malloc和free

函数传需要修改的参数方法

1、二级指针

2、带哨兵位的头结点

3、返回值

4、如果有多个值，用结构体封装起来

可以把头指针和尾指针放到结构体里面，就不用二级指针了。

他们是结构体成员，想要改变就可以用结构体指针

Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int QDataType;typedef struct QueueNode {QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue {QNode* phead;QNode* ptail;int size;
}Queue;void QInit(Queue* pq);
void QDestroy(Queue* pq);
void QPush(Queue* pq, QDataType x);
void QPop(Queue* pq);//取队头的数据
QDataType QFront(Queue* pq);//取队尾的数据
QDataType QBack(Queue* pq);//判断链表是否为空
bool QEmpty(Queue* pq);//求队长度
int QSize(Queue* pq);

Queue.c

#define  _CRT_SECURE_NO_WARNINGS
#include"Queue.h"void QInit(Queue* pq) {assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}void QDestroy(Queue* pq) {assert(pq);QNode* cur = pq->phead;while (cur) {pq->phead = pq->phead->next;free(cur);cur = pq->phead;pq->size --;}pq->ptail = NULL;
}void QPush(Queue* pq, QDataType x) {assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc");return;}newnode->next = NULL;newnode->val = x;if (pq->phead == NULL) {pq->phead = newnode;pq->ptail = newnode;}else {pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}void QPop(Queue* pq) {assert(pq);assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL) {pq->ptail = NULL;}pq->size--;
}//取队头的数据
QDataType QFront(Queue* pq) {assert(pq);assert(pq->phead);return pq->phead->val;
}//取队尾的数据
QDataType QBack(Queue* pq) {assert(pq);assert(pq->phead);return pq->ptail->val;
}//判断链表是否为空
bool QEmpty(Queue* pq) {assert(pq);return pq->phead == NULL;
}//求队长度
int QSize(Queue* pq) {assert(pq);return pq->size;
}

Test.c

#define  _CRT_SECURE_NO_WARNINGS
#include"Queue.h"int main() {Queue q;QInit(&q);QPush(&q, 1);QPush(&q, 2);QPush(&q, 3);QPush(&q, 4);QPush(&q, 5);int size = QSize(&q);printf("%d\n", size);while (!QEmpty(&q)) {printf("%d ", QFront(&q));QPop(&q);}printf("\n");size = QSize(&q);printf("%d\n", size);QDestroy(&q);
}

练习：

用队列实现栈

这里有typedef，MyStack就是类型

没有typedef，MyStack就是变量，且这个结构体只能创建这一个变量

思路：

空的队列用来出仅存的那一个数据

满的队列用来存剩下的全部数据

如果直接free(obj)，则相当于只free了这个结构体，但是链表里可能还有数据，所以要先分别Destroy一下

用栈实现队列

思路：

1、建立两个栈，一个用来存放数据（pushst），一个用来改变成正确的顺序然后出栈（popst）

      等popst出空了再倒过来数据，效率更高

2、凡是看到这样一个返回值，都需要malloc，否则只是创建了局部变量，出了作用域就被销毁了

3、此处可以手动初始化栈，也可以调用之前写好的完整的一套函数去初始化（推荐）

访问结构体里的变量用 . 

4、内部实现

STInit需要传的是栈的地址，对栈进行操作

5、结构体 和 结构体的指针 是有区别的，结构体的指针只是一个地址。

如果定义结构体时定义成了上面这样

则相当于malloc了pushst和popst这两个指针，但是这两个指针没有具体只的内容和空间，如果没有初始化就是野指针。同时还需要malloc栈的空间