数据结构|顺序栈的实现（实验3.1）

野性酷女 2022-06-07 10:23 117阅读 0赞

# 一、实验目的 #

1、熟练掌栈的结构特点，掌握栈的顺序存储结构和实现。

2、学会使用栈解决实际问题。

**二、实验内容**

1、自己确定结点的具体数据类型和问题规模，建立一个顺序栈，实现栈的压栈和出栈操作。

三、实验步骤

1、依据实验内容分别说明实验程序中用到的数据类型的定义；

template < typename T >
    class SeqStack{
    	public:
    		SeqStack() {top = -1;}  //构造函数，初始化一个空栈
    		~SeqStack() {}   //析构函数为空
    		void push(T x);   //入栈操作，将元素x入栈
    		T pop();      //出栈操作，将栈顶元素弹出
    		T get() { if(top!=-1) return data[top]; }  //取栈顶元素（不删除）
    		bool Empty() { return top == - 1 ? true : false; }  //判断栈是否为空
    		bool Full()  { return top == StackSize - 1 ? true : false; }  //判断是否栈满
    		void print();  //遍历操作
    	private:  
    		T data[StackSize];  //存放栈元素的数组
    		int top;   //栈顶指针，为栈顶元素在数组中的下标
    };

2、相关操作的算法表达；

2.1、构造函数，初始化一个空栈

2.2、入栈操作函数：①.判断是否栈满，若是则返回，否则   
              ②.先栈顶指针 top 往上移一位，再在该位存储数据

2.3、出栈操作函数：①判断是否栈空，若是则返回 -1，否则   
              ②先返回栈顶指针 top 指向的位置的值，再把栈顶指针 top 往下移一位

2.4、输出操作函数：按照顺序，输出栈元素。

3、完整程序；

由于结点元素类型不确定，因此采用C++模板机制。

源代码如下：

#include<iostream>
    using namespace std;
    
    const int StackSize = 10 ;
    
    template < typename T >
    class SeqStack{
    	public:
    		SeqStack() {top = -1;}  //构造函数，初始化一个空栈
    		~SeqStack() {}   //析构函数为空
    		void push(T x);   //入栈操作，将元素x入栈
    		T pop();      //出栈操作，将栈顶元素弹出
    		T get() { if(top!=-1) return data[top]; }  //取栈顶元素（不删除）
    		bool Empty() { return top == - 1 ? true : false; }  //判断栈是否为空
    		bool Full()  { return top == StackSize - 1 ? true : false; }  //判断是否栈满
    		void print();  //遍历操作
    	private:  
    		T data[StackSize];  //存放栈元素的数组
    		int top;   //栈顶指针，为栈顶元素在数组中的下标
    };
    
    template< typename T >
    void SeqStack<T>::push(T x)
    {
    	if(Full()){              //判断是否栈满入栈： 
            cout<<"栈满！"<<endl;  
            return;  
        }
    	data[++top] = x; cout<<"入栈"<<x<<"成功！"<<endl;
    }
    
    template< typename T >
    T SeqStack<T>::pop()
    {
    	T x;
    	if(Empty()){             //判断是否栈空出栈
     * 1.判断是否栈空，若是则返回 -1，否则 
     * 2.先返回栈顶指针 top 指向的位置的值，再把栈顶指针 top 往下移一位
            cout<<"栈空！"<<endl;  
            return -1;  
        }
    	x = data[top--];
    	return x;
    }
    
    template< typename T >
    void SeqStack<T>::print()
    {
    	for( int i=0 ; i<=top ; i++)
    	{  cout<<data[i]<<" ";}
    	cout<<endl;
    }
    
    void main()
    {
    	SeqStack<int>a;
    	cout<<"按顺序把“1，2，3，4，5”推进栈"<<endl;
    	for(int i=1;i<=5;i++) {  a.push(i);  }
    	cout<<"结果如下："<<endl;
    	a.print();
    	cout<<"出栈一个元素"<<a.pop()<<"结果如下："<<endl;
    	a.print();
    	cout<<"现在栈顶元素为："<<a.get()<<endl;
    }

4、总结、运行结果和分析。

①总结

在程序内定义对象为int型，将元素1~5按顺序入栈。

通过调用成员函数，实现入栈、出栈、输出等基本功能。

②运行结果如下:

![Center][]

5、总体收获和不足，疑问等。

本次试验较为简单，因为实验内容较少，且对书本知识掌握得有点熟悉。但本次试验还是发现了自己的不足之处。经过改进、询问同学，成功完成了实验。收获颇丰。总的来说，我对理论知识有了更充分的理解，也能较大程度明白运行原理。

[Center]: /images/20220607/a3e91a7c59ec4d3d9e975c4ee650cae4.png