深圳住房建设局网站,在线做ppt模板下载网站有哪些,网站设计公司有名乐云seo,seo排名关键词栈和队列 1.栈1.1栈的概念和结构1.2栈的实现 2.队列2.1队列的概念和结构2.2队列的实现 1.栈
1.1栈的概念和结构
栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底。… 栈和队列 1.栈1.1栈的概念和结构1.2栈的实现 2.队列2.1队列的概念和结构2.2队列的实现 1.栈
1.1栈的概念和结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。
1.2栈的实现
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小 Stack.h #includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int STDateType;
typedef struct Stack
{STDateType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* ps);//销毁
void STDestroy(ST* ps);//入栈
void STPush(ST* ps, STDateType x);//出栈
void STPop(ST* ps);//栈顶
STDateType SLTTop(ST* ps);//计算大小
int STSize(ST* ps);//判断是否为空
bool STEmpty(ST* ps);Stack.c #includeStack.h//初始化
void STInit(ST* ps)
{assert(ps);ps-capacity NULL;ps-a 0;ps-top 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;
}//入栈
void STPush(ST* ps, STDateType x)
{assert(ps);if (ps-top ps-capacity){int NewCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDateType* tmp (STDateType*)realloc(ps-a, sizeof(STDateType) * NewCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity NewCapacity;}ps-a[ps-top] x;ps-top;
}//出栈
void STPop(ST* ps)
{assert(ps);assert(ps-a 0);--ps-top;
}//栈顶
STDateType STTop(ST* ps)
{assert(ps);assert(ps-a 0);return ps-a[ps-top - 1];
}//计算
int STSize(ST* ps)
{assert(ps);return ps-top;
}//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top NULL;
}test.c #includeStack.hvoid TestStack()
{ST st;STInit(st);STPush(st, 1);STPush(st, 2);STPush(st, 3);STPush(st, 4);STPush(st, 5);while (!STEmpty(st)){printf(%d , STTop(st));STPop(st);}printf(\n);STDestroy(st);
}int main()
{TestStack();return 0;
}2.队列
2.1队列的概念和结构
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾出队列进行删除操作的一端称为队头
2.2队列的实现
队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 Queue.h #includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;
void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);Queue.c #includeQueue.h//初始化
void QueueInit(Que* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}//销毁
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur cur-next;}pq-head pq-tail NULL;pq-size 0;
}//入队
void QueuePush(Que* pq, QDateType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-date x;newnode-next NULL;if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}//出队
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}//队头
QDateType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-date;
}//队尾
QDateType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty);return pq-tail-date;
}//判断是否为空
bool QueueEmpty(Que* pq)
{assert(pq);return pq-head NULL;
}//计算
int QueueSize(Que* pq)
{assert(pq);return pq-size;
}test.c #includeQueue.hvoid QueueTest()
{Que pq;QueueInit(pq);QueuePush(pq, 1);QueuePush(pq, 2);QueuePush(pq, 3);QueuePush(pq, 4);while (!QueueEmpty(pq)){printf(%d , QueueFront(pq));QueuePop(pq);}printf(\n);QueueDestroy(pq);
}int main()
{QueueTest();return 0;
}3.栈和队列面试题
3.1括号匹配问题 OJ
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
//有效括号
typedef char STDateType;
typedef struct Stack
{STDateType* a;int top;int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDateType x);
//出栈
void STPop(ST* ps);
//栈顶
STDateType SLTTop(ST* ps);
//计算大小
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);//初始化
void STInit(ST* ps)
{assert(ps);ps-capacity NULL;ps-a 0;ps-top 0;
}
//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;
}
//入栈
void STPush(ST* ps, STDateType x)
{assert(ps);if (ps-top ps-capacity){int NewCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDateType* tmp (STDateType*)realloc(ps-a, sizeof(STDateType) * NewCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity NewCapacity;}ps-a[ps-top] x;ps-top;
}
//出栈
void STPop(ST* ps)
{assert(ps);assert(ps-a 0);--ps-top;
}
//栈顶
STDateType STTop(ST* ps)
{assert(ps);assert(ps-a 0);return ps-a[ps-top - 1];
}
//计算
int STSize(ST* ps)
{assert(ps);return ps-top;
}
//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top NULL;
}bool isValid(char* s)
{ST st;STInit(st);char topVal;while (*s){//数量不匹配if (*s ( || *s [ || *s {){STPush(st, *s);}else{if (STEmpty(st)){STDestroy(st);return false;}topVal STTop(st);STPop(st);if ((*s ) topVal ! () || (*s ] topVal ! [) || (*s } topVal ! {)){STDestroy(st);return false;}}s;}//栈不为空false,说明数量不匹配bool ret STEmpty(st);STDestroy(st);return ret;
}int main()
{isValid([(({})}]);#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int STDateType;
typedef struct Stack
{STDateType* a;int top;int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDateType x);
//出栈
void STPop(ST* ps);
//栈顶
STDateType SLTTop(ST* ps);
//计算大小
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);
//初始化
void STInit(ST* ps)
{assert(ps);ps-capacity NULL;ps-a 0;ps-top 0;
}
//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;
}
//入栈
void STPush(ST* ps, STDateType x)
{assert(ps);if (ps-top ps-capacity){int NewCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDateType* tmp (STDateType*)realloc(ps-a, sizeof(STDateType) * NewCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity NewCapacity;}ps-a[ps-top] x;ps-top;
}
//出栈
void STPop(ST* ps)
{assert(ps);assert(ps-a 0);--ps-top;
}
//栈顶
STDateType STTop(ST* ps)
{assert(ps);assert(ps-a 0);return ps-a[ps-top - 1];
}
//计算
int STSize(ST* ps)
{assert(ps);return ps-top;
}
//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top NULL;
}
typedef struct
{ST pushst;ST popst;
} MyQueue;
MyQueue* myQueueCreate()
{MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-popst);STInit(obj-pushst);return obj;
}void myQueuePush(MyQueue* obj, int x)
{STPush(obj-pushst, x);
}int myQueuePeek(MyQueue* obj)
{if (STEmpty(obj-popst)){while (!STEmpty(obj-pushst)){STPush(obj-popst, STTop(obj-pushst));STPop(obj-pushst);}}return STTop(obj-popst);
}int myQueuePop(MyQueue* obj)
{int front myQueuePeek(obj);STPop(obj-popst);return front;
}bool myQueueEmpty(MyQueue* obj)
{return STEmpty(obj-popst) STEmpty(obj-pushst);
}void myQueueFree(MyQueue* obj)
{STDestroy(obj-popst);STDestroy(obj-pushst);free(obj);
}}3.2用队列实现栈 OJ
3.3用栈实现队列 OJ
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int STDateType;
typedef struct Stack
{STDateType* a;int top;int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDateType x);
//出栈
void STPop(ST* ps);
//栈顶
STDateType SLTTop(ST* ps);
//计算大小
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);
//初始化
void STInit(ST* ps)
{assert(ps);ps-capacity NULL;ps-a 0;ps-top 0;
}
//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;
}
//入栈
void STPush(ST* ps, STDateType x)
{assert(ps);if (ps-top ps-capacity){int NewCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDateType* tmp (STDateType*)realloc(ps-a, sizeof(STDateType) * NewCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity NewCapacity;}ps-a[ps-top] x;ps-top;
}
//出栈
void STPop(ST* ps)
{assert(ps);assert(ps-a 0);--ps-top;
}
//栈顶
STDateType STTop(ST* ps)
{assert(ps);assert(ps-a 0);return ps-a[ps-top - 1];
}
//计算
int STSize(ST* ps)
{assert(ps);return ps-top;
}
//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top NULL;
}
typedef struct
{ST pushst;ST popst;
} MyQueue;
MyQueue* myQueueCreate()
{MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-popst);STInit(obj-pushst);return obj;
}void myQueuePush(MyQueue* obj, int x)
{STPush(obj-pushst, x);
}int myQueuePeek(MyQueue* obj)
{if (STEmpty(obj-popst)){while (!STEmpty(obj-pushst)){STPush(obj-popst, STTop(obj-pushst));STPop(obj-pushst);}}return STTop(obj-popst);
}int myQueuePop(MyQueue* obj)
{int front myQueuePeek(obj);STPop(obj-popst);return front;
}bool myQueueEmpty(MyQueue* obj)
{return STEmpty(obj-popst) STEmpty(obj-pushst);
}void myQueueFree(MyQueue* obj)
{STDestroy(obj-popst);STDestroy(obj-pushst);free(obj);
}
3.4设计循环队列 OJ
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
//计循环队列
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) * (k 1));obj-front obj-rear 0;obj-k k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{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;obj-rear % (obj-k 1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj))return false;obj-front;obj-front % (obj-k 1);return true;
}int myCircularQueueFront(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj))return -1;return obj-a[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj)
{if (myCircularQueueIsEmpty(obj))return -1;return obj-a[(obj-rear obj-k) % (obj-k 1)];
}void myCircularQueueFree(MyCircularQueue* obj)
{free(obj-a);free(obj);
}
不知不觉【数据结构初阶】栈和队列以告一段落。通读全文的你肯定收获满满让我们继续为数据结构学习共同奋进!!!
