雄安优秀网站建设方案,西安网站建设推广专家,wordpress 个人公众号,wordpress 定时重启1.栈
1.1栈的概念及结构
栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端成为栈顶#xff0c;另一端成为栈底。遵守后进先出的原则#xff08;类似于弹夹#xff09;
压栈#xff1a;栈的插入操…1.栈
1.1栈的概念及结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端成为栈顶另一端成为栈底。遵守后进先出的原则类似于弹夹
压栈栈的插入操作叫做进栈/入栈/压栈入数据在栈顶
出栈栈的删除操作叫做出栈出数据也在栈顶
那如何实现栈呢 经过比较数组栈是最优解链式的扩容会很久才会扩容一下
由于top的位置意义不同我们分为两种解决方案 1.2基本操作
1.定义一个栈
typedef int SLDataType
typedef struct Stack
{int *a;int top;int capacity;
}2,初始化一个栈
void STInit(ST*pst)
{assert(pst);pst-aNULL;pst-top0;pst-capacity0;
}3压栈
void STPush(ST* pst, SLDataType x)
{assert(pst);if (pst-top pst-capacity){ST* newcapacity pst-capacity 0 ? 4 : capacity * 2;SLDataType* tmp (SLDataType*)realloc((SLDataType)*newcapacity);if (newcapacity NULL){return -1;}else{pst-a tmp;pst-capacity newcapacity;pst-a[pst-top] x;pst-top;}}
} 4弹栈
void STPop(ST* pst)
{assert(pst);assert(pst-top0);pst-top--;
}
5 返回栈顶元素
void STTop(ST* pst)
{assert(pst);assert(pst-top0);return pst-a[pst-top-1];
}
6 判断是否为空
bool STEmpty(ST* pst)
{assert(pst);if (pst-top 0){return true;}else{return false;}
}
7 栈的大小
int STSize(ST* pst)
{assert(pst);return pst-top;
}
8销毁栈
void STDestory(ST*pst)
{assert(pst);free(pst-a);pst-aNULL;pst-toppst-capacity0;
}
让我们看几道例题吧
例题1 思路栈的顺序是后进先出有题可知最后一个是E所以E先出故选B
例题2 我们首先看选项A选项1先进1先出把2 3 4放进去把4拿出来再把3拿出来最后把2拿出来。同理我们看C选项把1 2 3放进去然后把3拿出来然后我们会发现如果想要拿1的话拿2是必经之路所以此选项错误
例题3 思路
1先建立一个栈初始化一个栈
2然后我们把所有的左括号放入栈里面如果不是左括号即是有括号
3其次我们要知道本题的关键在于数量匹配和顺序匹配。所以我们要考虑一下栈是否为空右括号的数量大于左括号的数量然后考虑顺序匹配的问题
4最后我们看栈是否为空如果为空就返回true然后把栈毁掉
bool isVaild(char* s)
{ST st;// 定义一个栈STInit(st);while (*s){if (*s [ || *s { || *s (){STPush(st, *s);s;}else{if (STEmpty(st)){return false;}//栈里面取左括号char top STTop(st);STPop(st);//顺序不匹配if (*s ] top ! [) || (8s } top ! {) || (*s ) top (){return false;}s;}}//栈为空返回真说明数量都匹配bool ret STEmpty(st);STDestory(pst);return ret;
}
好啦~栈我们就先讲到这里啦让我们看一下队列的知识点吧
2队列
2.1队列的概念和结构 我们可以考虑一个问题
入队之后出队的时候顺序是唯一一定的吗
答案是当然是
从以上我们可以了解到栈用数组的方法比较好而队列用单链表头删尾插的方式比较好
2.2基本操作
1定义一个队列
typedef int QueueType;
typedef struct QueueNode
{QueueType val;struct QueueNode* next;}QNode;
为了解决二级指针以及两个指针的问题我们可以把两个指针放入一个结构体里面然后进行一级指针的操作即可
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue; 2.初始化一个队列
void QueueInit(Queue* pq)
{assert(pq);pq-size 0;pq-phead pq-ptail NULL;
}
3.插入到队列 void QueuePushQueue* pq, QDataType x){QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL)return -1;else{newnode-val x;newnode-next NULL;}if (pq-tail NULL){return -1;pq-tail pq-phead newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;}4. 头删
void QueuePop(Queue* pq)
{assert(pq);assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;if (pq-phead NULL)pq-tail NULL;
}
5找头结点的值
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}
6队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-pheadNULL;
}
7队列大小
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
8销毁队列
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;cur next;}
pq-pheadpq-ptailNULL;
}
让我们看几道关于队列和栈的例题吧
例题1 思路 代码实现
typedef struct
{Queue q1;Queue q2;}Stack;MyStack* CreateStack()
{MyStack* pst (MyStack*)malloc(sizeof(MyStack));QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}
void mystackpush(Mystack* obj, int x)
{Queue Empty obj-q1;Queue nonEmpty obj-q2;if (!Empty(obj-q1)){Queue Empty obj-q2;Queue nonEmpty obj-q1;}//开始到数据while (QueueSize(nonempty) 1){QueuePush(Empty, QueueFront(nonempty));QueuePop(nonempty);}int top QueueFront(nonempty);QueuePop(nonempty);return top;
}int mystackTop(Mystack* obj)
{if (!Empty(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);
}
例题2 思路 代码实现 typedef struct
{int* a;int top;int capacity;
}ST;
typedef struct
{ST pushst;ST popst;
}MyQueue;
//初始化
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-top 0;pst-capacity 0;
}
//压栈
void STPush(ST* pst, SLDataType x)
{assert(pst);if (pst-top pst-capacity){ST* newcapacity (SLDataType*)malloc(sizeof(SLDataType);SLDataType* tmp pst-capacity 0 ? 4 : newcapacity * 2;if (newcapacity 0){return -1;}else{pst-a tmp;pst-capacity newcapacity;pst-a[pst-top] x;pst-top;}}
}
//返回栈顶元素
void STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-a[pst-top - 1];
}
//弹栈
void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}
//判断是否为空
bool STEmpty(ST* pst)
{assert(pst);if (pst-top 0){return true;}else{return -1;}
}
MyQueue* myQueueCreate()
{MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;
}
void myQueuePush(MyQueue* obj, int x)
{STPush(obj-pushst, x);
}
返回队列开头的元素不删除
void myQueuepeek(MyQueue* obj)
{if (!STEmpty(obj-popst)){return STTop(obj-popst);}else{while (!STEmpty(obj-pushst)){STPush(obj-popst, STTop(obj-pushst);STPop(obj-pushst);}return STTop(obj-popst);}
}
//从队列开头移除并返回元素
void myQueuePop(MyQueue* obj)
{int front myQueuePeek(obj);STPop(obj-popst);return front;
}
bool myQueueEmpty(MyQueue* obj)
{return STEmpty(obj-pushst) (obj-popst);
}
void myQueueFree(MyQueue* obj)
{STDestory(obj-popst);STDestory(obj-pushst);free(obj);
}接下来我们看一下循环队列吧
1.判断循环队列是否为空frontbackfront指向对头back指向队尾的下一个 如何判断队列是否为满
1.前提frontback当size0时为空size0则为满
2再增加一个地方
即
数组实现back1%k1front则为满其中k1指的是开辟空间的个数k指的是有效数据数 数组实现k1是为了防止溢出
链表实现即把上面式子去掉 %k1
链表实现 数组实现 单链表缺陷以及找尾的办法 如何计算循环中元素的个数 typedef struct {int* a;int front;int back;int k;
}MyCircularQueue;
//初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a (int*)malloc(sizeof(int) * (k 1));obj-front 0;obj-back 0;obj-k 0;return obj;
}
//是否为空
bool myCircularQueueEmpty(MyCircularQueue* obj)
{return obj-front obj - back;}
//是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return (obj-front) % (obj-k 1) obj-front;}
//插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if (myCircularQueueIsFull(obj)){return false;}obj-a[obj-back] value;obj-back;obj-back % (obj-k 1) obj-back;return true;
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj, int value)
{if (myCircularQueueIsFull(obj)){return false;}obj-front;obj-front % (obj-k 1) obj-front;return true;
}
//返回队头
int myCircularQueueFront(MyCircularQueue* obj)
{if (myCircularQueueIsFull(obj)){return false;}return obj-a[obj-front];
}
//返回队尾
int myCircularQueueRear(MyCircularQueue* obj)
{if (myCircularQueueIsFull(obj)){return false;}return obj-a[obj-back - 1];
}
//清空
void myCircularQueueFree(MyCircularQueue* obj)
{free(obj-a);free(obj);
}
好啦~关于栈和队列的知识点就这些啦~谢谢大家观看~
