数据结构——栈和队列

目录

一栈

1栈的概念及其结构

2栈的实现 

二队列

1队列的概念及其结构

2队列的实现

三相关题目

有效的括号

 用队列实现栈

用栈实现队列

设计循环队列

一栈

1栈的概念及其结构

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作；                                       进行数据插入和删除操作的一端称为栈顶，另一端称为栈底;                                                          栈中的数据元素遵守后进先出LIFO（Last In First Out）的特性

2栈的实现 

栈的实现有两者方式：数组栈和链式栈；一般选择用数组栈实现，代价小（在前文顺序表和链表中有提到是因为CPU缓存命中高）；如果用链式栈来实现时，是用单链表还是双链表呢？其实两种都是差不多的，但用单链表实现时栈顶和栈底的选择用注意了：如果用头节点做栈底，尾节点做栈顶就会返回麻烦，因为尾插尾删是单链表要进行找尾操作；所以要选择头节点做栈顶方便一点

在实现时我们用top变量指向栈顶元素，但在实现之前，会有一个问题：                                          如果初始化栈时，top = 0：这到底表示什么呢？

这样实现会出来歧义，解决方法有两种：

top = 0 ：代表空栈，当数据插入时top指向栈顶元素的下一个（实现时用这种方便扩容）                top = -1 : 代表空栈，当数据插入时top指向栈顶元素

//Inn.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define Max_Val 2

typedef int STDataType;
typedef struct Stack
{
    STDataType *_a;
    int _top;      // 栈顶
    int _capacity; // 容量
} Stack;

// 初始化栈
void StackInit(Stack *ps);
// 入栈
void StackPush(Stack *ps, STDataType data);
// 出栈
void StackPop(Stack *ps);
// 获取栈顶元素
STDataType StackTop(Stack *ps);
// 获取栈中有效元素个数
int StackSize(Stack *ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack *ps);
// 销毁栈
void StackDestroy(Stack *ps);

//Inn.c
#include "Inn.h"

void StackInit(Stack *ps)
{
    assert(ps);

    ps->_a = NULL;
    ps->_capacity = 0;
    ps->_top = 0;
}

void StackPush(Stack *ps, STDataType data)
{
    assert(ps);
    if (ps->_top == ps->_capacity)
    {
        int NewCapacity = ps->_capacity == 0 ? Max_Val : ps->_capacity * Max_Val;
        STDataType *new = (STDataType *)realloc(ps->_a, NewCapacity);
        if (new == NULL)
        {
            perror("reallpc fail");
            exit(-1);
        }
        ps->_a = new;
        ps->_capacity = NewCapacity;
    }
    ps->_a[ps->_top] = data;
    ps->_top++;
}

void StackPop(Stack *ps)
{
    assert(ps);
    // 不为空
    assert(ps->_top > 0);
    ps->_top--;
}

STDataType StackTop(Stack *ps)
{
    assert(ps);
    // 不为空
    assert(ps->_top > 0);
    return ps->_a[ps->_top - 1];
}

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

int StackEmpty(Stack *ps)
{
    assert(ps);
    // if (ps->_top == 0)
    //     return 1;
    // else
    //     return 0;
    return ps->_top == 0 ? 1 : 0;
}

void StackDestroy(Stack *ps)
{
    assert(ps);
    free(ps->_a);
    ps->_a = NULL;
    ps->_capacity = 0;
    ps->_top = 0;
}

二队列

1队列的概念及其结构

队列也是一种特殊线性表，只允许在一端进行插入数据操作，在另一端进行删除数据操作；         队列具有先进先出的特性；
进行插入操作的一端称为队尾；进行删除操作的一端称为队头

2队列的实现

与栈一样，队列也用两种方式：数组队列和链式队列；队列由于是入队在尾，出队在头，用数组就不合适（要头删移动数据），链表实现的话有两种：单链表和双链表，但是单链表要头插操作，所以你可能自然而然想用双链表来实现，但我们可以在单链表的基础上加上尾指针，这样的话就不用去找尾了，尾插自然就方便了，用单链表来实现反而是更高效的（双链表要malloc头节点，释放头节点），至于带不带哨兵位，个人实现就不带了（反正就多判断一次而已）！

//Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int QDataType;

// typedef struct queue
// {
//     QeDateType _val;
//     struct queue* _next;

//     struct queue* _phead;
//     struct queue* _tail;
// }qe;

typedef struct QueueNode
{
    QDataType _val;
    struct QueueNode *_next;
} node;

// void QueuePush(node*head,node* tail, QDataType data);

typedef struct Queue
{
    node *_front;
    node *_back;
    int _size;
} Queue;

// 初始化队列
void QueueInit(Queue *q);
// 队尾入队列
void QueuePush(Queue *q, QDataType data);
// 队头出队列
void QueuePop(Queue *q);
// 获取队列头部元素
QDataType QueueFront(Queue *q);
// 获取队列队尾元素
QDataType QueueBack(Queue *q);
// 获取队列中有效元素个数
int QueueSize(Queue *q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue *q);
// 销毁队列
void QueueDestroy(Queue *q);

//Queue.c
#pragma once
#include "queue.h"

void QueueInit(Queue *q)
{
    assert(q);
    q->_front = NULL;
    q->_back = NULL;
    q->_size=0;
}

void QueuePush(Queue *q, QDataType data)
{
    assert(q);
    node *tmp = (node *)malloc(sizeof(node));
    if (tmp == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    tmp->_val = data;
    tmp->_next = NULL;

    if (q->_back == NULL)
    {
        q->_front=q->_back = tmp;
    }
    else
    {
        q->_back->_next = tmp;
        // q->_back = q->_back->_next;
        q->_back=tmp;
    }
    q->_size++;
    // if (q->_front == NULL)
    //     q->_front = q->_back; // 尾即是头
}

void QueuePop(Queue *q)
{
    assert(q);
    assert(q->_front);
    node *tmp = q->_front;
    q->_front = q->_front->_next;
    free(tmp);
    tmp = NULL;
    //删除最后一个节点
    if(q->_front==NULL) q->_back=NULL;
    q->_size--;
}
QDataType QueueFront(Queue *q)
{
    assert(q);
    assert(q->_front);
    return q->_front->_val;
}

QDataType QueueBack(Queue *q)
{
    assert(q);
    assert(q->_back);
    return q->_back->_val;
}

int QueueSize(Queue *q)
{
    assert(q);
    // return q->_back - q->_front;
    return q->_size;
}

int QueueEmpty(Queue *q)
{
    assert(q);
    // if (q->_front == NULL || q->_back == NULL)
    //     return 1;
    // return 0;
    return q->_front==NULL;
}
void QueueDestroy(Queue *q)
{
    assert(q);
    node* cur=q->_front;
    while (cur)
    {
        node* next=cur->_next;
        free(cur);
        cur=next;
    }
    q->_front=q->_back=NULL;
    q->_size=0;
    // assert(q->_front);
    // while (q->_front != q->_back)
    // {
    //     node *next = q->_front->_next;
    //     free(q->_front);
    //     q->_front = next;
    // }
    // free(q->_front);
    // q->_front = NULL;
    // q->_back = NULL;
}

三相关题目

有效的括号

解法：模拟

（C语言）使用前面实现出来的栈和相应的接口进行使用

左括号入栈，遇到右括号判断栈顶是不是匹配的左括号，不是直接返回false，是就Pop后往下遍历下一个括号

遍历完成后看看栈里是否为空，为空代表括号都匹配完了，返回true 

#define Max_Val 2

typedef char STDataType;
typedef struct Stack
{
    STDataType *_a;
    int _top;      // 栈顶
    int _capacity; // 容量
} Stack;

// 初始化栈
void StackInit(Stack *ps);
// 入栈
void StackPush(Stack *ps, STDataType data);
// 出栈
void StackPop(Stack *ps);
// 获取栈顶元素
STDataType StackTop(Stack *ps);
// 获取栈中有效元素个数
int StackSize(Stack *ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack *ps);
// 销毁栈
void StackDestroy(Stack *ps);

void StackInit(Stack *ps)
{
    assert(ps);

    ps->_a = NULL;
    ps->_capacity = 0;
    ps->_top = 0;
}

void StackPush(Stack *ps, STDataType data)
{
    assert(ps);
    if (ps->_top == ps->_capacity)
    {
        int NewCapacity = ps->_capacity == 0 ? Max_Val : ps->_capacity * Max_Val;
        STDataType *new = (STDataType *)realloc(ps->_a, NewCapacity);
        if (new == NULL)
        {
            perror("reallpc fail");
            exit(-1);
        }
        ps->_a = new;
        ps->_capacity = NewCapacity;
    }
    ps->_a[ps->_top] = data;
    ps->_top++;
}

void StackPop(Stack *ps)
{
    assert(ps);
    // 不为空
    assert(ps->_top > 0);
    ps->_top--;
}

STDataType StackTop(Stack *ps)
{
    assert(ps);
    // 不为空
    assert(ps->_top > 0);
    return ps->_a[ps->_top - 1];
}

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

int StackEmpty(Stack *ps)
{
    assert(ps);
    // if (ps->_top == 0)
    //     return 1;
    // else
    //     return 0;
    return ps->_top == 0 ? 1 : 0;
}

void StackDestroy(Stack *ps)
{
    assert(ps);
    free(ps->_a);
    ps->_a = NULL;
    ps->_capacity = 0;
    ps->_top = 0;
}

bool isValid(char* s) {
    Stack st;
    StackInit(&st);
    while(*s)
    {
        char tmp=*s;
        if(tmp=='('||tmp=='['||tmp=='{') StackPush(&st,tmp);
        else
        {
            if(StackEmpty(&st)) return false;//必须栈里有左括号才能来判断，否则StackTop用不了
            char top=StackTop(&st);
            StackPop(&st);
            if(top=='('&&tmp!=')'||
               top=='['&&tmp!=']'||
               top=='{'&&tmp!='}')
            {
                return false;
            }
            // if(tmp==')'&&StackTop(&st)=='('||
            //    tmp==']'&&StackTop(&st)=='['||
            //    tmp=='}'&&StackTop(&st)=='{')
            // {
            //     StackPop(&st);
            // }
            // else return false;
        }
        s++;
    }
    if(StackSize(&st)) return false;//
    return true;
}

 用队列实现栈

解法：模拟

使用两个队列，一个队列存数据，一个队列进行导数据（当要pop时有数据的队列中的N-1个数据导到空队列来，再把最后一个数据pop掉） 

typedef int QDataType;

// typedef struct queue
// {
//     QeDateType _val;
//     struct queue* _next;

//     struct queue* _phead;
//     struct queue* _tail;
// }qe;

typedef struct QueueNode
{
    QDataType _val;
    struct QueueNode *_next;
} node;

// void QueuePush(node*head,node* tail, QDataType data);

typedef struct Queue
{
    node *_front;
    node *_back;
    int _size;
} Queue;

// 初始化队列
void QueueInit(Queue *q);
// 队尾入队列
void QueuePush(Queue *q, QDataType data);
// 队头出队列
void QueuePop(Queue *q);
// 获取队列头部元素
QDataType QueueFront(Queue *q);
// 获取队列队尾元素
QDataType QueueBack(Queue *q);
// 获取队列中有效元素个数
int QueueSize(Queue *q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue *q);
// 销毁队列
void QueueDestroy(Queue *q);

void QueueInit(Queue *q)
{
    assert(q);
    q->_front = NULL;
    q->_back = NULL;
    q->_size = 0;
}

void QueuePush(Queue *q, QDataType data)
{
    assert(q);
    node *tmp = (node *)malloc(sizeof(node));
    if (tmp == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    tmp->_val = data;
    tmp->_next = NULL;

    if (q->_back == NULL)
    {
        q->_front = q->_back = tmp;
    }
    else
    {
        q->_back->_next = tmp;
        // q->_back = q->_back->_next;
        q->_back = tmp;
    }
    q->_size++;
    // if (q->_front == NULL)
    //     q->_front = q->_back; // 尾即是头
}

void QueuePop(Queue *q)
{
    assert(q);
    assert(q->_front);
    node *tmp = q->_front;
    q->_front = q->_front->_next;
    free(tmp);
    tmp = NULL;
    // 删除最后一个节点
    if (q->_front == NULL)
        q->_back = NULL;
    q->_size--;
}
QDataType QueueFront(Queue *q)
{
    assert(q);
    assert(q->_front);
    return q->_front->_val;
}

QDataType QueueBack(Queue *q)
{
    assert(q);
    assert(q->_back);
    return q->_back->_val;
}

int QueueSize(Queue *q)
{
    assert(q);
    // return q->_back - q->_front;
    return q->_size;
}

int QueueEmpty(Queue *q)
{
    assert(q);
    // if (q->_front == NULL || q->_back == NULL)
    //     return 1;
    // return 0;
    return q->_front == NULL;
}
void QueueDestroy(Queue *q)
{
    assert(q);
    node *cur = q->_front;
    while (cur)
    {
        node *next = cur->_next;
        free(cur);
        cur = next;
    }
    q->_front = q->_back = NULL;
    q->_size = 0;
    // assert(q->_front);
    // while (q->_front != q->_back)
    // {
    //     node *next = q->_front->_next;
    //     free(q->_front);
    //     q->_front = next;
    // }
    // free(q->_front);
    // q->_front = NULL;
    // q->_back = NULL;
}

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

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

void myStackPush(MyStack *obj, int x)
{
    if (!QueueEmpty(&(obj->q1)))
        QueuePush(&(obj->q1), x);
    else
        QueuePush(&(obj->q2), x);
}

int myStackPop(MyStack *obj)
{
    Queue *empty = &(obj->q1), *NotEmpty = &(obj->q2);
    if (!QueueEmpty(empty))
    {
        empty = &(obj->q2);
        NotEmpty = &(obj->q1);
    }
    // 非空里的N-1个导入空
    while (QueueSize(NotEmpty) != 1)
    {
        int tmp = QueueFront(NotEmpty);
        QueuePop(NotEmpty);
        QueuePush(empty, tmp);
    }
    int top = QueueFront(NotEmpty);
    QueuePop(NotEmpty); // 后进先出
    return top;
}

int myStackTop(MyStack *obj)
{
    if (!QueueEmpty(&(obj->q1)))
        return QueueBack(&(obj->q1));
    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));
}

用栈实现队列

解法：模拟

#define Max_Val 2

typedef int STDataType;
typedef struct Stack
{
    STDataType *_a;
    int _top;      // 栈顶
    int _capacity; // 容量
} Stack;

// 初始化栈
void StackInit(Stack *ps);
// 入栈
void StackPush(Stack *ps, STDataType data);
// 出栈
void StackPop(Stack *ps);
// 获取栈顶元素
STDataType StackTop(Stack *ps);
// 获取栈中有效元素个数
int StackSize(Stack *ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack *ps);
// 销毁栈
void StackDestroy(Stack *ps);

void StackInit(Stack *ps)
{
    assert(ps);

    ps->_a = NULL;
    ps->_capacity = 0;
    ps->_top = 0;
}

void StackPush(Stack *ps, STDataType data)
{
    assert(ps);
    if (ps->_top == ps->_capacity)
    {
        int NewCapacity = ps->_capacity == 0 ? Max_Val : ps->_capacity * Max_Val;
        STDataType *new = (STDataType *)realloc(ps->_a, sizeof(STDataType) * NewCapacity);
        if (new == NULL)
        {
            perror("reallpc fail");
            exit(-1);
        }
        ps->_a = new;
        ps->_capacity = NewCapacity;
    }
    ps->_a[ps->_top] = data;
    ps->_top++;
}

void StackPop(Stack *ps)
{
    assert(ps);
    // 不为空
    assert(ps->_top > 0);
    ps->_top--;
}

STDataType StackTop(Stack *ps)
{
    assert(ps);
    // 不为空
    assert(ps->_top > 0);
    return ps->_a[ps->_top - 1];
}

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

int StackEmpty(Stack *ps)
{
    assert(ps);
    // if (ps->_top == 0)
    //     return 1;
    // else
    //     return 0;
    return ps->_top == 0 ? 1 : 0;
}

void StackDestroy(Stack *ps)
{
    assert(ps);
    free(ps->_a);
    ps->_a = NULL;
    ps->_capacity = 0;
    ps->_top = 0;
}

typedef struct
{
    Stack in;
    Stack out;
} MyQueue;

MyQueue *myQueueCreate()
{
    MyQueue *q = (MyQueue *)malloc(sizeof(MyQueue));
    if (q == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    StackInit(&(q->in));
    StackInit(&(q->out));
    return q;
}

void myQueuePush(MyQueue *obj, int x)
{

    StackPush(&(obj->in), x);
}

int myQueuePop(MyQueue *obj)
{
    if (StackEmpty(&(obj->out)))
    {
        while (!StackEmpty(&(obj->in)))
        {
            StackPush(&(obj->out), StackTop(&(obj->in)));
            StackPop(&(obj->in));
        }
    }
    int tmp = StackTop(&(obj->out));
    StackPop(&(obj->out));
    return tmp;
}

int myQueuePeek(MyQueue *obj)
{
    // 导数据
    if (StackEmpty(&(obj->out)))
    {
        while (!StackEmpty(&(obj->in)))
        {
            StackPush(&(obj->out), StackTop(&(obj->in)));
            StackPop(&(obj->in));
        }
    }

    return StackTop(&(obj->out));
}

bool myQueueEmpty(MyQueue *obj)
{
    return StackEmpty(&(obj->in)) && StackEmpty(&(obj->out));
}

void myQueueFree(MyQueue *obj)
{
    StackDestroy(&(obj->in));
    StackDestroy(&(obj->out));
}

设计循环队列

用链表实现的话要实现成循环链表，也要多开一个空间来方便处理，而且找队尾时要单独设计一个指针来找尾

//数组实现
typedef struct {
    int _front;
    int _back;
    int _k;
    int *_a;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* tmp=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    tmp->_a=(int*)malloc(sizeof(int)*(k+1));
    tmp->_front=0;
    tmp->_back=0;
    tmp->_k=k+1;//这里的_k是开辟k+1个空间的k
    return tmp;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->_front==obj->_back;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->_back+1)%obj->_k==obj->_front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj)) return false;
    obj->_a[obj->_back]=value;
    obj->_back=(obj->_back+1)%obj->_k;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) return false;
    obj->_front=(obj->_front+1)%obj->_k;
    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)%obj->_k];//back==0要特殊处理
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->_a);
    obj->_a=NULL;
    free(obj);
}

//链表实现
typedef struct QueueNode
{
    int _val;
    struct QueueNode* _next;
}node;

typedef struct {
    node* _front;
    node* _BackPrev;
    node* _back;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* tmp=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    tmp->_front=tmp->_BackPrev=tmp->_back=NULL;
    for(int i=0;i<=k;i++)//开k+1个空间
    {
        node* cur=(node*)malloc(sizeof(node));
        cur->_val=0;
        cur->_next=NULL;
        if(tmp->_front==NULL)
        {
            tmp->_front=tmp->_back=cur;
        }
        else
        {
            tmp->_back->_next=cur;
            tmp->_back=cur;
        }
    }
    tmp->_back->_next=tmp->_front;//构建循环链表
    tmp->_back=tmp->_front;//再将back指向front的位置
    tmp->_BackPrev=NULL;
    return tmp;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->_front==obj->_back;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->_back->_next==obj->_front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj)) return false;
    obj->_back->_val=value;
    obj->_BackPrev=obj->_back;//保存_back的前一个
    obj->_back=obj->_back->_next;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) return false;
    obj->_front=obj->_front->_next;
    return true;
}

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

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

void myCircularQueueFree(MyCircularQueue* obj) {
    while(obj->_front!=obj->_back)
    {
        node* next=obj->_front->_next;
        free(obj->_front);
        obj->_front=next;
    }
    free(obj->_back);
    obj->_front=NULL;
    obj->_back=NULL;
    obj->_BackPrev=NULL;
    free(obj);
}

以上便是全部内容，有问题欢迎在评论区指正，感谢观看！