0
0

【leetcode】学了栈和队列却觉得无用武之地？试试这几道题目吧！

0.写在前面

这些题目所用语言为C语言，由于C语言未提供栈和队列的数据结构，所以需要我们手动实现栈和队列。此外熟练掌握栈和队列的性质对解题尤为重要。如果忘记了栈和队列的使用方法可在此直接跳转到栈和队列详解篇。

＜栈＞的概念&结构&实现【C语言版】http://t.csdn.cn/lqe2X＜队列＞的概念&结构&实现【C语言版】http://t.csdn.cn/iXiZI

1.leetcode.20 有效的括号

OJ链接：有效的括号（点此跳转）

解题思路：遍历字符串，如果碰到 ' ( ' 或 ' [ ' 或 ' { ' 就入栈；如果碰到字符是 ' ) ' ，栈顶的元素又是 ' ( '，就将栈顶的元素出栈。其他两种情况与之类似。

解题实战：

typedef char STDataType;

typedef struct Stack
{
    STDataType* a;  //动态开辟数组
    int capacity; //记录栈的容量大小
    int top; //记录栈顶的位置
}Stack;

//栈的初始化
void StackInit(Stack* ps);
//释放动态开辟的内存
void StackDestroy(Stack* ps);
//压栈
void StackPush(Stack* ps, STDataType data);
//出栈
void StackPop(Stack* ps);
//读取栈顶的元素
STDataType StackTop(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);
//栈存储的数据个数
int StackSize(Stack* ps);

void StackInit(Stack* ps)
{
    assert(ps);
    //初始化时，可附初值，也可置空
    ps->a = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

void StackDestroy(Stack* ps)
{
    assert(ps);
    //若并未对ps->a申请内存，则无需释放
    if (ps->capacity == 0)
        return;
    //释放
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps,STDataType data)
{
    assert(ps);
    //若容量大小等于数据个数，则说明栈已满，需扩容
    if (ps->capacity == ps->top)
    {
        //若为第一次扩容，则大小为4，否则每次扩大2倍
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tmp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }

        ps->a = tmp;
        ps->capacity = newCapacity;
    }
    //压栈
    ps->a[ps->top] = data;
    ps->top++;
}

void StackPop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    //出栈
    ps->top--;
}

STDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    //返回栈顶的数据
    return ps->a[ps->top - 1];
}

bool StackEmpty(Stack* ps)
{
    assert(ps);
    //返回top
    return ps->top == 0;
}

int StackSize(Stack* ps)
{
    assert(ps);
    return ps->top;
}
bool isValid(char* s) {
    Stack ST;
    StackInit(&ST);

    int pos=0;
    //遍历字符串，遇到'\0'结束
    while(*(s+pos) != '\0')
    {
        if(*(s+pos) == '(' || *(s+pos) == '[' || *(s+pos) == '{')
        {
            StackPush(&ST,*(s+pos));
        }
        else
        {
            if(StackEmpty(&ST))
                return false;
            if((ST.top != 0) &&
               (*(s+pos) == ')' && StackTop(&ST) == '(')||
               (*(s+pos) == ']' && StackTop(&ST) == '[')||
               (*(s+pos) == '}' && StackTop(&ST) == '{'))
            {
                StackPop(&ST);
            }
            else
            {
                return false;
            }
        } 

        pos++;
    }

    if( StackEmpty(&ST) )
    {
        return true;
    }
    else
    {
        return false;
    }
}

2.leetcode.225 用队列实现栈

OJ链接：用队列实现栈

解题思路：首先我们要清楚栈和队列的性质：

栈：先进后出。只在尾部删数据。

队列：先进先出。只在头部删数据。

也就是说，添加数据时，两个是一样的，区别在于删数据时。栈要pop一个数据时，其实pop的是队尾的数据，而不巧的是，队列不能在队尾pop数据。所以此时，我们用两个队列来完成。

栈的结构定义用两个队列来实现。

typedef struct {
    Queue q1;
    Queue q2;
    int size;
} MyStack;

使用两个队列的目的是，其中一个队列用来存储数据，另外一个空的队列在pop的时候用来接收非空的队列的数据。非空队列将数据全部拷贝到空队列，只留下一个队尾的数据，此时，队列只剩一个元素，它既在队尾也在队头，所以就可以pop了。

解题实战：

typedef int QDataType;

typedef struct QueueNode
{
    QDataType data; //存储的数据
    struct QueueNode* next; //记录下一个结点的位置
}QNode;

typedef struct Queue
{
    QNode* head; //记录队头的位置
    QNode* tail; //记录队尾的位置
    int size; //记录队列的长度
}Queue;

//队列的初始化
void QueueInit(Queue* pq);
//释放malloc出的内存
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->head = NULL;
    pq->tail = NULL;
    pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);
    //用cur找尾
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* del = cur;
        cur = cur->next;

        free(del);
    }
    pq->size = 0;
    pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq,QDataType data)
{
    assert(pq);

    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }

    //初始化结点
    newNode->data = data;
    newNode->next = NULL;

    if (pq->tail == NULL)
    {
        //队列为空时入队
        pq->head = newNode;
        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);
    }
    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->size==0;
    return pq->head == NULL && pq->tail == NULL;
}

int QueueSize(Queue* pq)
{
    assert(pq);

    return pq->size;
}

typedef struct {
    Queue q1;
    Queue q2;
    int size;
} MyStack;

MyStack* myStackCreate() {
    MyStack* ps=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&ps->q1);
    QueueInit(&ps->q2);
    ps->size=0;
    return ps;
}

void myStackPush(MyStack* obj, int x) {
    //找一个不为空的队列来push数据
    Queue* noneQueue=(&obj->q1)->size == 0?&obj->q2:&obj->q1;
    QueuePush(noneQueue,x);
    obj->size++;
}

int myStackPop(MyStack* obj) {
    //找空队列
    if ((obj->q2).size == 0)
    {
        QDataType top;
        //复制数据
        while ((&obj->q1)->size > 1)
        {
            top = QueueFront(&obj->q1);
            QueuePop(&obj->q1);
            QueuePush(&obj->q2,top);
        }
        top=QueueFront(&obj->q1);
        QueuePop(&obj->q1);
        obj->size--;
        return top;
    }
    else
    {
        QDataType top;
        //复制数据
        while ((&obj->q2)->size > 1)
        {
            top = QueueFront(&obj->q2);
            QueuePop(&obj->q2);
            QueuePush(&obj->q1,top);
        }
        top = QueueFront(&obj->q2);
        QueuePop(&obj->q2);
        obj->size--;
        return top;
    }
 
}                                        

int myStackTop(MyStack* obj) {
    
    if ((&obj->q1)->size != 0)
        return (&obj->q1)->tail->data;
    else
        return (&obj->q2)->tail->data;

}

bool myStackEmpty(MyStack* obj) {
    return !obj->size;
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj=NULL;
}

3.leetcode.232 用栈实现队列

OJ链接：用栈实现队列

解题思路：同上一题的思路，本题也是用两个栈实现队列。其中s1用来push，s2用来pop和peek。与上一题不同的是，这次pop时，不用一直将s1的数据导入到s2中。而是当s2为空时再导入。

解题实战：

typedef int STDataType;

typedef struct Stack
{
    STDataType* a;  //动态开辟数组
    int capacity; //记录栈的容量大小
    int top; //记录栈顶的位置
}Stack;

//栈的初始化
void StackInit(Stack* ps);
//释放动态开辟的内存
void StackDestroy(Stack* ps);
//压栈
void StackPush(Stack* ps, STDataType data);
//出栈
void StackPop(Stack* ps);
//读取栈顶的元素
STDataType StackTop(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);
//栈存储的数据个数
int StackSize(Stack* ps);

void StackInit(Stack* ps)
{
    assert(ps);
    //初始化时，可附初值，也可置空
    ps->a = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

void StackDestroy(Stack* ps)
{
    assert(ps);
    //若并未对ps->a申请内存，则无需释放
    if (ps->capacity == 0)
        return;
    //释放
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps,STDataType data)
{
    assert(ps);
    //若容量大小等于数据个数，则说明栈已满，需扩容
    if (ps->capacity == ps->top)
    {
        //若为第一次扩容，则大小为4，否则每次扩大2倍
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tmp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }

        ps->a = tmp;
        ps->capacity = newCapacity;
    }
    //压栈
    ps->a[ps->top] = data;
    ps->top++;
}

void StackPop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    //出栈
    ps->top--;
}

STDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    //返回栈顶的数据
    return ps->a[ps->top - 1];
}

bool StackEmpty(Stack* ps)
{
    assert(ps);
    //返回top
    return ps->top == 0;
}

int StackSize(Stack* ps)
{
    assert(ps);
    return ps->top;
}

typedef struct {
    Stack s1; //用来push数据
    Stack s2; //用来pop和peek
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue* myqueue = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&myqueue->s1);
    StackInit(&myqueue->s2);
    return myqueue;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->s1, x);
}

int myQueuePeek(MyQueue* obj) {
    //s2不为空时，不用再将s1的数据导入到s2
    if(StackEmpty(&obj->s2))
    {
        //将s1的数据倒着push到s2中
        while (!StackEmpty(&obj->s1))
        {
            STDataType top = StackTop(&obj->s1);
            StackPop(&obj->s1);
            StackPush(&obj->s2, top);
        }
    }
    //此时s2的数据是逆置的，所以栈顶的数据也就是队头的数据
    return StackTop(&obj->s2);

}

int myQueuePop(MyQueue* obj) {

    STDataType top= myQueuePeek(obj);
    //此时s2的数据是逆置的，pop s2栈顶的数据，也就是pop队头的数据
    StackPop(&obj->s2);
    return top;
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s2);
    free(obj);
    obj = NULL;

4.leetcode.622 设计循环队列

OJ链接：设计循环队列

解题思路：循环队列与普通的队列就两点差别。

1.增加一个capacity来记录队列的容量

2.队尾与队头相连（称之为循环）

解题实战：

typedef int QDataType;

typedef struct QueueNode
{
    QDataType data; //存储的数据
    struct QueueNode* next; //记录下一个结点的位置
}QNode;

typedef struct {
    QNode* head;
    QNode* tail;
    int size;
    int capacity;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* tmp=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    tmp->head=NULL;
    tmp->tail=NULL;
    tmp->size=0;
    tmp->capacity=k;
    return tmp;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    
    if(myCircularQueueIsFull(obj))
        return false;

    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    newNode->next = NULL;
    newNode->data = value;
    if (obj->size == 0)
    {
        obj->head = obj->tail = newNode;
        obj->size++;

    }
    else
    {
        obj->tail->next = newNode;
        obj->tail = newNode;
        newNode->next=obj->head;
        obj->size++;
    }

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    
    if(myCircularQueueIsEmpty(obj))
        return false;

    QNode* cur=obj->head;
    obj->head=obj->head->next;
    obj->tail->next=obj->head;
    free(cur);
    obj->size--;
    return true;

}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->head->data;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->tail->data;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return !obj->size;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->size==obj->capacity;
}

void myCircularQueueFree(MyCircularQueue* obj) {

    if(myCircularQueueIsEmpty(obj))
    {
        free(obj);
        return;
    }
    while(obj->head!=obj->tail)
    {
        QNode* cur=obj->head;
        obj->head=obj->head->next;
        free(cur);
    }
    free(obj->head);
    free(obj);
    obj=NULL;
}
标签： 数据结构 leetcode 栈
本文转载自: https://blog.csdn.net/gllll_yu/article/details/128751879
版权归原作者 花想云 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【leetcode】学了栈和队列却觉得无用武之地？试试这几道题目吧！”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

通过SSH操作Linux虚拟机

C#学习笔记（三）Visual Studio安装与使用

JPA基础教程：实体操作和数据库交互实践

开源低代码-Microi吾码报表引擎

HiveSQL：提取json串内容（含key为中文情况）——get_json_oject和json_tuple

Spring Cloud Stream 3.x+kafka 3.8整合

【大数据·hadoop】项目实践：IDEA实现WordCount词频统计项目

文章导航