中山网站上排名,高端制作网站找哪个公司,网站登陆页面怎么做,国外网站建立栈和队列 一、栈的概念二、栈的实现三、栈的应用四、队列的概念五、队列的实现 一、栈的概念
栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底。栈中的数据元素遵守… 栈和队列 一、栈的概念二、栈的实现三、栈的应用四、队列的概念五、队列的实现 一、栈的概念
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。
二、栈的实现
1.头文件
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#includestdbool.h
#includestdio.h
#includeassert.h
#includestdlib.htypedef int STDataType;struct Stack
{STDataType* a;int top;//栈顶top指向最后一个数据的下一个位置int capacity;//容量方便增容
};typedef struct Stack Stack;//初始化
void StackInit(Stack* pst);//销毁
void StackDestroy(Stack* pst);//栈顶插入元素
void StackPush(Stack* pst, STDataType x);//栈顶删除元素
void StackPop(Stack* pst);//取栈顶元素
STDataType StackTop(Stack* pst);//判断栈空
bool StackEmpty(Stack* pst);//求栈元素个数
int StackSize(Stack* pst);2.源文件
#include 039-Stack.h//初始化
void StackInit(Stack* pst)
{assert(pst);pst-a (STDataType*)malloc(sizeof(STDataType) * 4);pst-top 0;pst-capacity 4;
}//销毁
void StackDestroy(Stack* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-capacity pst-top 0;
}//插入元素
void StackPush(Stack* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * pst-capacity * 2);if (tmp NULL){printf(realloc fail\n);exit(-1);}pst-a tmp;pst-capacity * 2;}pst-a[pst-top] x;pst-top;
}//删除元素
void StackPop(Stack* pst)
{assert(pst);assert(!StackEmpty(pst));pst-top--;
}//返回栈顶元素
STDataType StackTop(Stack* pst)
{assert(pst);assert(!StackEmpty(pst));return pst-a[pst-top - 1];
}//判断栈是否已满空返回1非空返回0
bool StackEmpty(Stack* pst)
{assert(pst);return pst-top 0;
}//求栈中元素个数
int StackSize(Stack* pst)
{assert(pst);return pst-top;
}3.测试文件
#define _CRT_SECURE_NO_WARNINGS 1
#include 039-Stack.hvoid TestStack()
{Stack st;StackInit(st);StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);while (!StackEmpty(st)){printf(%d , StackTop(st));StackPop(st);}StackDestroy(st);}
int main()
{TestStack();return 0;
}三、栈的应用
1.有效的括号链接
分析
1将栈的实现可以直接copy进去返回栈顶元素需要做小小的改动如果栈为空不能直接assert断言终止而要返回’\0’后面只需要实现括号的匹配即可。
2如何实现括号匹配如果是左括号那么入栈如果是右括号就判断栈顶元素该右括号是否能够匹配如果可以就从栈里弹出一个左括号如果不匹配就直接返回false。
char pairs(char a) {if (a }) return {;if (a ]) return [;if (a )) return (;return 0;
}bool isValid(char* s) {int n strlen(s);if (n % 2 1) {return false;}int stk[n 1], top 0;for (int i 0; i n; i) {char ch pairs(s[i]);if (ch) {if (top 0 || stk[top - 1] ! ch) {return false;}top--;} else {stk[top] s[i];}}return top 0;
}四、队列的概念
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头
五、队列的实现
1.头文件
#pragma once
#includestdio.h
#includestdbool.h
#includeassert.h
#includestdlib.htypedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;//初始化
void QueueInit(Queue* pq);//销毁
void QueueDestroy(Queue* pq);//插入数据
void QueuePush(Queue* pq, QDataType x);//删除数据
void QueuePop(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);//取队尾数据
QDataType QueueRear(Queue* pq);//判断队是否已满
bool QueueEmpty(Queue* pq);//求队列元素个数
int QueueSize(Queue* pq);2.源文件
#define _CRT_SECURE_NO_WARNINGS 1
#include 040-Queue.h//初始化
void QueueInit(Queue* pq)
{pq-head pq-tail NULL;
}//销毁
void QueueDestroy(Queue* pq)
{QueueNode* cur pq-head;while (cur){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));if (newNode NULL){printf(malloc fail\n);exit(-1);}newNode-data x;newNode-next NULL;//插入一个数据尾指针1当尾指针为空时队列为空if (pq-tail NULL){pq-head pq-tail newNode;}else{pq-tail-next newNode;pq-tail newNode;}
}//删除数据
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QueueNode* next pq-head-next;free(pq-head);pq-head next;}
}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}//取队尾数据
QDataType QueueRear(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}//判断队是否已满
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL;
}//求队列元素个数
int QueueSize(Queue* pq)
{int size 0;QueueNode* cur pq-head;while (cur){size;cur cur-next;}return size;}3.测试文件
#define _CRT_SECURE_NO_WARNINGS 1
#include040-Queue.h
void TestQueue()
{Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);printf(%d , QueueFront(q));QueuePop(q);printf(%d , QueueFront(q));QueuePop(q);QueuePush(q, 3);QueuePush(q, 4);while (!QueueEmpty(q)){printf(%d , QueueFront(q));QueuePop(q);}printf(\n);QueueDestroy(q);
}int main()
{TestQueue();
}好了今天的分享就到这里了 如果对你有帮助记得点赞关注哦 我的主页还有其他文章欢迎学习指点。关注我让我们一起学习一起成长吧
