什么网站做电器出租,wordpress 网银支付,手机微信打开文件是乱码,xampp如何搭建wordpress栈和队列1 栈栈的顺序存储栈的链式存储2 队列队列的顺序存储队列的链式存储3 栈和队列的应用用栈实现队列用队列实现栈最小栈1 栈
参考文章#xff1a; https://zhuanlan.zhihu.com/p/346164833 https://zhuanlan.zhihu.com/p/120965372#:~:text%E6%A0%88%E6%98%AF%E4%B8%80%…
栈和队列1 栈栈的顺序存储栈的链式存储2 队列队列的顺序存储队列的链式存储3 栈和队列的应用用栈实现队列用队列实现栈最小栈1 栈
参考文章 https://zhuanlan.zhihu.com/p/346164833 https://zhuanlan.zhihu.com/p/120965372#:~:text%E6%A0%88%E6%98%AF%E4%B8%80%E7%A7%8D%20%E5%90%8E%E8%BF%9B%E5%85%88%E5%87%BA%EF%BC%88LIFO%EF%BC%89,%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20%E8%BF%9B%E6%A0%88%E7%9A%84%E9%A1%BA%E5%BA%8F%E4%B8%BAa1%2Ca2%2Ca3%2Ca4%2Ca5%EF%BC%8C%E5%87%BA%E6%A0%88%E7%9A%84%E9%A1%BA%E5%BA%8F%E4%B8%BAa5%2Ca4%2Ca3%2Ca2%2Ca1
栈是一种特殊的线性表仅允许在一端进行插入和删除。被允许插入和删除的一端为栈顶top另一端称为栈底bottom栈底是固定的不允许进行插入和删除 栈的主要基本操作有
InitStack(S)初始化栈StackEmpty(S)判断一个栈是否为空Push(S,x)进栈若栈未满则将x加入到栈顶pop(S,x)出栈若栈非空则将栈顶元素出栈并用x返回
栈的顺序存储
采用顺序存储的栈称为顺序栈用数组实现。 栈的定义为
#define STACK_SIZE 100typedef int ElmType;typedef struct{int top; /* 栈顶指针 */ElmType data[STACK_SIZE]; /* 顺序栈 */
}SqStack;
栈顶指针S.top初始时设置S.top -1栈顶元素S.data[top]进栈操作先判断S.topSTACK_SIZE-1若栈不满S.top加1然后将值送到栈顶。出栈操作栈非空时先去栈顶元素值然后再将栈顶指针减1栈空条件S.top-1栈满条件S.topSTACK_SIZE-1栈长S.top1
栈的链式存储
采用链式存储的栈称为链栈链栈的优点是便于多个栈共享存储空间和提高其效率且不存在栈满上溢的情况。通常采用单链表实现并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点top指向栈顶元素 链栈的存储可定义为
typedef int ElemType;
typedef struct LinkNode{ElemType data;struct LinkNode *next;
}LinkStack;2 队列
队列是只允许在一端进程插入操作在另一端进行删除操作的线性表。被允许插入的一端叫队尾rear被允许删除的一端叫队头front。 队列的主要基本操作有
InitQueue(Q)初始化队列QueueEmpty(Q)判断队列是否为空QueueLenght(Q)判断队列中元素的个数push(Q,x)入队如果队列没有满就在队尾插入xpop(Q,x)出队如果队列非空就在队首删除一个元素并用x返回
队列的顺序存储
类型定义为
#define QUEUE_SIZE 100
typedef int ElemType;
typedef struct
{ElemType data[QUEUE_SIZE]; /* 队列 */int front; /* 队首 */int rear; /* 队尾 */
}SqQueue;由于普通队列存在溢出问题所以我们用循环队列循环队列的定义和普通队列定义一样。
说明这里浪费一个存储空间
初始化rearfront0添加一个元素如果队列没有满则插入即Q[rear] x,rear rear1%QUEUE_SIZE删除一个元素如果队列非空则删除即*xQ[front]front front1% QUEUE_SIZE判断队列是否为空rearfront判断队列是否满(rear1)%QUEUE_SIZEfront队列元素个数(rear-frontQUEUE_SIZE)%QUEUE_SIZE
队列的链式存储
队列的数组实现比较麻烦需要考虑各种边界情况所以通常使用链表形式来实现队列。
使用单向链表来实现链式队列链式队列中存储front和rear即可。
typedef int ElemType;
typedef struct node
{int date;struct node *next;
}LinkNode;
typedef struct queue{LinkNode *front;LinkNode *rear;
}LinkQueue;
3 栈和队列的应用
用栈实现队列
参考文章https://cloud.tencent.com/developer/article/1643318
LeedCode题目位置232. 用栈实现队列
队列的特性是新加入的元素在队尾最先入队的元素排在队首按队首到队尾的顺序依次出栈。用栈实现队列需要把新加入的元素保留在栈底保证栈顶是队列最先加入的元素。
所以我们用两个栈A、B来实现每次入队时先把存放数据的栈A弹出到另一个栈B然后把数据存到A最后把B中的元素依次弹出压入A栈中这样保证了新加入的元素在栈底。 队列出队是把队列队首的删除对应栈是把栈A的栈顶元素删除。
实现代码如下
#include stdlib.htypedef char bool;#define SIZE 100
#define false 0
#define true 1
/* 栈的定义 */
typedef struct{int length;int data[SIZE];
}Stack;/* 初始化栈 */
Stack *initStack()
{Stack * ret malloc(sizeof(Stack));ret-length-1;return ret;
}/* 判断栈是否为空 */
bool StackEmpty(Stack *s)
{return s-length-1;
}/* 入栈操作 */
bool stackPush(Stack *s,int x)
{if(s-lengthSIZE-1){return false;}s-length;s-data[s-length]x;return true;
}
/* 出栈操作 */
bool stackPop(Stack *s,int *x)
{if(s-length-1){return false;}*x s-data[s-length];s-length--;return true;
}/* 释放栈 */
void freeStack(Stack *s)
{free(s);
}typedef struct {Stack *inStack;Stack *outStack;
} MyQueue;/* 创造队列 */
MyQueue* myQueueCreate() {MyQueue *ret (MyQueue *)malloc(sizeof(MyQueue));ret-inStack initStack();ret-outStack initStack();return ret;
}void myQueuePush(MyQueue* obj, int x) {int y;/* 先把栈A的元素依次弹出放到栈B */while(stackPop(obj-inStack,y)){stackPush(obj-outStack,y);}/* 把入队的元素放到栈A的栈底 */stackPush(obj-inStack,x);/* 依次弹出栈B的元素放到栈A */while(stackPop(obj-outStack,y)){stackPush(obj-inStack,y);}
}int myQueuePop(MyQueue* obj) {int x;/* 删除栈A的栈顶元素 */stackPop(obj-inStack,x);return x;
}int myQueuePeek(MyQueue* obj) {return obj-inStack-data[obj-inStack-length];
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(obj-inStack);
}void myQueueFree(MyQueue* obj) {free(obj-inStack);free(obj-outStack);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);
*/用队列实现栈
参考文章https://cloud.tencent.com/developer/article/1643318 LeedCode题目位置225. 用队列实现栈 栈的特性是新加入的元素出现在栈顶删除的元素也在栈顶队列的特性是新加入的特性在队尾删除的元素在队首。 我们可以让数据先入队列然后把队列的以前的数据依次出队再入队这样保证了新压入的数据在队首对应栈的栈顶。 出栈的话对应队列的操作就是把队首的元素删除即可。 实现代码如下
#include stdlib.h#define false 0
#define true 1
#define SIZE 101typedef struct{int front; // 队首int rear; //队尾int data[SIZE];
}Queue;/* 初始化队列 */
Queue * initQueue()
{Queue * ret (Queue *)malloc(sizeof(Queue));ret-front0;ret-rear0;return ret;
}
/* 判断队列是否为空 */
bool QueueEmpty(Queue *q)
{if(q-frontq-rear){return true;}elsereturn false;
}/* 入队 */
bool queuePush(Queue *q,int x)
{/* 队满 */if(q-front (q-rear1)%SIZE){return false;}q-data[q-rear]x;q-rear (q-rear1)%SIZE;return true;
}
/* 出队 */
bool QueuePop(Queue *q,int *x)
{/* 队列是否为空 */if(q-frontq-rear)return false;*x q-data[q-front];q-front (q-front1)%SIZE;return true;
}
/* 获取队首元素 */
int getQueueTop(Queue *q)
{return q-data[q-front];
}
typedef struct {Queue *q;
} MyStack;MyStack* myStackCreate() {MyStack *ret (MyStack *)malloc(sizeof(MyStack));ret-q initQueue();return ret;
}void myStackPush(MyStack* obj, int x) {int y;/* 计算现在有多少个元素 */int length (obj-q-rear-obj-q-frontSIZE)%SIZE;/* x入队 */queuePush(obj-q,x);for(int i0;ilength;i){/* 出队 */QueuePop(obj-q,y);/* 入队 */queuePush(obj-q,y);}
}
/* 只需将队首元素删除 */
int myStackPop(MyStack* obj) {int x;QueuePop(obj-q,x);return x;
}int myStackTop(MyStack* obj) {return getQueueTop(obj-q);
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q);
}void myStackFree(MyStack* obj) {free(obj-q);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);
*/最小栈
LeedCode位置155. 最小栈 题目要求在常数时间内检索到最小元素的栈所以我们在栈里面设置一个变量min来记录最小元素的位置。
当插入元素如果插入的元素比栈内的元素都要小这个时候需要更新min当删除元素时如果此时最小的元素在栈顶也需要更新min值。
代码实现如下
#include stdlib.h#define SIZE 30000typedef struct {int length; //记录元素个数,始终指向栈顶元素int min; //记录最小元素的位置int data[SIZE];
} MinStack;int getStackMin(MinStack *s)
{int min 0;for(int i1;is-length;i){if(s-data[min]s-data[i]){min i;}}return min;
}MinStack* minStackCreate() {MinStack *ret (MinStack *)malloc(sizeof(MinStack));ret-length -1;ret-min 0;return ret;
}void minStackPush(MinStack* obj, int val) {obj-data[obj-length]val;/* 插入的元素比栈内的元素都要小这个时候需要更新min */if(valobj-data[obj-min])obj-min obj-length;
}void minStackPop(MinStack* obj) {obj-length--;/* 删除元素时如果此时最小的元素在栈顶也需要更新min值 */if(obj-min(obj-length1)){obj-min getStackMin(obj);}
}int minStackTop(MinStack* obj) {return obj-data[obj-length];
}int minStackGetMin(MinStack* obj) {return obj-data[obj-min];
}void minStackFree(MinStack* obj) {free(obj);
}/*** Your MinStack struct will be instantiated and called as such:* MinStack* obj minStackCreate();* minStackPush(obj, val);* minStackPop(obj);* int param_3 minStackTop(obj);* int param_4 minStackGetMin(obj);* minStackFree(obj);
*/
