实验二 栈和队列

一、实验目的

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

二、实验内容

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

#include

#include

#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("nnn");

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

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

       printf("nn     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);

        }

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

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

     printf("n               再见！")

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

}

void out_s(SqStack s)

 { char ch; int i;                 

   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();

 }

void push(SqStack *s,ElemType e)

 {

 }

ElemType pop(SqStack *s)

{

 }

1. 运行结果

1. 算法分析

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

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

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

#include

#include

#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("nnn");

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

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

       printf("nn     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);

      }

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

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

     printf("n               再见！");

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

}

void out_Q(SqQueue Q)

 { char ch; int i;                

 

 

 }

/ *  进队函数  */

void EnQueue(SqQueue *Q,ElemType e)

 {  

 } 

ElemType DeQueue(SqQueue *Q)

{

 }

 

1. 算法分析

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

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

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

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

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