可以免费商用国外印花图案设计网站,陕西省建设工程安全协会网站,消费全返的 微网站开发,万全孔家庄做网站文章目录前言一、栈1.1 栈的概念结构1.2栈的实现二、队列2.1队列的概念及结构2.2队列的实现三、栈和队列面试题总结前言
一、栈
1.1 栈的概念结构
栈也是一种线性表#xff0c;数据在逻辑上挨着存储。只允许在固定的一端进行插入和删除元素。进行插入和删除操作的一端叫栈顶…
文章目录前言一、栈1.1 栈的概念结构1.2栈的实现二、队列2.1队列的概念及结构2.2队列的实现三、栈和队列面试题总结前言
一、栈
1.1 栈的概念结构
栈也是一种线性表数据在逻辑上挨着存储。只允许在固定的一端进行插入和删除元素。进行插入和删除操作的一端叫栈顶另一端叫栈底。符合LIFO 先进后出。
压栈插入操作。
出栈删除操作。1.2栈的实现
栈的实现用数组实现更好因为完美符合数组的尾插尾删。 数组的缓存利用率高一点。 小练习 支持动态增长的栈: typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 栈顶int _capacity; // 容量
}Stack;初始化栈: void StackInit(ST* ps)
{assert(ps);ps-a NULL;ps-top ps-capacity 0;
}入栈:进栈栈的插入操作若栈未满则将x加入使之成为新栈顶。 void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, newCapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}出栈:出栈栈的删除操作若栈非空则弹出栈顶元素并用x返回。 void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps-top;
}获取栈顶元素: STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-a[ps-top - 1];
} 获取栈中有效元素个数: int StackSize(ST* ps)
{assert(ps);return ps-top;
}销毁栈:栈销毁并释放占用的存储空间 void StackDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;
}检测栈是否为空如果为空返回非零结果如果不为空返回0: bool StackEmpty(ST* ps)
{assert(ps);return ps-top 0;
}Stack.h#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);Stack.c#include Stack.hvoid StackInit(ST* ps)
{assert(ps);ps-a NULL;ps-top ps-capacity 0;
}void StackDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;
}void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, newCapacity * sizeof(STDataType));if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps-top;
}STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-a[ps-top - 1];
}bool StackEmpty(ST* ps)
{assert(ps);return ps-top 0;
}int StackSize(ST* ps)
{assert(ps);return ps-top;
}二、队列
2.1队列的概念及结构
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾。 出队列进行删除操作的一端称为队头。
2.2队列的实现
队列用链表的结构实现更优 链式结构表示队列 typedef struct QListNode
{ struct QListNode* _pNext; QDataType _data;
}QNode;队列的结构 typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;初始化队列 void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}队尾入队列 void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}else{newnode-data 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(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* del pq-head;pq-head pq-head-next;free(del);del NULL;}pq-size--;
} 获取队列头部元素 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);return pq-size;
}检测队列是否为空如果为空返回非零结果如果非空返回0 bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL pq-tail NULL;
}销毁队列 void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* del cur;cur cur-next;free(del);}pq-head pq-tail NULL;
}Queue.h#pragma once
#include stdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);Queue.c#includeQueue.hvoid QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* del cur;cur cur-next;free(del);}pq-head pq-tail NULL;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}else{newnode-data 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(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* del pq-head;pq-head pq-head-next;free(del);del NULL;}pq-size--;
}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;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL pq-tail NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}三、栈和队列面试题
题目链接 1.https://leetcode.cn/problems/valid-parentheses/ 题目链接 2.https://leetcode.cn/problems/implement-stack-using-queues/ 总结
