目录

前言

一、顺序栈的定义

二、顺序栈的c++语言结构描述表示

三、顺序栈中基本操作的实现

3.1顺序栈的初始化 

3.2判断顺序栈是否为空

3.3求顺序栈的长度

3.4清空顺序栈

3.5销毁顺序栈

3.6顺序栈的入栈

3.7顺序栈的出栈

3.8求栈顶元素

3.9遍历顺序栈 

 四、顺序栈的代码实现

五、测试结果

五、总结

---

前言

本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》

---

一、顺序栈的定义

栈：操作受限的线性表，限定仅在表尾进行插入和删除操作的线性表，即后进先出。这一端被称为栈顶，相对地，把另一端称为栈底。

顺序栈：用顺序结构存储的栈

例子：类似子弹压入弹夹，后放入的子弹可以先从弹夹弹出来。

特点：简单方便，但是容易溢出（上溢或者下溢）

二、顺序栈的c++语言结构描述表示

代码如下（示例）：

typedef struct sqstack{
    int *top;//栈顶指针
    int *base;//栈底指针
    int stackSize;//栈的最大容量 
}stack;

三、顺序栈中基本操作的实现

3.1顺序栈的初始化 

数组用c++的new来动态开辟

当内存不够的时候，也即是s.base为空，则直接结束

不为空的时候，则栈的栈顶指针与栈底指针都指向同一位置

代码如下（示例）：

void initStack(stack &s)
{
	s.base=new int[MaxSize];
	if(!s.base)	exit(0);//内存分配失败，结束
	s.top=s.base;//初始的时候栈的top与base相等 
	s.stackSize=MaxSize;//栈的最大容量	
} 

3.2判断顺序栈是否为空

栈顶指针与栈底指针都指向同一位置，即s.base==s.top的时候，则栈为空，返回1

否则，不为空，返回0

 代码如下（示例）：

int isEmpty(stack s)
{
	if(s.base==s.top)
		return 1;//表示为空，无元素
	return 0;//不为空	
} 

3.3求顺序栈的长度

长度即为有多少个元素，可以用s.top-s.base

 代码如下（示例）：

int stackLength(stack s)
{
	return s.top-s.base;
}

3.4清空顺序栈

当s.base不为空的时候，让s.top(栈顶指针)直接指向s.base（栈底）,则把所有的元素逻辑上清空了

而当s.base为空的时候，则栈已经被销毁了，无需清空

 代码如下（示例）：

void CleanStack(stack &s)
{
	if(s.base)
	{
		s.top=s.base;
		cout<<"成功清空"<<endl;
	}
	else
		cout<<"栈已经被销毁，无需清空"<<endl;
}

3.5销毁顺序栈

从物理层次销毁

也即是用delete将整个s.base从内存中删除

 代码如下（示例）：

void DestoryStack(stack &s)
{
	if(s.base)
	{
		delete s.base;
		s.stackSize=0;
		s.base=NULL;
		s.top=NULL;
		cout<<"成功销毁"<<endl;
	}
	else
		cout<<"栈已经被销毁，无需销毁"<<endl;
}

3.6顺序栈的入栈

首先判断栈是否已经满了，如果满了则无法入栈，否则可以入栈

 代码如下（示例）：

void push(stack &s,int e)
{
	if((s.top-s.base)==s.stackSize)
		cout<<"栈满了，无法添加新元素"<<endl;
	else
	{
		*(s.top)=e;
		s.top++;	
		cout<<"添加成功"<<endl;
	}	
} 

3.7顺序栈的出栈

首先判断栈是否为空，如果为空，则无法出栈，否则可以出栈 

  代码如下（示例）：

void pop(stack &s,int &e)
{
	if(isEmpty(s))
	{
		cout<<"栈为空，无法弹出"<<endl;
	}	
	else
	{
		s.top--;
		e=*(s.top);
		cout<<"成功弹出"<<endl; 
	}
} 

3.8求栈顶元素

 先判断栈是否为空，为空则无法求栈顶元素，否则可以求栈顶元素

  代码如下（示例）：

int top(stack s)
{
	if(isEmpty(s))
	{
		cout<<"栈为空，没有栈顶元素"<<endl;
		return -1;
	}
	else
	{
		s.top--;
		return *(s.top);
	}
}

3.9遍历顺序栈 

从栈底开始遍历 

  代码如下（示例）：

void traverse(stack s)
{
	int length=stackLength(s);
	
	if(length>0)
	{
		cout<<"顺序栈的元素为:(从栈底开始遍历)"<<endl;
		for(int i=0;i<length;i++)
			cout<<s.base[i]<<" ";
	}	
	else
		cout<<"顺序栈为空"<<endl;
} 

 四、顺序栈的代码实现

#include <iostream>
using namespace std;
const int MaxSize=100;
typedef struct sqstack{
	int *top;//栈顶指针
	int *base;//栈底指针
	int stackSize;//栈的最大容量 
}stack;
void initStack(stack &s)
{
	s.base=new int[MaxSize];
	if(!s.base)	exit(0);//内存分配失败，结束
	s.top=s.base;//初始的时候栈的top与base相等 
	s.stackSize=MaxSize;//栈的最大容量	
} 
int isEmpty(stack s)
{
	if(s.base==s.top)
		return 1;//表示为空，无元素
	return 0;//不为空	
} 
int stackLength(stack s)
{
	return s.top-s.base;
}
void CleanStack(stack &s)
{
	if(s.base)
	{
		s.top=s.base;
		cout<<"成功清空"<<endl;
	}
	else
		cout<<"栈已经被销毁，无需清空"<<endl;
}
void DestoryStack(stack &s)
{
	if(s.base)
	{
		delete s.base;
		s.stackSize=0;
		s.base=NULL;
		s.top=NULL;
		cout<<"成功销毁"<<endl;
	}
	else
		cout<<"栈已经被销毁，无需销毁"<<endl;
}
//入栈
void push(stack &s,int e)
{
	if((s.top-s.base)==s.stackSize)
		cout<<"栈满了，无法添加新元素"<<endl;
	else
	{
		*(s.top)=e;
		s.top++;	
		cout<<"添加成功"<<endl;
	}	
} 
//出栈
void pop(stack &s,int &e)
{
	if(isEmpty(s))
	{
		cout<<"栈为空，无法弹出"<<endl;
	}	
	else
	{
		s.top--;
		e=*(s.top);
		cout<<"成功弹出"<<endl; 
	}
} 
int top(stack s)
{
	if(isEmpty(s))
	{
		cout<<"栈为空，没有栈顶元素"<<endl;
		return -1;
	}
	else
	{
		s.top--;
		return *(s.top);
	}
}
void traverse(stack s)
{
	int length=stackLength(s);
	
	if(length>0)
	{
		cout<<"顺序栈的元素为:(从栈底开始遍历)"<<endl;
		for(int i=0;i<length;i++)
			cout<<s.base[i]<<" ";
	}	
	else
		cout<<"顺序栈为空"<<endl;
} 
void menu()
{
	cout<<"**********************************"<<endl;
	cout<<"1.初始化"<<endl;
	cout<<"2.判断栈是否为空"<<endl;
	cout<<"3.求栈的长度"<<endl;
	cout<<"4.清空栈"<<endl;
	cout<<"5.销毁栈"<<endl;
	cout<<"6.入栈"<<endl;
	cout<<"7.出栈"<<endl;
	cout<<"8.求栈顶元素"<<endl;
	cout<<"9.遍历顺序栈"<<endl;
	cout<<"10.退出"<<endl;
	cout<<"**********************************"<<endl;
}
int main()
{
	int choice;
	stack s;
	int e1,e2;
	while(1)
	{
		menu();
		cin>>choice;
		switch(choice)
		{
			case 1:
				initStack(s);
				cout<<"初始化成功"<<endl;
				break;
			case 2:
				if(isEmpty(s))
					cout<<"栈为空"<<endl;
				else
					cout<<"栈不为空"<<endl; 
				break;
			case 3:
				cout<<"栈的长度为"<<stackLength(s)<<endl;
				break;
			case 4:
				CleanStack(s);
				break;
			case 5:
				DestoryStack(s);
				break;	
			case 6:
				cout<<"请输入想要入栈的元素值："<<endl;
				cin>>e1;
				push(s,e1);
				break;
			case 7:
				pop(s,e2);
				cout<<"弹出的元素为"<<e2<<endl;
				break;
			case 8:
				if(top(s)!=-1)
					cout<<"栈顶元素为"<<top(s)<<endl;
				break;
			case 9:
				traverse(s);
				cout<<endl;
				break;
			case 10:
				cout<<"成功退出"<<endl;
				exit(0);
			default:
				cout<<"输入有误，请重新输入"<<endl;
				break;			
		}	
	}
} 

五、测试结果

                                          图一

                                        图二 

                                        图三

 

                                        图四 

 

                                         图五

                                         图六

                                         图七

                                          图八

                                           图九

                                            图十

                                             图十一

六、总结

        栈是一种操作受限的线性表，虽然操作受限，但是与线性表有点类似，只不过栈的插入和删除都在表尾而已。而我在本文中实现的顺序栈有点类似顺序表。我们也需要注意到顺序栈虽然实现简单，但是其容易发生溢出，在栈满的时候，还要入栈，则会上溢，而在栈空的时候，还要出栈，则会下溢，针对这个问题，我将在下一篇文章的链栈解决这个问题。