数据结构——栈和队列
如意.759 2024-08-22 16:05:03 阅读 96
目录
一、栈
1.1栈的概念及结构
1.2栈的结构选择
1.3栈的实现
二、队列
2.1队列的概念及结构
2.2队列的应用
2.3队列的实现
三、OJ题——栈与队列
3.1括号匹配问题
3.2用队列实现栈
3.3用栈实现队列
3.4设计循环队列
一、栈
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2栈的结构选择
<1>数组
可以用下标直接访问栈顶元素
<2>单链表
右边为栈顶的单链表并不好实现，因为无法直接访问，遍历麻烦
但是我们可以让头结点为栈顶减少遍历访问
1.3栈的实现
栈的定义：
定义一个栈结构体，里面放着指向栈数组的指针，栈顶元素的下标 top ，空间大小 capacity
<code>typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
栈的初始化：
先断言一下，然后将指针置空，并将空间大小和top初始化为0
void STInit(ST* pst)
{
assert(pst);
pst->;a = NULL;
pst->top = pst->capacity = 0;
}
栈的初始化有两种方法
<1>top赋值为-1
<2>top赋值为0
栈的销毁
free释放数组空间，再将指针置空和空间大小与top置为0
<code>void STDestroy(ST* pst)
{
assert(pst);
free(pst->;a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
入栈
先对栈空间判满，如果满了我们需要扩容到原来的2倍
如果一开始没开空间可以先给出4个字节，最后更新指针a top capacity
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->capacity == pst->top)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return 1;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[(pst->top)++] = x;
}
出栈
注意 断言 top＞0
void STPop(ST* pst)
{
assert(pst && pst->top > 0);
pst->top--;
}
获取栈顶数据
STDataType STTop(ST* pst)
{
assert(pst && pst->top > 0);
return pst->a[pst->top - 1];
}
判空
bool STEmpty(ST* pst)
{
assert(pst);
return 0 == pst->top;
}
获取数据个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
栈的遍历
int main()
{
ST s1;
STInit(&s1);
STPush(&s1, 1);
STPush(&s1, 2);
STPush(&s1, 3);
STPush(&s1, 4);
while (!STEmpty(&s1))
{
printf("%d ", STTop(&s1));
STPop(&s1);
}
STDestroy(&s1);
return 0;
}
二、队列
2.1队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2.2队列的应用
<1>抽号机
日常生活中都会遇到取票排队，取票后就把票数尾插到抽号机，要取号时就在队头出数据
<2>好友推荐——广度优先遍历（DFS）
2.3队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据需要挪动数据，效率会比较低。
队列的结构体
定义一个结点的结构体，然后为了队尾进数据，队头出数据，再用一个头指针和一个尾指针和size维护整个队列
<code>typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
//头指针
QNode* phead;
//尾指针
QNode* ptail;
int size;
}Queue;
队列的初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->;phead = pq->ptail = NULL;
pq->size = 0;
}
队列的销毁
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;//用来遍历销毁结点
while (cur)
{
QNode* next = cur->next;//存下一个结点的位置
free(cur);
cur = next;
}
pq->ptail = pq->phead = NULL;
pq->size = 0;
}
队尾插入
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return ;
}
newnode->next = NULL;
newnode->val = x;
//空链表情况
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
获取队头队尾元素
QDataType QueueFront(Queue* pq)
{
assert(pq && pq->size > 0);
return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
assert(pq && pq->size > 0);
return pq->ptail->val;
}
队头的删除
void QueuePop(Queue* pq)
{
assert(pq && pq->size > 0);
//一个结点情况
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
队列的判空
<code>bool QueueEmpty(Queue* pq)
{
assert(pq);
return 0 == pq->;size;
}
队列的数据个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
队列的遍历
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ",QueueFront(&q));
QueuePop(&q);
}
QueueDestory(&q);
return 0;
}
三、OJ题——栈与队列
3.1括号匹配问题
. - 力扣（LeetCode）
思路分析：
遍历字符串s 左括号入栈，右括号与出栈的左括号匹配，如果不匹配直接false
Tip：仅有右括号或者左括号，数量不匹配问题也应该注意结合判空返回真假
演示代码：
<code>typedef char STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void STInit(ST* pst)
{
assert(pst);
pst->;a = NULL;
pst->top = pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->capacity == pst->top)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return ;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[(pst->top)++] = x;
}
void STPop(ST* pst)
{
assert(pst && pst->top > 0);
pst->top--;
}
STDataType STTop(ST* pst)
{
assert(pst && pst->top > 0);
return pst->a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{
assert(pst);
return 0 == pst->top;
}
//栈的元素个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
bool isValid(char* s) {
ST s1;
STInit(&s1);
while(*s)
{
if(*s=='('||*s=='{'||*s=='[')
STPush(&s1,*s);//左括号入栈
else
{
if(STEmpty(&s1))
return false;
char tmp=STTop(&s1);
STPop(&s1);
if(tmp=='('&&*s!=')'
||tmp=='['&&*s!=']'
||tmp=='{'&&*s!='}')
return false;
}
s++;
}
bool ret=STEmpty(&s1);
STDestroy(&s1);
return ret;
}
3.2用队列实现栈
. - 力扣（LeetCode）
思路分析：
因为队列是先进先出，而需要实现的栈是后进先出的。所以我们需要借助另外一个队列导数据才能实现后进先出的栈
如何出栈得到4呢？将非空队列q1前size-1个数据挪到空队列q2，再pop q1最后一个元素即栈顶元素
最后入数据的话就需要入到非空队列 否则需要一直导数据过于繁琐
封装结构：
初始化：
<code>MyStack* myStackCreate() {
MyStack*pst=(MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->;q1);
QueueInit(&pst->q2);
return pst;
}
为了防止局部变量出作用域就销毁，所以这里要malloc动态内存
入数据：
需要入到非空队列中
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&(obj->q1)))
{
QueuePush(& (obj->q1),x);
}
else
{
QueuePush(& (obj->q2),x);
}
}
出数据:
先判断哪个队列是空的然后while循环导size-1数据，最后pop
int myStackPop(MyStack* obj) {
Queue *empty=&(obj->q1);
Queue* nempty=&(obj->q2);
if(!QueueEmpty(&(obj->q1)))
{
empty=&(obj->q2);
nempty=&(obj->q1);
}
while(QueueSize(nempty)>1)
{
QueuePush(empty,QueueFront(nempty));
QueuePop(nempty);
}
QDataType ret=QueueFront(nempty);
QueuePop(nempty);
return ret;
}
获取栈顶元素：
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&(obj->q1)))
return QueueBack(&(obj->q1));
else
return QueueBack(&(obj->q2));
}
判空：
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&(obj->q1))&&QueueEmpty(&(obj->q2));
}
销毁：
注意封装的完整性 obj里面的两个队列也需要释放内存
void myStackFree(MyStack* obj) {
QueueDestory(&(obj->q1));
QueueDestory(&(obj->q2));
free(obj);
}
3.3用栈实现队列
. - 力扣（LeetCode）
思路分析：
出数据应该是 1 2 3 4，发现只要将数据导入另一个栈中 pop顺序刚好是 1 2 3 4
这样我们就可以利用一个 push栈 和一个 pop栈实现队列的先进先出，当pop为空时就需要导入数据
演示代码：
<code>typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
void STInit(ST* pst)
{
assert(pst);
pst->;a = NULL;
pst->top = pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->capacity == pst->top)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return ;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[(pst->top)++] = x;
}
void STPop(ST* pst)
{
assert(pst && pst->top > 0);
pst->top--;
}
STDataType STTop(ST* pst)
{
assert(pst && pst->top > 0);
return pst->a[pst->top - 1];
}
bool STEmpty(ST* pst)
{
assert(pst);
if(pst->top == 0)
return 1;
else
return 0;
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
typedef struct {
ST pushst;
ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue*queue=(MyQueue *)malloc(sizeof(MyQueue));
STInit(&queue->pushst);
STInit(&queue->popst);
return queue;
}
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->pushst,x);
}
int myQueuePeek(MyQueue* obj);
int myQueuePop(MyQueue* obj) {
int ret=myQueuePeek(obj);
STPop(&obj->popst);
return ret;
}
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);
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->popst)&&STEmpty(&obj->pushst);
}
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->popst);
STDestroy(&obj->pushst);
free(obj);
obj=NULL;
}
3.4设计循环队列
. - 力扣（LeetCode）
思路分析：
题意有限的资源重复利用保证先进先出，也就是要求head和tail在队列里回绕重复使用队列的空间
上述方法可以解决掉判空和判满的冲突问题
实现：
循环队列的结构体
<code>typedef struct {
int *a;
int head;//指向头
int tail;//指向尾的下一个
int k;
} MyCircularQueue;
初始化
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->;a=(int*)malloc(sizeof(int)*(k+1));
obj->head=obj->tail=0;
obj->k=k;
}
判空与判满
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->head==obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%(obj->k+1)==obj->head;
}
队列的插入
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return 0;
obj->a[obj->tail]=value;
obj->tail=(obj->tail+1)%(obj->k+1);
return 1;
}
队列的删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return 0;
obj->head++;
obj->head=(obj->head)%(obj->k+1);
return 1;
}
队头元素与队尾元素
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
else
return obj->a[obj->head];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
// return obj->tail==0?obj->a[obj->k]:obj->a[obj->tail-1];
return obj->a[((obj->tail-1)+(obj->k+1))%(obj->k+1)];
}
Tip：tail-1可能为负值越界所以需要加k+1再取模
队列的销毁
<code>void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->;a);
obj->a=NULL;
free(obj);
obj=NULL;
}
总的来说题之关键在于解决 空和满的判断冲突和循环回绕问题，对应的解决方法就是 k+1与取模
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。