C语言 栈和队列基本操作以及经典OJ题

栈

之前已经写过了顺序栈的表示方式link
今天来实现链式栈：

链式栈的基本操作

typedef int DataType;
typedef struct stack
{
    DataType data;
    struct stack* next;
}ST;

初始化栈

ST* Init()
{
    ST* phead=(ST*)malloc(sizeof(ST));
    phead->data=-1;
    phead->next=NULL;
    
    return phead;
}

入栈

入栈和出栈，分别对应头插和头删

ST* Create(DataType x)
{
    ST* new=(ST*)malloc(sizeof(ST));
    new->data=x;
    new->next=NULL;

    return new;
}
void Push(ST* head,DataType x)
{
    ST* new=Create(x);
    new->next=head->next;
    head->next=new;
}

出栈

void Pop(ST* head)
{
    if(isEmpty(head))
        return;
    ST* tmp=head->next;
    head->next=tmp->next;
    free(tmp);
}

判断栈空

int isEmpty(ST* head)
{
    return head->next==NULL;
}

取栈顶元素

DataType Top(ST* head)
{
    if(isEmpty(head))
        return;
    return head->next->data;
}

队列

循环队列

循环队列不需要构建结构体，构造三个全局变量Front（头指针），Rear（尾指针）还有Count（队列数量）就行。

初始化

#define MAX 100
typedef int DataType;
DataType queue[MAX];
int Front,Rear,Count;
void Init()
{
    Front=0;
    Rear=MAX-1;
    Count=0;
}

注意：Rear指向队尾元素，初始值在队列末尾，这样第一个元素进来的时候，下标刚好尾0；

入队

void Push(DataType x)
{
    if(isFull())
        return;
    Rear=(Rear+1)%MAX;
    queue[Rear]=x;
    Count++;
}

出队

DataType Pop()
{
    if(isEmpty())
        return -1;
    DataType e=queue[Front];
    Front=(Front+1)%MAX;
    Count--;
    return e;
}

判断空和满

int isFull()
{
    return Count==MAX;
}
int isEmpty()
{
    return Count==0;
}

链式队列

结构体

typedef int DataType;
typedef struct Qnode
{
    DataType data;
    struct Qnode* next;
}QNode;
QNode *Front,*Rear;

初始化

void Init()
{
    Front=NULL;
    Rear=NULL;
}

判断空

int isEmpty()
{
    return Front==NULL;
}

入队

void Push(DataType x)
{
    QNode* new=(QNode*)malloc(sizeof(QNode));
    new->data=x;
    new->next=NULL;

    if(Front==NULL)
    {
        Front=Rear=new;
        return;
    }
    Rear->next=new;
    Rear=Rear->next;
}

出队

DataType Pop()
{
    if(isEmpty())
        return;
    DataType tmp=Front->data;
    free(Front);
    Front=Front->next;
    if(Front==NULL)
        Rear=NULL;
    return tmp;
}

栈和队经典OJ题

括号匹配问题

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()” 输出：true

示例 2：

输入：s = “()[]{}” 输出：true

示例 3：

输入：s = “(]” 输出：false

题目链接：link
思路：遇左括号入栈，遇右括号，看看栈顶元素是否和右括号匹配。
我们先把栈的数据结构粘贴过来：

typedef char DataType;
typedef struct stack
{
    DataType data;
    struct stack* next;
}ST;

ST* Init()
{
    ST* phead=(ST*)malloc(sizeof(ST));
    phead->data=-1;
    phead->next=NULL;
    
    return phead;
}

ST* Create(DataType x)
{
    ST* new=(ST*)malloc(sizeof(ST));
    new->data=x;
    new->next=NULL;

    return new;
}
void Push(ST* head,DataType x)
{
    ST* new=Create(x);
    new->next=head->next;
    head->next=new;
}
int isEmpty(ST* head)
{
    return head->next==NULL;
}
void Pop(ST* head)
{
    if(isEmpty(head))
        return;
    ST* tmp=head->next;
    head->next=tmp->next;
    free(tmp);
}
DataType Top(ST* head)
{
    if(isEmpty(head))
        return 0;
    return head->next->data;
}
bool isValid(char* s) {
    ST* head=Init();
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        if(s[i]=='('||s[i]=='{'||s[i]=='[')
            Push(head,s[i]);
        else
        {
            char top=Top(head);
            if(top==0)
                return false;
            else
            {
                if(s[i]==')'&&top!='('||s[i]==']'&&top!='['||s[i]=='}'&&top!='{')
                    return false;
                else
                    Pop(head);
            }
        }
    }
    int i=isEmpty(head);
    if(i!=0)
        return true;
    else
       return false;
}

但是，不用栈的数据结构也可以做，只需要用到栈的后进先出思想就行，我们接下来做一步优化：

bool isValid(char* s) {
    int len=strlen(s);
    char stack[len];
    int top=-1;
    if(len%2!=0)
        return false;

    for(int i=0;i<len;i++)
    {
        if(s[i]=='{'||s[i]=='('||s[i]=='[')
            stack[++top]=s[i];
        else
        {
            if(top==-1)
                return false;
            else
            {
                char topchar=stack[top];
                if(s[i]=='}'&&topchar!='{'||s[i]==')'&&topchar!='('||s[i]==']'&&topchar!='[')
                    return false; 
                top--;
            }
        }
    }
    if(top!=-1)
        return false;
    else
        return true;
}

后面有很多类似的情况，比如队列、堆这些，有时候并不需要把完整的数据结构全敲出来，那样太浪费时间了，我们只需要用到他的思想就行。

约瑟夫问题

这个题不知道为什么力扣上搜不到了，口述一下就行：

编号为1到n的n个人围成一圈，从编号为1的人开始报数，报到m的人离开。下一个人继续从1开始报数。n-1轮结束以后，只剩下一个人，问最后留下的人的编号是多少。

主要思路就是创建一个单向不带头循环链表

#include
#include
#include
typedef struct node
{
    int val;
    struct node* next;
}NODE;
NODE* Create(int x)
{
    NODE* new=(NODE*)malloc(sizeof(NODE));
    new->val=x;
    new->next=NULL;
    return new;
}
NODE* List(int n)
{
    NODE* head=Create(1);
    NODE* cur=head;
    for(int i=2;i<=n;i++)
    {
        NODE* new=Create(i);
        cur->next=new;
        cur=cur->next;
    }
    cur->next=head;
    return cur;
}
void print(NODE* p)
{
    NODE* cur=p;
    do{
    printf("%d ",cur->val);
    cur=cur->next;
    }while(cur!=p);
    printf("\n");
}
int ysf(int n,int m)
{
    NODE* prev=List(n);
    NODE* cur=prev->next;
    int count=1;
    while(cur->next!=cur)
    {
        if(count==m)
        {
            prev->next=cur->next;
            free(cur);
            count=1;
            cur=prev->next;
            print(cur);
        }
        else
        {
            prev=cur;
            cur=cur->next;
            count++;
        }
    }
    return cur->val;
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int last=ysf(n,m);
    printf("%d",last);
    return 0;
}

看看测试结果：
第一行和最后一行表示输入和输出，中间部分是每一次删除一个元素后的队列。
这个题需要注意一个点：

NODE* List(int n)
{
    NODE* head=Create(1);
    NODE* cur=head;
    for(int i=2;i<=n;i++)
    {
        NODE* new=Create(i);
        cur->next=new;
        cur=cur->next;
    }
    cur->next=head;
    return cur;//为什么返回cur而不返回head?
}

那么我们为什么要返回cur，也就是单向循环链表的尾指针（头结点的前一个）呢？
因为在ysf函数里，

int ysf(int n,int m)
{
    NODE* prev=List(n);
    NODE* cur=prev->next;

如果m=1，也就是第一个报数的人如果要被删除，那么如果我们list的返回值是head，那么就无法访问到head的前一个节点，那么删除head以后，链表断裂，因此我们返回尾指针，就避免了这个问题。

剩下还有中缀表达式计算也是非常经典的题目，在后期复习我们作业的时候我会再继续分享。谢谢大家支持啦~