相册管理网站模板,小波app推广网,朋友圈网站怎么做的,网页制作基础教程26页简答题是什么前言在我们学习了栈和队列之后#xff0c;今天来通过几道练习题来巩固一下我们的知识。题目一 用栈实现队列题目链接#xff1a;232. 用栈实现队列 - 力扣#xff08;Leetcode#xff09;这道题难度不是很大#xff0c;重要的是我们对结构认识的考察#xff0c;由于这篇文…前言在我们学习了栈和队列之后今天来通过几道练习题来巩固一下我们的知识。题目一 用栈实现队列题目链接232. 用栈实现队列 - 力扣Leetcode这道题难度不是很大重要的是我们对结构认识的考察由于这篇文章我们是通过C语言解决的所以我们必须先去构造一个栈并且可以进行栈的各种操作最终实现队列的实现。typedef int datetype;typedef struct Stack
{datetype* a;int capacity;int top;
}stack;
//初始化
void stackInit(stack* p);
//销毁
void stackDestroy(stack* p);
//入栈
void stackPush(stack* p, datetype x);
//出栈
void stackPop(stack* p);
//取栈顶数据
datetype stackTop(stack* p);
//数据个数
int stackSize(stack* p);
//判断是否为空
bool stackEmpty(stack* p);
bool isValid(char* s);
void stackInit(stack* p)
{assert(p);p-a NULL;p-capacity 0;p-top 0;
}
void stackPush(stack* p,datetype x)
{assert(p);if (p-capacity p-top){int newCapacity p-capacity 0 ? 4 : 2 * p-capacity;datetype* tmp (datetype*)realloc(p-a, newCapacity * sizeof(datetype));if (tmp NULL){perror(realloc);exit(-1);}p-a tmp;p-capacitynewCapacity;}p-a[p-top] x;p-top;
}void stackPop(stack* p)
{assert(p);assert(!stackEmpty(p));p-top--;
}void stackDestroy(stack* p)
{assert(p);if (p-capacity 0)return;free(p-a);p-a NULL;p-capacity 0;p-top 0;
}datetype stackTop(stack* p)
{assert(p);assert(!stackEmpty(p));return p-a[p-top-1];
}bool stackEmpty(stack* p)
{assert(p);return p-top0;
}
int stackSize(stack* p)
{assert(p);return p-top;
}
//定义进行出数据和入数据的栈
typedef struct {stack pushST;stack popST;
} MyQueue;//创建队列使用两个栈来实现
MyQueue* myQueueCreate() {MyQueue* tmp(MyQueue*)malloc(sizeof(MyQueue));stackInit(tmp-pushST);stackInit(tmp-popST);return tmp;
}
//直接将数据入pushST
void myQueuePush(MyQueue* obj, int x) {stackPush(obj-pushST,x);
}
//如过popST内不为空直接输出数据如果为空,将pushST数据都入到popST内
int myQueuePop(MyQueue* obj) {if(stackEmpty(obj-popST)){while(!stackEmpty(obj-pushST)){stackPush(obj-popST,stackTop(obj-pushST));stackPop(obj-pushST);}}int frontstackTop(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) {stackDestroy(obj-pushST);stackDestroy(obj-popST);free(obj);objNULL;
}这道题我们使用两个栈一个栈负责出数据一个栈负责入数据当入数据时直接push即可当出数据时我们使用两个栈配合使用栈先入先出的特点将pushST的内容入到popST时数据就已经变成了逆序所以在popST栈内直接出就可以实现队列的先入后出的功能。题目二 用队列实现栈题目链接225. 用队列实现栈 - 力扣Leetcode这道题与上道题类似都是对结构的考察使用队列先入先出的特点通过两个队列之前出数据入数据后可以实现栈的功能当一个队列出队进入另外一个队列只剩一个数据时直接将这个数据出队列两个队列互相配合最终将所有数出队实现栈的功能。typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;// size_t _size;
}Queue;//void QueueInit(QueueNode** pphead, QueueNode** pptail);
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq-head NULL;pq-tail NULL;
}void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* cur pq-head;while (cur ! NULL){QueueNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));newnode-data x;newnode-next NULL;if (pq-head NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}
}void QueuePop(Queue* pq)
{assert(pq);//if (pq-head NULL)// return;assert(!QueueEmpty(pq));QueueNode* next pq-head-next;free(pq-head);pq-head next;if (pq-head NULL){pq-tail NULL;}
}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;
}int QueueSize(Queue* pq)
{assert(pq);int n 0;QueueNode* cur pq-head;while (cur){n;cur cur-next;}return n;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* ret (MyStack*)malloc(sizeof(MyStack));QueueInit(ret-q1);QueueInit(ret-q2);return ret;
}//哪个队列不为空就在哪个队列入数据
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)){empty obj-q2;nonempty obj-q1;}while(QueueSize(nonempty)1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int retQueueFront(nonempty);QueuePop(nonempty);return ret;
}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) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}题目三 设计循环队列题目链接622. 设计循环队列 - 力扣Leetcode我们之前实现队列是使用链表来实现的当然也可以使用顺序表来实现考虑到这道题循环队列的特殊结构我们使用顺序表和链表两种方式来解决这个问题。方法一使用链表解决首先定义每个结点的结构再定义一个结构来存headtail数据个数size最大容量capacity,当数据个数等于最大容量时说明队列已满当数据个数size为0时说明队列为空。typedef struct qNode
{int data;struct qNode* next;
}qNode;typedef struct {qNode* head;qNode* tail;int size;int capacity;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq(MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq-headcq-tailNULL;cq-capacityk;cq-size0;return cq;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}qNode* newNode(qNode*)malloc(sizeof(qNode));newNode-datavalue;newNode-nextNULL;if(obj-size0){obj-headobj-tailnewNode;}else{obj-tail-nextnewNode;obj-tailnewNode;}obj-size;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}qNode* nextobj-head-next;free(obj-head);obj-headnext;obj-size--;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-head-data;
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-tail-data;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return !obj-size;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj-sizeobj-capacity;
}
void myCircularQueueFree(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){free(obj);return;}qNode* curobj-head;while(cur!obj-tail){qNode* next cur-next;free(cur);cur next;}free(obj);objNULL;
}方法二使用顺序表解决使用顺序表当headtail时说明队列为空当headtail1时说明队列为满。typedef struct {int* a;int head;int tail;int capacity;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq(MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq-a (int*)malloc(sizeof(int)*(k1));cq-headcq-tail0;cq-capacityk;return cq;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-headobj-tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-tail1)%(obj-capacity1)obj-head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj-a[obj-tail]value;obj-tail obj-tail % (obj-capacity1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj-head;obj-headobj-head%(obj-capacity1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-a[obj-head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-a[obj-tail];
}
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}
总结我们今天讲解了栈与队列的笔试题希望可以得到大家的支持。
