栈和队列的基本操作的实现

封面：

安徽大学

网络工程

栈和队列的基本操作的实现

______2010\\4\\12

【实验目的】

1.理解并掌握栈和队列的逻辑结构和存储结构； 2.理解栈和队列的相关基本运算； 3.编程对相关算法进行验证。

【实验内容】

（一）分别在顺序和链式存储结构上实现栈的以下操作（含初始化，入栈，出栈，取栈顶元素等）： 1.构造一个栈S，将构造好的栈输出；

2.在第1步所构造的栈S中将元素e 入栈，并将更新后的栈S输出；

3.在第2步更新后所得到的栈S中将栈顶元素出栈，用变量e返回该元素，并将更新后的栈S输出。 （二）分别在链队列和循环队列上实现以下操作（初始化，入队，出队，取队头元素等）： 1.构造一个队列Q，将构造好的队列输出； 2.在第1步所构造的队列Q中将元素e入队，并将更新后的队列Q输出；

3.在第2步更新后所得到的队列Q中将队头元素出队，用变量e返回该元素，并将更新后的队列Q输出。

【要求】

1.栈和队列中的元素要从终端输入； 2.具体的输入和输出格式不限；

3.算法要具有较好的健壮性，对运行过程中的错误操作要做适当处理。 三、实验步骤

1．本实验用到的数据结构 (1)逻辑结构：线性结构

(2)存储结构：程序一、四（顺序存储结构）；

程序二、三（链式存储结构）；

2．各程序的功能和算法设计思想

程序一：顺序栈

# include # include # include

#define STACKINITISIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0

# define OVERFLOW -2 typedef int SElemtype; typedef int status;

typedef struct { SElemtype *base; SElemtype *top; int stacksize; }sqstack;

void Initstack (sqstack *s) {

(*s).base = (SElemtype *)malloc(STACKINITISIZE * sizeof (SElemtype)); if(!(*s).base) exit(OVERFLOW);

(*s).top = (*s).base;

(*s).stacksize = STACKINITISIZE; }

void push ( sqstack *s , SElemtype e ){

if ((*s).top - (*s).base >=(*s).stacksize){

(*s).base = (SElemtype *) realloc ((*s).base,((*s).stacksize + STACKINCREMENT) * sizeof (SElemtype )); if ( ! (*s).base ) exit (OVERFLOW);

(*s).top = (*s).base +(*s).stacksize ; (*s).stacksize += STACKINCREMENT; }

*(*s).top ++ = e; }

status Gettop (sqstack s ) { int e;

if (s.top ==s.base ) return ERROR;

e=*(s.top-1);

printf (\栈顶元素是%d\\n\return OK; }

status pop ( sqstack *s ) { int f;

if ( (*s).top==(*s).base) return ERROR; f = *(--(*s).top);

printf(\出栈元素是%d\\n\return OK; }

void stackTraverse(sqstack s ){ SElemtype * p =s.base; while (s.top>p)

printf (\ printf(\}

void main(){

int h,k,e,i;

sqstack la; printf (\构建一个空栈\\n\ Initstack (&la); printf(\请输入栈内元素的个数\\n\ scanf (\

printf(\请输入%d个元素\\n\

for (i=0;i

printf (\

push (&la,e);

printf(\输出栈内所有元素\\n\ stackTraverse (la); fflush (stdin);

printf(\查找栈顶元素\\n\ Gettop (la); printf(\删除栈顶元素\\n\ pop (&la); printf(\输出栈内所有元素\\n\ stackTraverse (la);

fflush (stdin); printf (\

printf (\插入一个元素\\n\

printf(\请输入插入的元素值\\n\scanf (\push (&la,h);

printf(\输出栈内所有元素\\n\ stackTraverse (la); printf(\}

功能：实现顺序栈的各种功能，如能建立空栈，实现栈的初始化，插入，删除栈顶元素等操作。

算法设计思想：首先建立一个空栈，再实现栈的初始化，用一个主函数包涵栈的各种操作。 程序调式如下：

本文来源：https://www.bwwdw.com/article/8k1v.html