栈是一种先进后出、后进先出的线性序列。
实现了顺序栈的创建和初始化,并实现了栈的入栈、出栈、取栈顶、遍历操作。
1、定义顺序栈的结构体
? ? 栈的结构体有两个成员变量,一个是栈顶指针,指向栈顶元素的上一个位置;一个是栈底指针,指向栈的底部。
struct Stack
{
int* base; //栈底指针
int* top; //栈顶指针
};
2、顺序栈初始化
? ? 给顺序栈分配一段内存空间,内存空间的容量即为栈的容量,动态分配返回的空间基地址作为栈底指针;? ? ? ? ? ? ? ? ?
? ? 初始时,栈顶指针等于栈底指针。
const int max_size = 1000;
//初始化
bool InitStack(Stack& s)
{
s.base = new int[max_size]; //在内存上给栈分配一段空间
if (!s.base)
{
return false;
}
s.top = s.base; //初始时栈顶指针和栈底指针相同
return true;
}
3、入栈操作
? ? 分两步进行:首先,将入栈元素放到栈顶指针指向的位置;然后,将栈顶指针上移一位。
? ? 注意:在入栈之前要判断栈是否已满。
//入栈
void Push(Stack& s)
{
int elem;
cout << "请输入入栈元素" << endl;
cin >> elem;
if (s.top - s.base == max_size) //栈已满
{
cout << "栈已满" << endl;
}
*s.top = elem; //压入元素
s.top++; //栈顶指针上移,此时栈顶指针空指
}
4、出栈操作?
? ? 分两步进行:首先,将栈顶指针下移一位,使其指向真正的栈顶元素;然后,将栈顶元素取走。
//出栈
void Pop(Stack& s)
{
int elem;
if (s.top == s.base)
{
cout << "栈已空" << endl;
}
s.top--; //栈顶指针下移,此时栈顶指针指向真正栈顶元素
elem = *s.top; //取出元素
cout << "出栈元素为:" << elem << endl;
}
5、取栈顶元素
? ? 不需要移动栈顶指针,只取走栈顶指针前一个位置的元素即可
//取栈顶
void GetTop(const Stack& s)
{
if (s.top == s.base)
{
cout << "栈已空" << endl;
}
int elem = *(s.top - 1); //真正的栈顶元素是top-1位置上的元素
cout << "栈顶元素为:" << elem << endl;
}
6、遍历打印顺序栈
? ? 定义一个指针变量,从栈底指针开始,遍历到栈顶指针的前一个位置,打印变量指向的元素。
//遍历打印
void Print(const Stack& s)
{
for (auto i = s.base; i < s.top; i++)
{
cout << *i << " ";
}
cout << endl;
}
整体代码:
#include <iostream>
using namespace std;
#define max_size 100
struct Stack
{
int* base; //栈底指针
int* top; //栈顶指针
};
//初始化
bool InitStack(Stack& s)
{
s.base = new int[max_size]; //在内存上给栈分配一段空间
if (!s.base)
{
return false;
}
s.top = s.base; //初始时栈顶指针和栈底指针相同
return true;
}
//栈中的元素包括s.base到s.top-1位置上的所有元素
//入栈
void Push(Stack& s)
{
int elem;
cout << "请输入入栈元素" << endl;
cin >> elem;
if (s.top - s.base == max_size) //栈已满
{
cout << "栈已满" << endl;
}
*s.top = elem; //压入元素
s.top++; //栈顶指针上移,此时栈顶指针空指
}
//出栈
void Pop(Stack& s)
{
int elem;
if (s.top == s.base)
{
cout << "栈已空" << endl;
}
s.top--; //栈顶指针下移,此时栈顶指针指向真正栈顶元素
elem = *s.top; //取出元素
cout << "出栈元素为:" << elem << endl;
}
//取栈顶
void GetTop(const Stack& s)
{
if (s.top == s.base)
{
cout << "栈已空" << endl;
}
int elem = *(s.top - 1); //真正的栈顶元素是top-1位置上的元素
cout << "栈顶元素为:" << elem << endl;
}
//遍历打印
void Print(const Stack& s)
{
for (auto i = s.base; i < s.top; i++)
{
cout << *i << " ";
}
cout << endl;
}
int main()
{
int choose = 0;
Stack s;
if (!InitStack(s))
{
cout << "初始化失败" << endl;
}
cout << "1、入栈" << endl;
cout << "2、出栈" << endl;
cout << "3、取栈顶" << endl;
cout << "4、遍历" << endl;
cout << "9、退出" << endl;
while (choose != 9)
{
cout << "请输入要做的操作" << endl;
cin >> choose;
switch (choose)
{
case 1:
Push(s);
break;
case 2:
Pop(s);
break;
case 3:
GetTop(s);
break;
case 4:
Print(s);
break;
delegate:
break;
}
}
return 0;
}
cs