宁波网站建设方案报价,长沙网开亿面做网站多少钱,公司域名让做网站的,大专有什么专业可以选目录 一、队列的概念及结构
二、队列的实现 拓展#xff1a;循环队列
三、初学的队列以及栈和队列结合的练习题 一、队列的概念及结构
队列#xff1a;只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff0c;队列具有先进先出FIFO(Fi…目录 一、队列的概念及结构
二、队列的实现 拓展循环队列
三、初学的队列以及栈和队列结合的练习题 一、队列的概念及结构
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 二、队列的实现
队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 具体代码如下C语言实现
#pragma once//Queue.h
// 链式结构表示队列#include stdio.h
#include stdlib.h
#include assert.htypedef int QDateType;typedef struct QListNode
{struct QListNode* _next;QDateType _data;
}QNode;// 队列的结构
typedef struct Queue
{QNode* _front;//队头QNode* _rear;//队尾int size;
}Queue;// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDateType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDateType QueueFront(Queue* q);
// 获取队列队尾元素
QDateType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);//Queue.c
#include Queue.hvoid QueueInit(Queue* q)
{assert(q);q-_front NULL;q-_rear NULL;q-size 0;
}void QueuePush(Queue* q, QDateType data)
{assert(q);QNode* tmp (QNode*)malloc(sizeof(QNode));if (tmp NULL){perror(tmp malloc);exit(-1);}tmp-_data data;tmp-_next NULL;if (q-_rear NULL){q-_front q-_rear tmp;}else{q-_rear-_next tmp;q-_rear tmp;}q-size;
}void QueuePop(Queue* q)
{assert(q);assert(QueueEmpty(q));if (q-_front-_next NULL){free(q-_front);q-_front q-_rear NULL;}else{QNode* next q-_front-_next;free(q-_front);q-_front next;}q-size--;
}QDateType QueueFront(Queue* q)
{assert(q);assert(QueueEmpty(q));return q-_front-_data;
}QDateType QueueBack(Queue* q)
{assert(q);assert(QueueEmpty(q));return q-_rear-_data;
}int QueueSize(Queue* q)
{assert(q);return q-size;
}int QueueEmpty(Queue* q)
{assert(q);return q-size;
}void QueueDestroy(Queue* q)
{assert(q);QNode* cur q-_front;while (cur){Queue* next cur-_next;free(cur);cur next;}q-_front q-_rear NULL;q-size 0;
}
//test.c
#include Queue.hvoid test02()
{Queue q1;QueueInit(q1);QueuePush(q1, 1);QueuePush(q1, 2);QueuePush(q1, 3);QueuePush(q1, 4);QueuePush(q1, 5);QueuePop(q1);while (QueueEmpty(q1)){printf(%d , QueueFront(q1));QueuePop(q1);}printf(\n);QueueDestroy(q1);
}int main()
{test02();return 0;
} 拓展循环队列 如上图所示循环队列的节点数一般会比要求的节点数多一个以便区分空的循环队列和满的循环队列。空的循环队列front和rear指向同一个节点满的循环队列可以理解为rear front 1。
三、初学的队列以及栈和队列结合的练习题
题目一设计循环队列
MyCircularQueue(k): 构造器设置队列长度为 k 。Front: 从队首获取元素。如果队列为空返回 -1 。Rear: 获取队尾元素。如果队列为空返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
typedef struct
{int* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a (int*)malloc(sizeof(int)*(k1));obj-front obj-rear 0;obj-k k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{//front和rear相等即为空return obj-front obj-rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj)
{//数学方法判满return (obj-rear 1) % (obj-k 1) obj-front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if(myCircularQueueIsFull(obj))return false;obj-a[obj-rear] value;obj-rear;//不然rear可能越界obj-rear % (obj-k1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return false;obj-front;obj-front % (obj-k1);return true;
}int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-a[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj))return -1;else//数学方法return obj-a[(obj-rear obj-k) % (obj-k 1)];
}void myCircularQueueFree(MyCircularQueue* obj)
{free(obj-a);free(obj);
}
题目二用队列实现栈
思路用两个队列保持一个队列为空一个不为空当要出栈的时候就将不为空的队列中除了队尾的元素全都入到为空的队列中然后将唯一的那个元素出栈。
typedef int QDateType;typedef struct QListNode
{struct QListNode* _next;QDateType _data;
}QNode;// 队列的结构
typedef struct Queue
{QNode* _front;QNode* _rear;int size;
}Queue;void QueueInit(Queue* q)
{assert(q);q-_front NULL;q-_rear NULL;q-size 0;
}void QueuePush(Queue* q, QDateType data)
{assert(q);QNode* tmp (QNode*)malloc(sizeof(QNode));if (tmp NULL){perror(tmp malloc);exit(-1);}tmp-_data data;tmp-_next NULL;if (q-_rear NULL){q-_front q-_rear tmp;}else{q-_rear-_next tmp;q-_rear tmp;}q-size;
}void QueuePop(Queue* q)
{assert(q);assert(QueueEmpty(q));if (q-_front-_next NULL){free(q-_front);q-_front q-_rear NULL;}else{QNode* next q-_front-_next;free(q-_front);q-_front next;}q-size--;
}QDateType QueueFront(Queue* q)
{assert(q);assert(QueueEmpty(q));return q-_front-_data;
}QDateType QueueBack(Queue* q)
{assert(q);assert(QueueEmpty(q));return q-_rear-_data;
}int QueueSize(Queue* q)
{assert(q);return q-size;
}int QueueEmpty(Queue* q)
{assert(q);return q-size;
}void QueueDestroy(Queue* q)
{assert(q);QNode* cur q-_front;while (cur){Queue* next cur-_next;free(cur);cur next;}q-_front q-_rear NULL;q-size 0;
}typedef struct
{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate()
{MyStack* tmp (MyStack*)malloc(sizeof(MyStack));QueueInit(tmp-q1);QueueInit(tmp-q2);return tmp;
}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* noempty obj-q2;if(QueueEmpty(obj-q1)){empty obj-q2;noempty obj-q1;}while(QueueSize(noempty) 1){QueuePush(empty, QueueFront(noempty));QueuePop(noempty);}int top QueueFront(noempty);QueuePop(noempty);return top;
}int myStackTop(MyStack* obj)
{if(QueueEmpty(obj-q1))return QueueBack(obj-q1);elsereturn QueueBack(obj-q2);
}bool myStackEmpty(MyStack* obj)
{int ret1, ret2;if(QueueEmpty(obj-q1) 0)ret1 0;elseret1 1;if(QueueEmpty(obj-q2) 0)ret2 0;elseret2 1;if(ret1 0 ret2 0)return true;elsereturn false;
}void myStackFree(MyStack* obj)
{QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}
题目三用栈实现队列
思路使用两个栈一个push栈一个pop栈先往push栈中堆入元素出队时先将push栈中的元素先pop到pop栈中再从pop栈中pop元素其间再有元素堆入入到push栈中。
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 栈顶int _capacity; // 容量
}Stack;void StackInit(Stack* ps)
{assert(ps);ps-_a NULL;ps-_top 0;ps-_capacity 0;
}void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps-_capacity ps-_top){int newCapacity ps-_capacity 0 ? 4 : ps-_capacity * 2;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] data;ps-_top;
}void StackPop(Stack* ps)
{assert(ps);assert(ps-_top 0);ps-_top--;
}STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-_top 0);return ps-_a[ps-_top - 1];
}int StackSize(Stack* ps)
{assert(ps);return ps-_top;
}int StackEmpty(Stack* ps)
{return ps-_top;
}void StackDestroy(Stack* ps)
{assert(ps);free(ps-_a);ps-_a NULL;ps-_capacity 0;ps-_top 0;
}typedef struct
{Stack pushst;Stack 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 myQueuePeek(MyQueue* obj)
{//pop栈为空就往其中堆入元素if(StackEmpty(obj-popst) 0){while(StackEmpty(obj-pushst) 0){StackPush(obj-popst, StackTop(obj-pushst));StackPop(obj-pushst);}}return StackTop(obj-popst);
}int myQueuePop(MyQueue* obj)
{int front myQueuePeek(obj);StackPop(obj-popst);return front;
}bool myQueueEmpty(MyQueue* obj)
{int ret1, ret2;if(StackEmpty(obj-pushst) 0)ret1 0;elseret1 1;if(StackEmpty(obj-popst) 0)ret2 0;elseret2 1;if(ret1 0 ret2 0)return true;elsereturn false;
}void myQueueFree(MyQueue* obj)
{StackDestroy(obj-pushst);StackDestroy(obj-popst);free(obj);
}
