0
0

数据结构51题之栈和队列18题

创作不易，点个关注加个收藏再走，防止找不到

一、栈系列基础8道题

1.顺序栈的建立

1.定义顺序栈的存储结构
2.初始化顺序栈为空栈（InitStack_Sq）
3.输入要入栈的元素个数n
4.向顺序栈中压入n个元素（Push_Sq）
5.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq）
6.销毁顺序栈（DestroyStack_Sq）
例如：
5
4 3 5 10 9
9 10 5 3 4 //遍历输出时最后一个元素后有一个空格

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int SElemType;
#define MAXSIZE 100
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

Status InitStack_Sq(SqStack *S)
{
    S->base=(int*)malloc (sizeof(int)*MAXSIZE);
    if(!S->base) exit(OVERFLOW);
    S->top=S->base;
    S->stacksize=MAXSIZE;
    return OK;
}

void DestroyStack_Sq(SqStack *S)
{
    if(S->base) free(S->base);
    S->top=S->base=NULL;
}

//在此处定义入栈函数Push_Sq
int Push_Sq(SqStack *S,int n)
{
  for(int i=0;i<n;i++)
  {
     int e;
      scanf("%d",&e);
      *S->top=e;
     S->top++;
  }
  
  
    
}

void StackTraverse_Sq(SqStack *S,int n)
{
    
      for(int i=0;i<n;i++)
    {
        S->top--;
        printf("%d ",*S->top);
    }
    
    
    
    
}

int main()
{
    SqStack S;
    InitStack_Sq(&S);
    int n;
    SElemType e;
scanf("%d",&n);
Push_Sq(&S,n);
    StackTraverse_Sq(&S,n);
    DestroyStack_Sq(&S);
    return 0;
}

2.顺序栈的入栈

1.定义顺序栈入栈函数（Push_Sq）
2.输入要入栈的元素个数n
3.向顺序栈中压入n个元素
4.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq）
5.销毁顺序栈（DestroyStack_Sq）
例如：
5
6 2 8 10 9
9 10 8 2 6 //遍历输出时最后一个元素后有一个空格

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int SElemType;
#define MAXSIZE 100
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

Status InitStack_Sq(SqStack *S)
{
    S->base=(int*)malloc (sizeof(int)*MAXSIZE);
    if(!S->base) exit(OVERFLOW);
    S->top=S->base;
    S->stacksize=MAXSIZE;
    return OK;
}

void DestroyStack_Sq(SqStack *S)
{
    if(S->base) free(S->base);
    S->top=S->base=NULL;
}

//在此处定义入栈函数Push_Sq
int Push_Sq(SqStack *S,int n)
{
  for(int i=0;i<n;i++)
  {
     int e;
      scanf("%d",&e);
      *S->top=e;
     S->top++;
  }
  
  
    
}

void StackTraverse_Sq(SqStack *S,int n)
{
    
      for(int i=0;i<n;i++)
    {
        S->top--;
        printf("%d ",*S->top);
    }
    
    
    
    
}

int main()
{
    SqStack S;
    InitStack_Sq(&S);
    int n;
    SElemType e;
scanf("%d",&n);
Push_Sq(&S,n);
    StackTraverse_Sq(&S,n);
    DestroyStack_Sq(&S);
    return 0;
}

3.顺序栈的出栈

1.定义顺序栈出栈函数（Pop_Sq）
2.定义求顺序栈栈长函数（StackLength_Sq）
3.输入要入栈的元素个数n
4.向顺序栈中压入n个元素
5.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq）
6.销毁顺序栈（DestroyStack_Sq）
例如：
4
2 4 6 8
8 6 4 2 //遍历输出时最后一个元素后有一个空格
4
6 4 2 //遍历输出时最后一个元素后有一个空格
8
3

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int SElemType;
#define MAXSIZE 100
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack ;

Status InitStack_Sq(SqStack *S)
{
    S->base=(SElemType*) malloc (sizeof(int)*MAXSIZE);
    if(!S->base) exit(OVERFLOW);
    S->top=S->base;
    S->stacksize=MAXSIZE;
    return OK;
}

void DestroyStack_Sq(SqStack *S)
{
    if(S->base) 
    free (S->base);
    S->top=S->base=NULL;
}

//此处定义求栈长函数StackLength_Sq
       void StackLength_Sq(SqStack *S)
       {
           
           if(S->top==S->base)
           {
               exit(0);
           }
           int y=S->top-S->base;
           printf("%d ",y);
           
       }

Status Push_Sq(SqStack *S,SElemType e)
{
    if(S->top-S->base==S->stacksize) return ERROR;
    *S->top++=e;
    return OK;
}

//此处定义出栈函数

int Pop_Sq(SqStack* S)
{
            int e;
         S->top--;
        e=*S->top;
//printf("%d    ",e);
        return e;
    
    
}

void StackTraverse_Sq(SqStack *S,int n)
{            int e;
int *p=S->top;

        for(int i=0;i<n;i++)
        {
            S->top--;
            e=*S->top;
            printf("%d ",e);    
        }
S->top=p;        
}
SqStack* yazhan(SqStack *S,int n)
{
    int u;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&u);
           *S->top++=u;  
    }
    return S;
}
int main()
{
    SqStack S;
    SElemType e;
    InitStack_Sq(&S);
    int n;
        //SElemType y;
        scanf("%d",&n);
        yazhan(&S,n);
        StackTraverse_Sq(&S,n);
         printf("\n");
        StackLength_Sq(&S);
        printf("\n");
    
         e=Pop_Sq(&S);
         StackTraverse_Sq(&S,S.top-S.base);
         printf("\n");
         printf("%d",e);
             printf("\n");
          StackLength_Sq(&S);
         return 0;
}

4.顺序栈栈顶元素的获取

1.定义获取顺序栈栈顶元素函数（GetTop_Sq）
2.输入要入栈的元素个数n
3.向顺序栈中压入n个元素
4.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq）
5.获取栈顶元素
6.输出栈顶元素
7.销毁顺序栈（DestroyStack_Sq）
例如：
4
2 4 6 8
8 6 4 2 //遍历输出时最后一个元素后有一个空格
8

/*1.定义获取顺序栈栈顶元素函数（GetTop_Sq）
2.输入要入栈的元素个数n
3.向顺序栈中压入n个元素
4.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq）
5.获取栈顶元素
6.输出栈顶元素
7.销毁顺序栈（DestroyStack_Sq）
例如：
4
2 4 6 8
8 6 4 2 //遍历输出时最后一个元素后有一个空格
8*/

#include <stdio.h>
# include <stdlib.h>
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int SElemType;
#define MAXSIZE 100
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

Status InitStack_Sq(SqStack *S)
{
    S->base=(int *) malloc (sizeof(int)*MAXSIZE);
    if(!S->base) exit(OVERFLOW);
    S->top=S->base;
    S->stacksize=MAXSIZE;
    return OK;
}

void DestroyStack_Sq(SqStack *S)
{
    if(S->base) free(S->base);
    S->top=S->base=NULL;
}

//此处定义获取栈顶元素函数GetTop_Sq

    int  GetTop_Sq(SqStack *S)
    {
        int *p=S->top;
        int y;
        S->top--;
        y=*S->top;
        S->top=p;
        return y;
    }

Status Push_Sq(SqStack *S,SElemType e)
{
    if(S->top-S->base==S->stacksize) return ERROR;
    *S->top++=e;
    return OK;
}

void StackTraverse_Sq(SqStack* S,int n)
{
    int w;
int *p;
    p=S->top;
    for(int i=0;i<n;i++)
    {
        S->top--;
        w=*S->top;
        printf("%d ",w);    
    }
    S->top=p;
    printf("\n");
}

SqStack * shuru(SqStack *S,int n)
 {
     int y;
     for(int i=0;i<n;i++)
     {
     
         scanf("%d",&y);
         *S->top++=y;
     }

 return S;
     
 }

int main()
{
    SqStack S;
    SElemType e;
    InitStack_Sq(&S);
    int n;
    scanf("%d",&n);
   S=*shuru(&S,n);
//    printf("\n");
    StackTraverse_Sq(&S,n);

    //此处调用获取栈顶元素函数，将其存储在参数e中
e=GetTop_Sq(&S);
printf("%d ",e);
    return 0;
}

5.链栈的建立

1.定义链栈的结点存储结构
2.初始化链栈为空栈（InitStack_Link）
3.输入要入栈的元素个数n
4.向链栈中压入n个元素（Push_Link）
5.从栈顶到栈底遍历链栈数据（StackTraverse_Link）
6.销毁链栈（DestroyStack_Link）
例如：
5
4 3 5 10 9
9 10 5 3 4 //遍历输出时最后一个元素后有一个空格

# include<stdio.h>
# include <stdlib.h>
typedef struct Lstack
{
    int data;
    struct Lstack *next;
}Lstack,*LinkStack;
int InitStack_Link(LinkStack S)
{
    S=NULL;
  return 1;  
}
void StackTraverse_Link(LinkStack S)
{ //int i=0;
    LinkStack p=S;
    while(p)
    {
       // i++;
        printf("%d ",p->data);
        p=p->next;
    }
}
LinkStack Push_Link(LinkStack S,int n)
{               int y;
            LinkStack p;
            for(int i=0;i<n;i++)
            {
                if(i==0)
                {
                p=(LinkStack)malloc(sizeof(Lstack));
                scanf("%d",&y);
                p->data=y;
                p->next=NULL;
                 S=p;
                }
               else{
                   
                   p=(LinkStack)malloc(sizeof(Lstack));
                scanf("%d",&y);
                p->data=y;
                p->next=S;
                 S=p;
               }
               
            }

                return S;    
}
void DestroyStack_Link(LinkStack S)
{
    LinkStack p=S;
   while(p){
       S=S->next;
       free(p);
       p=S;
}}
int main()
{

    LinkStack S;
    int n;
    InitStack_Link(S);
    scanf("%d",&n);
    S=Push_Link(S,n);
    StackTraverse_Link(S);
    printf("\n");    

    DestroyStack_Link(S);
//    printf("over");
    
    return 0;
}

6.链栈的入栈

1.定义链栈的入栈函数（Push_Link）
2.输入要入栈的元素个数n
3.向顺序栈中压入n个元素
4.将链栈中的元素从栈顶到栈底依次输出（StackTraverse_Link）
5.销毁链栈栈（DestroyStack_Link）
例如：
5
1 2 3 4 5
5 4 3 2 1 //遍历输出时最后一个元素后有一个空格

/*1.定义链栈的入栈函数（Push_Link）
2.输入要入栈的元素个数n
3.向顺序栈中压入n个元素
4.将链栈中的元素从栈顶到栈底依次输出（StackTraverse_Link）
5.销毁链栈栈（DestroyStack_Link）
例如：
5
1 2 3 4 5
5 4 3 2 1  //遍历输出时最后一个元素后有一个空格*/
# include <stdio.h>
# include <stdlib.h>

#define MAXSIZE 100
typedef struct StackNode
{
    int data;
    struct StackNode *next;
}StackNode,*LinkStack;

int Initstack(LinkStack S) {
    S=NULL;
    return 1; 
}
LinkStack Push_Link(LinkStack S,int n)
{
            int y;
            LinkStack p;
            for(int i=0;i<n;i++)
            {
                if(i==0)
                {
                p=(LinkStack)malloc(sizeof(StackNode));
                scanf("%d",&y);
                p->data=y;
                p->next=NULL;
                 S=p;
                }
               else{
                   
                   p=(LinkStack)malloc(sizeof(StackNode));
                scanf("%d",&y);
                p->data=y;
                p->next=S;
                 S=p;
               }
               
            }

                return S;    
}
void StackTraverse_Link(LinkStack S,int n)
{
    LinkStack p=S;
for(int i=0;i<n;i++)
    {
        
        printf("%d ",p->data);
            p=p->next;
     } 
    
}
void  DestroyStack_Link(LinkStack S)
{ 

    LinkStack p=S;
   while(p){
       S=S->next;
      free(p);
       p=S;
}}
    

int main()
{
LinkStack S;
Initstack(S);
int n;
scanf("%d",&n);
S=Push_Link(S,n);
 StackTraverse_Link(S,n);
  //
 DestroyStack_Link(S);
 return 0;    
}

7.链栈的出栈

1.定义求栈长函数（StackLength_Link）
2.定义出栈函数（Pop_Link）
3.输入要入栈的元素个数n
4.向顺序栈中压入n个元素（Push_Link）
5.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Link）
6.输出栈长
7.执行出栈操作
8.将顺序栈中的元素从栈顶到栈底依次输出
9.输出出栈元素
10.输出栈长
11.销毁链栈（DestroyStack_Link）
例如：
5
1 2 3 4 5
5 4 3 2 1 //遍历输出时最后一个元素后有一个空格
5
4 3 2 1 //遍历输出时最后一个元素后有一个空格
5
4

# include<stdio.h>
# include <stdlib.h>
typedef struct Lstack
{
    int data;
    struct Lstack *next;
}Lstack,*LinkStack;
int Init_S(LinkStack S)
{
    S=NULL;
  return 1;  
}
int StackLength_Link(LinkStack S)
{          int i=0;

    LinkStack p = S;
    while (p){
        
       if(p->next!=NULL)
       {i++;
           p = p->next;
        
       }
        else
        {
            i++;
           return i;
        }

    }

   
   

   
}
void StackTraverse_Link(LinkStack S)
{ //int i=0;
    LinkStack p=S;
    while(p)
    {
       // i++;
        printf("%d ",p->data);
        p=p->next;
    }
}
LinkStack Push_Link(LinkStack S,int n)
{               int y;
            LinkStack p;
            for(int i=0;i<n;i++)
            {
                if(i==0)
                {
                p=(LinkStack)malloc(sizeof(Lstack));
                scanf("%d",&y);
                p->data=y;
                p->next=NULL;
                 S=p;
                }
               else{
                   
                       p=(LinkStack)malloc(sizeof(Lstack));
                scanf("%d",&y);
                p->data=y;
                p->next=S;
                 S=p;
               }
               
            }

                return S;    
}
void DestroyStack_Link(LinkStack S)
{
   LinkStack p=S;
   while(p){
       S=S->next;
       free(p);
       p=S;
}
}
LinkStack Pop_Link(LinkStack S,int * e)
{ 
    LinkStack p=S;
    S=S->next;
   *e=p->data;
    return S;
}
int main()
{
    LinkStack S;
    int n;
    scanf("%d",&n);
    S=Push_Link(S,n);
    StackTraverse_Link(S);
    printf("\n");
    int y;
    y=StackLength_Link(S);
    printf("%d\n",y);
    int r;
    S=Pop_Link(S,&r);
    StackTraverse_Link(S);
    printf("\n");
    printf("%d",r);
    printf("\n");
    y=StackLength_Link(S);
    printf("%d\n",y);
    DestroyStack_Link(S);
    return 0;
}

8.链栈栈顶元素的获取

1.定义获取栈顶元素函数（GetTop_Link）
2.输入要入栈的元素个数n
3.向顺序栈中压入n个元素（Push_Link）
4.将顺序栈中的元素从栈底到栈顶依次输出（StackTraverse_Link）
5.获取栈顶元素
6.输出栈顶元素
7.销毁链栈（DestroyStack_Link）
例如：
4
2 4 6 8
8 6 4 2 //遍历输出时最后一个元素后有一个空格
8

# include<stdio.h>
# include <stdlib.h>
typedef struct Lstack
{
    int data;
    struct Lstack *next;
}Lstack,*LinkStack;
int Init_S(LinkStack S)
{
    S=NULL;
  return 1;  
}
void StackTraverse_Link(LinkStack S)
{ //int i=0;
    LinkStack p=S;
    while(p)
    {
       // i++;
        printf("%d ",p->data);
        p=p->next;
    }
}
LinkStack Push_Link(LinkStack S,int n)
{               int y;
            LinkStack p;
            for(int i=0;i<n;i++)
            {
                if(i==0)
                {
                p=(LinkStack)malloc(sizeof(Lstack));
                scanf("%d",&y);
                p->data=y;
                p->next=NULL;
                 S=p;
                }
               else{
                   
                   p=(LinkStack)malloc(sizeof(Lstack));
                scanf("%d",&y);
                p->data=y;
                p->next=S;
                 S=p;
               }
               
            }

                return S;    
}
void DestroyStack_Link(LinkStack S)
{
   LinkStack p=S;
   while(p){
       S=S->next;
       free(p);
       p=S;
   }

}
LinkStack GetTop_Link(LinkStack S,int * e)
{ 
    LinkStack p=S;
   *e=p->data;
    return S;
}
int main()
{

    LinkStack S;
    Init_S(S);
    int n;
    scanf("%d",&n);
    S=Push_Link(S,n);
    StackTraverse_Link(S);
    printf("\n");    
    int e;
    GetTop_Link(S,&e);
    printf("%d",e);
    DestroyStack_Link(S);
    
    return 0;
}

二、队列系列基础8道题

1.循环队列的建立

1.定义循环队列的存储结构
2.初始化循环队列为空队列（InitQueue_Sq）
3.输入要入队的元素个数n
4.向循环队列中输入n个元素（EnQueue_Sq）
5.将循环队列中的元素从队头至队尾依次输出（StackQueue_Sq）
6.销毁循环队列（DestroyQueue_Sq）
例如：
5
1 2 3 4 5
1 2 3 4 5 //遍历输出时最后一个元素后有一个空格

/*1.定义循环队列的存储结构
2.初始化循环队列为空队列（InitQueue_Sq）
3.输入要入队的元素个数n
4.向循环队列中输入n个元素（EnQueue_Sq）
5.将循环队列中的元素从队头至队尾依次输出（StackQueue_Sq）
6.销毁循环队列（DestroyQueue_Sq）
例如：
5
1 2 3 4 5
1 2 3 4 5  //遍历输出时最后一个元素后有一个空格
*/

# include <stdio.h>
# include <stdlib.h>
# define MAXSIZE 100
 typedef struct Sq{
     int *base;
     int tou;
     int wei;
 }Sq;
 
 int InitQueue_Sq(Sq *sq)
 {
     sq->base=(int *)malloc (sizeof(int)*MAXSIZE);
     sq->tou=sq->wei=0;
     return 1;
 }
 Sq* EnQueue_Sq(Sq *sq,int n)
 {
 
     if((sq->wei+1)%MAXSIZE==sq->tou)
 exit(0);
 //    printf("ffff");
     int e;
     for(int i=0;i<n;i++)
     {
         scanf("%d",&e);
         sq->base[sq->wei]=e;
         sq->wei=(sq->wei+1)%MAXSIZE;
     }
     return sq;
 }
 void StackQueue_Sq(Sq *sq)
 {
     while(sq->tou!=sq->wei)
     {
         printf("%d ",sq->base[sq->tou]);
         sq->tou=(sq->tou+1)%MAXSIZE;
 }}
 void DestroyQueue_Sq(Sq *sq)
 {
 if (sq->base)

free(sq->base);

sq->base = NULL;

sq->tou = sq->wei = 0;
//printf("ppp");
 }
 int main()
 {
     Sq sq;
     InitQueue_Sq(&sq);
     int n;
     scanf("%d",&n);
     
     EnQueue_Sq(&sq,n);
     StackQueue_Sq(&sq);
     DestroyQueue_Sq(&sq); 
     return 0;
 }

2.循环队列的入队

1.定义循环队列入队函数（EnQueue_Sq）
2.输入要入队的元素个数n
3.向循环队列中输入n个元素
4.将循环队列中的元素从队头至队尾依次输出（StackQueue_Sq）
5.销毁循环队列（DestroyQueue_Sq）
例如：
5
6 2 8 10 9
6 2 8 10 9 //遍历输出时最后一个元素后有一个空格

/*1.定义循环队列入队函数（EnQueue_Sq）
2.输入要入队的元素个数n
3.向循环队列中输入n个元素
4.将循环队列中的元素从队头至队尾依次输出（StackQueue_Sq）
5.销毁循环队列（DestroyQueue_Sq）
例如：
5
6 2 8 10 9
6 2 8 10 9  //遍历输出时最后一个元素后有一个空格
*/
# include <stdio.h>
# include <stdlib.h>
# define MAXSIZE   100
typedef struct SQQ{
    int *base;
    int tou;
    int wei;
}SQQ;
int Init_sqq(SQQ*sqq)
{
    sqq->base=(int *)malloc (sizeof(int)*MAXSIZE);
    sqq->tou=sqq->wei=0;
    return 1;
}
SQQ* EnQueue_Sq(SQQ *sqq,int n)     
{   
          int y;
              if((sqq->wei+1)%MAXSIZE==sqq->tou)
 exit(0);
         for(int i=0;i<n;i++)
         {
             scanf("%d",&y);
                sqq->base[sqq->wei]=y;
                sqq->wei=(sqq->wei+1)%MAXSIZE;
         }
      return sqq;
}

void StackQueue_Sq(SQQ *sqq)
{
    while(sqq->tou!=sqq->wei)
    {
        printf("%d ",sqq->base[sqq->tou]);
        sqq->tou=(sqq->tou+1)%MAXSIZE;
    }
}

 void  DestroyQueue_Sq(SQQ *sqq)
 {
if(sqq->base)
free(sqq->base);
sqq->base=NULL;
sqq->tou=sqq->wei=0;
 }
int main()
{
    SQQ sqq;
int n;
scanf("%d",&n);
Init_sqq(&sqq);
EnQueue_Sq(&sqq,n);
//printf("pppp");
StackQueue_Sq(&sqq);
    
DestroyQueue_Sq(&sqq);    
    
    
    
    
    
    
    return 0;
}

3.循环队列的出队

1.定义顺序栈出栈函数（Pop_Sq）
2.定义求顺序栈栈长函数（StackLength_Sq）
3.输入要入栈的元素个数n
4.向顺序栈中压入n个元素
5.将顺序栈中的元素从栈顶到栈底依次输出（StackTraverse_Sq）
6.销毁顺序栈（DestroyStack_Sq）
例如：
4
2 4 6 8
8 6 4 2 //遍历输出时最后一个元素后有一个空格
4
6 4 2 //遍历输出时最后一个元素后有一个空格
8
3

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int SElemType;
#define MAXSIZE 100
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack ;

Status InitStack_Sq(SqStack *S)
{
    S->base=(SElemType*) malloc (sizeof(int)*MAXSIZE);
    if(!S->base) exit(OVERFLOW);
    S->top=S->base;
    S->stacksize=MAXSIZE;
    return OK;
}

void DestroyStack_Sq(SqStack *S)
{
    if(S->base) 
    free (S->base);
    S->top=S->base=NULL;
}

//此处定义求栈长函数StackLength_Sq
       void StackLength_Sq(SqStack *S)
       {
           
           if(S->top==S->base)
           {
               exit(0);
           }
           int y=S->top-S->base;
           printf("%d ",y);
           
       }

Status Push_Sq(SqStack *S,SElemType e)
{
    if(S->top-S->base==S->stacksize) return ERROR;
    *S->top++=e;
    return OK;
}

//此处定义出栈函数

int Pop_Sq(SqStack* S)
{
            int e;
         S->top--;
        e=*S->top;
//printf("%d    ",e);
        return e;
    
    
}

void StackTraverse_Sq(SqStack *S,int n)
{            int e;
int *p=S->top;

        for(int i=0;i<n;i++)
        {
            S->top--;
            e=*S->top;
            printf("%d ",e);    
        }
S->top=p;        
}
SqStack* yazhan(SqStack *S,int n)
{
    int u;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&u);
           *S->top++=u;  
    }
    return S;
}
int main()
{
    SqStack S;
    SElemType e;
    InitStack_Sq(&S);
    int n;
        //SElemType y;
        scanf("%d",&n);
        yazhan(&S,n);
        StackTraverse_Sq(&S,n);
         printf("\n");
        StackLength_Sq(&S);
        printf("\n");
    
         e=Pop_Sq(&S);
         StackTraverse_Sq(&S,S.top-S.base);
         printf("\n");
         printf("%d",e);
             printf("\n");
          StackLength_Sq(&S);
         return 0;
}

4.循环队列队头元素的获取

1.定义获取循环队列队头元素函数（GetHead_Sq）
2.输入要入队的元素个数n
3.向循环队列中输入n个元素
4.将循环队列中的元素从队头至队尾依次输出
5.获取栈顶元素
6.将循环队列中的元素从队头至队尾依次输出
7.销毁循环队列
例如：
5
2 4 6 8 10
2 4 6 8 10 //遍历输出时最后一个元素后有一个空格
2

/*1.定义获取循环队列队头元素函数（GetHead_Sq）
2.输入要入队的元素个数n
3.向循环队列中输入n个元素
4.将循环队列中的元素从队头至队尾依次输出
5.获取栈顶元素
6.将循环队列中的元素从队头至队尾依次输出
7.销毁循环队列
例如：
5
2 4 6 8 10
2 4 6 8 10  //遍历输出时最后一个元素后有一个空格
2*/

# include <stdio.h>
# include <stdlib.h>
# define MAXSIZE 100
 typedef struct SQQ{
     int *base;
     int tou;
     int wei;
 }SQQ;
int Init_sq(SQQ *sqq)
{
    sqq->base=(int *)malloc (sizeof(int)*MAXSIZE);
    sqq->tou=sqq->wei=0;    
    return 1;
}
SQQ*shuru(SQQ*sqq,int n)
{int y;
for(int i=0;i<n;i++)
{
        scanf("%d",&y);
    sqq->base[sqq->wei]=y;
    sqq->wei=(sqq->wei+1)%MAXSIZE;
}
    return sqq;
}
void shuchu(SQQ *sqq)
{

    int q=sqq->tou;
    while(sqq->tou!=sqq->wei)
    {
        
        printf("%d ",sqq->base[sqq->tou]);
        sqq->tou=(sqq->tou+1)%MAXSIZE;
    }
    sqq->tou=q;
}
int  GetHead_Sq(SQQ *sqq)
{
    return sqq->base[sqq->tou];
}
void DestroyQueue_Sq(SQQ *sqq)
{
    if(sqq->base)
    free(sqq->base);
    sqq->base=NULL;
    sqq->tou=sqq->wei=0;
    
    
}
int main()
{
    SQQ sqq; 
    int n;
    scanf("%d",&n);
    Init_sq(&sqq);
    shuru(&sqq,n);
    shuchu(&sqq);
    int y;
    y=GetHead_Sq(&sqq);
    printf("\n");
    printf("%d",y);
    DestroyQueue_Sq(&sqq);
    return 0;
}

5.链队列的建立

1.定义链队列的存储结构
2.初始化链队列为空队列（InitQueue_Link）
3.输入要入队的元素个数n
4.向链队列中输入n个元素（EnQueue_Link）
5.将链队列中的元素从队头至队尾依次输出（StackQueue_Link）
6.销毁链队列（DestroyQueue_Link）
例如：
5
1 2 3 4 5
1 2 3 4 5 //遍历输出时最后一个元素后有一个空格


# include <stdio.h>
# include <stdlib.h>
typedef struct QNode
{
    int data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
  int  InitQueue_Link(LinkQueue*Q){    
    Q->front=Q->rear=(QueuePtr) malloc (sizeof(QNode));
    Q->front->next=NULL;
      return 1;
  }
LinkQueue * EnQueue_Link(LinkQueue*Q,int n)
 { 
    QueuePtr p;
    int y;
     for(int i=0;i<n;i++)
     {
         if(i==0)
         {
                 p=(QueuePtr)malloc(sizeof(QNode));
         scanf("%d",&y);
         p->data=y;
         p->next=NULL;
         Q->front=Q->rear=p;
          }
          else{
        p=(QueuePtr)malloc(sizeof(QNode));
         scanf("%d",&y);
         p->data=y;
         p->next=NULL;
         Q->rear->next=p;
    //    
    Q->rear=p;
         Q->rear=p;
              
          } 
    
     }
     
     return     Q;
 }
void StackQueue_Link(LinkQueue Q)
{
QueuePtr q=Q.front;//结构体类型
//printf("iiiiiii");
    while(Q.front!=NULL)
    {
        printf("%d ",Q.front->data);
        Q.front=Q.front->next;
        q=Q.front;
     } 
     Q.front=q;
 } 
 void DestroyQueue_Link(LinkQueue *sq)
 {
 QueuePtr q;//  节点指针类型 
     while(sq->front!=NULL)
     {
         q=sq->front;
         free(q);
         sq->front=sq->rear->next; 
     }
 //    printf("iii");
 }
 
 
 //front   rear  是单独开辟一个空间 指向   不在链表中 
int main()
{    LinkQueue sq;
    int n;
    scanf("%d",&n); 
    EnQueue_Link(&sq,n);
//printf("ooo");
    StackQueue_Link(sq);
    DestroyQueue_Link(&sq);
    return 0;
}

6.链队列的入队

1.定义循环队列入队函数（EnQueue_Sq）
2.输入要入队的元素个数n
3.向循环队列中输入n个元素
4.将循环队列中的元素从队头至队尾依次输出（StackQueue_Sq）
5.销毁循环队列（DestroyQueue_Sq）
例如：
5
6 2 8 10 9
6 2 8 10 9 //遍历输出时最后一个元素后有一个空格


# include <stdio.h>
# include <stdlib.h>
# define MAXSIZE   100
typedef struct SQQ{
    int *base;
    int tou;
    int wei;
}SQQ;
int Init_sqq(SQQ*sqq)
{
    sqq->base=(int *)malloc (sizeof(int)*MAXSIZE);
    sqq->tou=sqq->wei=0;
    return 1;
}
SQQ* EnQueue_Sq(SQQ *sqq,int n)     
{   
          int y;
              if((sqq->wei+1)%MAXSIZE==sqq->tou)
 exit(0);
         for(int i=0;i<n;i++)
         {
             scanf("%d",&y);
                sqq->base[sqq->wei]=y;
                sqq->wei=(sqq->wei+1)%MAXSIZE;
         }
      return sqq;
}

void StackQueue_Sq(SQQ *sqq)
{
    while(sqq->tou!=sqq->wei)
    {
        printf("%d ",sqq->base[sqq->tou]);
        sqq->tou=(sqq->tou+1)%MAXSIZE;
    }
}

 void  DestroyQueue_Sq(SQQ *sqq)
 {
if(sqq->base)
free(sqq->base);
sqq->base=NULL;
sqq->tou=sqq->wei=0;
 }
int main()
{
    SQQ sqq;
int n;
scanf("%d",&n);
Init_sqq(&sqq);
EnQueue_Sq(&sqq,n);
//printf("pppp");
StackQueue_Sq(&sqq);
    
DestroyQueue_Sq(&sqq);    
    
    
    
    
    
    
    return 0;
}

7.链队列的出队

1.定义求链队列队长函数（QueueLength_Link）
2.定义链队列的出队函数（DeQueue_Link）
3.输入要入队的元素个数n
4.向链队列中输入n个元素
5.将链队列中的元素从队头至队尾依次输出（StackQueue_Link）
6.输出队长
7.执行出队操作
8.将链队列中的元素从队头至队尾依次输出
9.输出出队元素
10.输出队长
11.销毁链队列（DestroyQueue_Link）
例如：
5
1 2 3 4 5
1 2 3 4 5 //遍历输出时最后一个元素后有一个空格
5
2 3 4 5 //遍历输出时最后一个元素后有一个空格
1
4


# include <stdio.h>
# include <stdlib.h>
typedef struct QNode{
    int data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct LinkQueue
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
int InitQueue_Link(LinkQueue *Q)
{
    Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    Q->front=NULL;
    return 1;
}
LinkQueue* EnQueue_Link(LinkQueue *Q,int n)
            {
                QueuePtr p;
                for(int i=0;i<n;i++)
                {
                    p=(QueuePtr) malloc(sizeof(QNode));
                    scanf("%d",&p->data);
                    p->next=NULL;
                    if(i==0)
                    {
                        Q->front=Q->rear=p;
                    }
                    else
                    {
                        Q->rear->next=p;
                        Q->rear=p;
                    }
                }
                
                return Q;
            }
void StackQueue_Link(LinkQueue *Q)
{
    QueuePtr p=Q->front;
    while(Q->front!=NULL)
    {
        printf("%d ",Q->front->data);
        Q->front=Q->front->next;
    }
    Q->front=p;
        }        
int QueueLength_Link(LinkQueue *Q)
{ 
    int y=0;
    QueuePtr p=Q->front;
    while(Q->front!=NULL)
    {
        y++;
        Q->front=Q->front->next;
    }
    Q->front=p;
    return y;
}
 int  DeQueue_Link(LinkQueue *Q){
         int y;
     y=Q->front->data;
     Q->front=Q->front->next;
     return y ;
 }
 void DestroyQueue_Link(LinkQueue *Q)
 {
     QueuePtr p;
     while(Q->front!=NULL){
         
         p=Q->front;
         Q->front=Q->front->next;
         free(p);
     }
     
  } 
int main()
{
    int n;
    scanf("%d",&n);
    int y;
    LinkQueue Q;
    InitQueue_Link(&Q);
    EnQueue_Link(&Q,n);
    StackQueue_Link(&Q);
    printf("\n");
    int x;
    x=QueueLength_Link(&Q);
    printf("%d ",x);
        printf("\n");
    y=DeQueue_Link(&Q);
    StackQueue_Link(&Q);
        printf("\n");
    printf("%d",y);
        printf("\n");
    x=QueueLength_Link(&Q);
    printf("%d",x);
    DestroyQueue_Link(&Q);
    return 0;
}

8.链队列队头元素的获取

1.定义获取链队列队头元素函数（GetHead_Link）
2.输入要入队的元素个数n
3.向链队列中输入n个元素
4.将链队列中的元素从队头至队尾依次输出
5.获取栈顶元素
6.将链队列中的元素从队头至队尾依次输出
7.销毁链队列
例如：
5
2 4 6 8 10
2 4 6 8 10 //遍历输出时最后一个元素后有一个空格
2

# include <stdio.h>
# include <stdlib.h>
typedef struct  QNode{
    int data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int InitQueue_Link(LinkQueue *Q)
{
    Q->front=Q->rear=(QueuePtr) malloc(sizeof(QNode));
    Q->front=NULL;    
        return 1;
}
LinkQueue* EnQueue_Link(LinkQueue *Q,int n)
{
    QueuePtr p;
    for(int i=0;i<n;i++)
    {
        p=(QueuePtr) malloc(sizeof(QNode));
        scanf("%d",&p->data);
        p->next=NULL;
        if(i==0)
        {
            Q->front=Q->rear=p;
        }
        else
        {
            Q->rear->next=p;
            Q->rear=p;
        }
    
    }
        return Q;
}
void StackQueue_Link(LinkQueue *Q)
{
    QueuePtr p=Q->front;
    while(Q->front!=NULL)
    {
        printf("%d ",Q->front->data);
        Q->front=Q->front->next;
    }
    Q->front=p;
}
int GetHead_Link(LinkQueue *Q){
    int y;
    y=Q->front->data;
    printf("%d ",y);
    return 1;
}
void DestroyQueue_Link(LinkQueue *Q)
{
    QueuePtr p;
    while(Q->front!=NULL)
    {
        p=Q->front;
        Q->front=Q->front->next;
        free(p);
    }
//    printf("成功调用"); 
}
int main()
{
    int n;
    scanf("%d",&n);
    LinkQueue Q;
    InitQueue_Link(&Q);
    EnQueue_Link(&Q,n);
    StackQueue_Link(&Q);
    printf("\n");
    GetHead_Link(&Q);
    DestroyQueue_Link(&Q);
    return 0;
}

三、栈与队列的应用

1.栈的应用

将十进制数n，转换成八进制。
例如：
10
12

# include <stdio.h>
# include <stdlib.h>
# define MAXSIZE 100
typedef struct {
    int *base;
    int *top;
    int stacksize;
}SqStack;
int InitStack_Sq(SqStack *S)
{
    S->base=(int*)malloc (sizeof(int)*MAXSIZE);
    if(!S->base) exit(-1);
    S->top=S->base;
    S->stacksize=MAXSIZE;
    return 1;
}
SqStack*  Push_Sq(SqStack * S,int x)
{

     *S->top=x;
      S->top++;
       return S; 
}
void StackTraverse_Sq(SqStack *S)
{
     while(S->top!=S->base)
    {
        S->top--;
        printf("%d",*S->top);
    }
}
    int main()
    {
        SqStack S;
        InitStack_Sq(&S); 
        int n;
        scanf("%d",&n);
        int m=1;
        while(m!=0)
        {    //printf("进入while");
            int x=0;
            x=n%8;
            Push_Sq(&S,x);
            //printf("push结束"); 
            m=n/8;
            n=m;
        }
        StackTraverse_Sq(&S);
        return 0;
    }

2.队列的应用

有n个人围成一圈，从第1个人开始，1，2，…，m报数，报至m出局，余下的人继续从1，2，…，m报数，重复之前的流程，要求：求出被淘汰编号的序列，及最后剩下的一人是原来的第几号？
例如：
10
3
3 6 9 2 7 1 8 5 10
4


# include <stdio.h>
# include <stdlib.h>
# define MAXSIZE 100
typedef struct {
    int  *base ;
    int front;
    int rear;
} SqQueue;
int  InitQueue(SqQueue *Q){
    
    Q->base=(int *)malloc (sizeof(int)*MAXSIZE);
    Q->front=Q->rear=0;
    return 1;
}
SqQueue *   EnQueue(SqQueue *Q,int n)
{
    //判断队满 
    if(Q->front==(Q->rear+1)%MAXSIZE)
    {
    exit(0);
     } 
    for(int i=0;i<n;i++)
    {
    Q->base[Q->rear]=i+1;
    Q->rear=(Q->rear+1)%MAXSIZE;
    }
    
    return Q;
 }
 int taotai(SqQueue *Q,int n,int m)
 {        int f=0;
         int a[n];
         int i=0;
    for( i=0;i<n;i++)
    {
        a[i]=1;
    }
     int t=n;
     while(t!=1)
     {
         if(a[i]==1)
         {
             f++;
         }
         if(f==m)
         {    f=0;
             a[i]=0;
             t--;
             printf("%d ",i+1);
         }
         if(i<n)
         {
             i++;
         }
         else
         {
             i=0;
         }
     }
      for(i=0;i<n;i++)
    {
        if(a[i]==1)
    {
        printf("\n");
        printf("%d",i+1);
    }
        
    }
     return 1;
 }
    
int main()
{
    int n;
       SqQueue Q;
     scanf("%d",&n);
     InitQueue(&Q);
     int m;
     scanf("%d",&m);
     EnQueue(&Q,n);    
     taotai(&Q,n,m);

    return 0;
}
标签： 算法 数据结构
本文转载自: https://blog.csdn.net/m0_61469860/article/details/125072129
版权归原作者 &volume 所有， 如有侵权，请联系我们删除。
登录后发布评论

“数据结构51题之栈和队列18题”的评论:

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

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航