实验二 栈和队列

一、实验目的

1. 掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。
2. 掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。  
3. 了解和掌握递归程序设计的基本原理和方法。

二、实验内容

1. 栈的顺序存储结构及实现。

#include <stdio.h>

#include <stdlib.h>

#define MAXSIZE 20                       /* 数组最大界限 */

typedef int ElemType;                    /* 数据元素类型 */

typedef  struct

   { ElemType  a[MAXSIZE];               /* 一维数组子域 */

     int  top;                        /* 栈顶指针子域    */

   }SqStack;                     /* 栈的顺序结构体类型 */

SqStack  s1;

/*  函数声明  */

void init_s(SqStack *s);

void out_s(SqStack s);

void push(SqStack *s,ElemType e);

ElemType pop(SqStack *s);

/*  主函数  */

main()

{ int k;  ElemType e,x; char ch;

  init_s( &s1);          /* 初始化一个空栈 */

  do { printf("\n\n\n");

       printf("\n\n     1. 数据元素e进栈 ");

       printf("\n\n     2. 出栈一个元素，返回其值")；

       printf("\n\n     3. 结束程序运行");

       printf("\n======================================");

       printf("\n     请输入您的选择 (1,2,3)");

       scanf("%d",&k);

       switch(k)

         { case 1:{ printf("\n 进栈 e=?"); scanf("%d",&e);

                      push( &s1,e); out_s( s1 );

                   } break;

           case 2:{   x= pop( &s1);

                      printf("\n出栈元素 : %d", x);

                     out_s( s1 );

                  } break;

           case 3: exit(0);

        } /*  switch  */

      printf("\n ----------------");

    }while(k>=1 && k<3);

     printf("\n               再见！")

     printf(“\n        打回车键，返回。“); ch=getch();

} /* main */

/*  初始化空栈  * /

void init_s(SqStack *s)

 { s->top=-1;

 } /*  init_s */

/*  输出栈的内容  */

void out_s(SqStack s)

 { char ch; int i;                  /*  千万不能修改栈顶指针top */

   if (s->top==-1) printf(“\n Stack is NULL. “);

   else{ i=s->top;

         while( i!=-1){ printf(“\n data=%d”, s->a[i]);

                       i--; }

       }

   printf(“\n 打回车键，继续。“); ch=getch();

 } /* out_c */

/*  进栈函数  */

void push(SqStack *s,ElemType e)

 {

 }/*  push  */

/*  出栈函数 */

ElemType pop(SqStack *s)

{

 } /* pop  */

1. 运行结果

1. 算法分析

1.创建一个空栈，定义栈的大小 size，以及栈顶元素指针 top

1. 判断栈是否为空：当堆栈为空时，返回。当堆栈不为空时，再见 。
2. 判断栈是否已满：当堆栈已满时返回，当堆栈未满时，返回 Null。
3. 入栈：在线性表最后元素后面插入一个新的数据元素。并改变栈顶指针top 的指向位置
4. 出栈：在线性表最后元素后面删除最后一个数据元素。并改变栈顶指针top 的指向位置
5. 获取栈顶元素：相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是，该操并不改变栈顶指针 top 的指向位置

循环队列（即队列的顺序存储结构）实现。

#include <stdio.h>

#include <stdlib.h>

#define MAXSIZE 20                       /* 数组最大界限 */

typedef int ElemType;                    /* 数据元素类型 */

typedef  struct

   { ElemType  a[MAXSIZE];               /* 一维数组子域 */

     int  front,rear;                 /* 头、尾指针子域  */

   }SqQueue;                     /* 循环队列的结构体类型 */

SqQueue  Q1;

/*  函数声明  */

void init_Q(SqQueue *Q);

void out_Q(SqQueue Q);

void EnQueue(SqQueue *Q,ElemType e);

ElemType DeQueue(SqQueue *Q);

/*  主函数  */

main()

{ int k; ElemType e,x; char ch;

  init_Q( &Q1);          /* 初始化一个空循环队列 */

  do { printf("\n\n\n");

       printf("\n\n     1. 数据元素e进队列 ");

       printf("\n\n     2. 出队一个元素，返回其值")；

       printf("\n\n     3. 结束程序运行");

       printf("\n======================================");

       printf("\n     请输入您的选择 (1,2,3)");

       scanf("%d",&k);

       switch(k)

     { case 1:{ printf("\n 进队 e=?"); scanf("%d",&e);

                      EnQueue(SqQueue &Q1,e); out_Q(Q1);

          } break;

       case 2:{ x= DeQueue(&Q1);

                      printf("\n出队元素 : %d", x);

          out_Q(Q1 );

 out_Q(Q1 );

         } break;

       case 3: exit(0);

      } /*  switch  */

      printf("\n ----------------");

       }while(k>=1 && k<3);

     printf("\n               再见！");

     printf(“\n        打回车键，返回。“); ch=getch();

} /* main */

/*  初始化空队列  * /

void init_Q(SqQueue *Q)

 { Q->front=0;   Q->rear=0;

 } /*  init_Q */

/*  输出队列的内容  */

void out_Q(SqQueue Q)

 { char ch; int i;                

 /*  不能修改队列头、尾指针 */

 

 } /* out_Q */

/ *  进队函数  */

void EnQueue(SqQueue *Q,ElemType e)

 {  

 }/*  EnQueue  */ 

/*  出队函数 */

ElemType DeQueue(SqQueue *Q)

{

 } /* DeQueue  */

 

1. 算法分析

1. 初始化一个空循环队列 。

2. 从队⾸获取元素。如果队列为空，返回，队列满则出错 。

3. 获取队尾元素。如果队列为空，返回，队列满则出错 。

4. 向循环队列插⼊⼀个元素。如果成功插⼊则返回。

5. 从循环队列中删除⼀个元素。如果成功删除则返回。