首页 > 其他分享 >栈和队列(原理、代码实现、例题)

栈和队列(原理、代码实现、例题)

时间:2024-11-10 12:16:56浏览次数:6  
标签:pq obj 队列 代码 ST assert return 例题 pst

一、栈

1.概念

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。

栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据也在栈顶。

1

2

2.实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。

因为数组在尾上插入数据的代价比较小。

3

数组栈

stack.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
​
typedef int STDataType;
​
typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;
​
void StInit(ST* pst);
void StDestory(ST* pst);
void StPush(ST* pst, STDataType x);
void StPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);

stack.c

#include"Stack.h"
​
void StInit(ST* pst)
{
    assert(pst);
​
    pst->a = NULL;
    pst->capacity = 0;
    pst->top = 0;
}
​
void StDestory(ST* pst)
{
    assert(pst);
​
    free(pst->a);
    pst->a = NULL;
    pst->top = pst->capacity = 0;
}
​
void StPush(ST* pst, STDataType x)
{
    assert(pst);
​
    if (pst->top == pst->capacity)
    {
        int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc failed");
            return;
        }
        pst->a = tmp;
        pst->capacity = newcapacity;
    }
​
    pst->a[pst->top] = x;
    ++pst->top;
}
​
void StPop(ST* pst)
{
    assert(pst);
    assert(pst->top > 0);
    
    pst->top--;
}
​
STDataType STTop(ST* pst)
{
    assert(pst);
    assert(pst->top > 0);
​
    return pst->a[pst->top - 1];
}
​
bool STEmpty(ST* pst)
{
    assert(pst);
    /*if (pst->top == 0)
    {
        return true;
    }
    else
    {
        return false;
    }*/
​
    return pst->top == 0;
}
​
int STSize(ST* pst)
{
    assert(pst);
​
    return pst->top;
}

二、队列

1.概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,

队列具有先进先出FIFO(First In First Out)

入队列:进行插入操作的一端称为队尾

出队列:进行删除操作的一端称为队头

4

2.实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,

因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。

5

6

链式队列

Queue.h

#pragma once
​
#include<stdio.h>
#include <assert.h>
#include <stdbool.h>
#include<stdlib.h>
#include<math.h>
​
​
​
typedef int QDataType;
​
typedef struct QueueNode
{
    QDataType val;
    struct QueueNode* next;
}QNode;
​
typedef struct Queue
{
    QNode* phead;
    QNode* ptail;
    int size;
}Queue;
​
​
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QuqueFront(Queue* pq); 
QDataType QuqueBack(Queue* pq);
bool QueueEmpty(Queue* pq); 
int QueueSize(Queue* pq);

Queue.c

#include"Queue.h"
​
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->phead;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->phead = pq->ptail = 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->val = x;
    newnode->next = NULL;
​
    if (pq->ptail == NULL)
    {
        pq->phead = pq->ptail = newnode;
    }
    else
    {
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
    ++pq->size;
}
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->phead);
​
    QNode* del = pq->phead;
    pq->phead = pq->phead->next;
    free(del);
    del = NULL;
​
    if (pq->phead == NULL)
    {
        pq->ptail = NULL;
    }
    pq->size--;
}
QDataType QuqueFront(Queue* pq)
{
    assert(pq);
    assert(pq->phead);
​
    return pq->phead->val;
}
QDataType QuqueBack(Queue* pq)
{
    assert(pq);
    assert(pq->ptail);
​
    return pq->ptail->val;
}
bool QueueEmpty(Queue* pq)
{
    assert(pq);
​
    return pq->phead == NULL;
}
int QueueSize(Queue* pq)
{
    assert(pq);
​
    return pq->size;
}

3.拓展

实际中我们有时还会使用一种队列叫循环队列。

如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。

环形队列可以使用数组实现,也可以使用循环链表实现。

image-20241108232203997

三、例题

1.力扣20:有效的括号

typedef char STDataType;
​
typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;
​
void StInit(ST* pst);
void StDestory(ST* pst);
void StPush(ST* pst, STDataType x);
void StPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);
​
​
void StInit(ST* pst)
{
    assert(pst);
​
    pst->a = NULL;
    pst->capacity = 0;
    pst->top = 0;
}
​
void StDestory(ST* pst)
{
    assert(pst);
​
    free(pst->a);
    pst->a = NULL;
    pst->top = pst->capacity = 0;
}
​
void StPush(ST* pst, STDataType x)
{
    assert(pst);
​
    if (pst->top == pst->capacity)
    {
        int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc failed");
            return;
        }
        pst->a = tmp;
        pst->capacity = newcapacity;
    }
​
    pst->a[pst->top] = x;
    ++pst->top;
}
​
void StPop(ST* pst)
{
    assert(pst);
    assert(pst->top > 0);
    
    --pst->top;
}
​
STDataType STTop(ST* pst)
{
    assert(pst);
    assert(pst->top > 0);
​
    return pst->a[pst->top - 1];
}
​
bool STEmpty(ST* pst)
{
    assert(pst);
    /*if (pst->top == 0)
    {
        return true;
    }
    else
    {
        return false;
    }*/
​
    return pst->top == 0;
}
​
int STSize(ST* pst)
{
    assert(pst);
​
    return pst->top;
}
​
​
bool isValid(char* s) 
{
    ST st;
    StInit(&st);
    while(*s)
    {
        if(*s=='{'||*s=='('||*s=='[')
        {
            StPush(&st,*s);
        }
        else
        {
            if(STEmpty(&st))
            {
                StDestory(&st);
                return false;
            }
            char top=STTop(&st);
            StPop(&st);
​
            if((*s==']'&&top!='[')||
            (*s==')'&&top!='(')||
            (*s=='}'&&top!='{'))
            {
                StDestory(&st);
                return false;
            }
        }
        ++s;
    }
    bool ret=STEmpty(&st);
​
    StDestory(&st);
​
    return ret;
​
}

2.力扣225:用队列实现栈

typedef struct QueueNode
{
    QDataType val;
    struct QueueNode* next;
}QNode;
​
typedef struct Queue
{
    QNode* phead;
    QNode* ptail;
    int size;
}Queue;
​
​
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq); 
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq); 
int QueueSize(Queue* pq);
​
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->phead;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->phead = pq->ptail = 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->val = x;
    newnode->next = NULL;
​
    if (pq->ptail == NULL)
    {
        pq->phead = pq->ptail = newnode;
    }
    else
    {
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
    ++pq->size;
}
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->phead);
​
    QNode* del = pq->phead;
    pq->phead = pq->phead->next;
    free(del);
    del = NULL;
​
    if (pq->phead == NULL)
    {
        pq->ptail = NULL;
    }
    pq->size--;
}
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->phead);
​
    return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->ptail);
​
    return pq->ptail->val;
}
bool QueueEmpty(Queue* pq)
{
    assert(pq);
​
    return pq->phead == NULL;
}
int QueueSize(Queue* pq)
{
    assert(pq);
​
    return pq->size;
}
​
typedef struct
{
    Queue q1;
    Queue q2;
} MyStack;
​
​
MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
​
    return pst;
}
​
void myStackPush(MyStack* obj, int x) {
    if (!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}
​
int myStackPop(MyStack* obj) 
{
    QNode* empty = &obj->q1;
    QNode* nonempty = &obj->q2;
    if (!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        nonempty = &obj->q1;
    }
    while (QueueSize(nonempty) > 1)
    {
        QueuePush(empty, QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int front = QueueFront(nonempty);
    QueuePop(nonempty);
    return front;
}
​
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));
}
​
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
​
    free(obj);
}

3.力扣232:用栈实现队列

typedef int STDataType;
​
typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;
​
void StInit(ST* pst);
void StDestory(ST* pst);
void StPush(ST* pst, STDataType x);
void StPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);
​
void StInit(ST* pst)
{
    assert(pst);
​
    pst->a = NULL;
    pst->capacity = 0;
    pst->top = 0;
}
​
void StDestory(ST* pst)
{
    assert(pst);
​
    free(pst->a);
    pst->a = NULL;
    pst->top = pst->capacity = 0;
}
​
void StPush(ST* pst, STDataType x)
{
    assert(pst);
​
    if (pst->top == pst->capacity)
    {
        int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc failed");
            return;
        }
        pst->a = tmp;
        pst->capacity = newcapacity;
    }
​
    pst->a[pst->top] = x;
    ++pst->top;
}
​
void StPop(ST* pst)
{
    assert(pst);
    assert(pst->top > 0);
    
    --pst->top;
}
​
STDataType STTop(ST* pst)
{
    assert(pst);
    assert(pst->top > 0);
​
    return pst->a[pst->top - 1];
}
​
bool STEmpty(ST* pst)
{
    assert(pst);
    /*if (pst->top == 0)
    {
        return true;
    }
    else
    {
        return false;
    }*/
​
    return pst->top == 0;
}
​
int STSize(ST* pst)
{
    assert(pst);
​
    return pst->top;
}
​
​
typedef struct {
    ST pushst;
    ST popst;
} MyQueue;
​
​
MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    StInit(&obj->pushst);
    StInit(&obj->popst);
​
    return obj;
}
​
void myQueuePush(MyQueue* obj, int x) {
    StPush(&obj->pushst,x);
}
​
int myQueuePop(MyQueue* obj) {
    int top=myQueuePeek(obj);
    StPop(&obj->popst);
    return top;
}
​
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->pushst)&&STEmpty(&obj->popst);
}
​
void myQueueFree(MyQueue* obj) {
    StDestory(&obj->pushst);
    StDestory(&obj->popst);
    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);
*/

4.力扣622:设计循环队列

typedef struct {
    int*a;
    int front;
    int back;
    int k;
} MyCircularQueue;
​
​
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=0;
    obj->back=0;
    obj->k=k;
​
    return obj;
}
​
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->back;
}
​
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back+1)%(obj->k+1)==obj->front;
}
​
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->back]=value;
    ++obj->back;
    (obj->back)%=(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->back-1+obj->k+1)%(obj->k+1)];
}
​
​
​
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}
​
/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

标签:pq,obj,队列,代码,ST,assert,return,例题,pst
From: https://blog.csdn.net/lll_666666/article/details/143658779

相关文章