总目录
- 1.基本操作
- 1.1 结构体定义
- 1.2 初始化
- 1.3 判空
- 1.4 入栈
- 1.5 出栈
- 1.6 取栈顶元素
- 1.7 弹出并输出栈中所有元素
- 2.完整代码
- 3.运行截图
各部分的解释已经以注释形式写于代码中。 1.基本操作 1.1 结构体定义
typedef struct { // 定义顺序栈
int data[MaxSize]; // 静态数组存放栈中元素
int top; // 栈顶指针：指向目前栈顶元素的位置
} SeqStack;
1.2 初始化
// 初始化
void InitStack(SeqStack &S) {
// 初始化栈顶指针，由于在顺序栈中，0表示栈底部的位置
// 所以初始应赋小于0的值，常用-1
S.top = -1;
}
1.3 判空
// 判断栈空
bool StackEmpty(SeqStack S) {
// 空栈条件：栈顶指针等于-1！！！
// 说明栈中没有任何元素
if(S.top == -1) {
return true;
} else {
return false;
}
}
1.4 入栈
// 进栈操作
// 类似于线性表的插入操作，即“增”操作
// 但由于栈的特殊性，只允许在栈顶进行操作，所以可称为进栈操作
// 即在栈顶增加元素
bool Push(SeqStack &S, int x) {
// 判断栈是否已满，由于top是静态数组最后一个元素的下标（栈顶元素下标）
// 所以只需要判断top值是否已经达到静态数组最大长度-1即可
if(S.top == MaxSize - 1) {
return false;
}
// top指针+1-->下标加一，指向数组后一位
S.top = S.top + 1;
// 新元素入栈
S.data[S.top] = x;
// 以上操作等价于S.data[++S.top] = x;
return true;
}
1.5 出栈
// 出栈操作
// 类似于线性表的删除操作，即“删”操作
// 但由于栈的特殊性，只允许在栈顶进行操作，所以可称为出栈操作
// 即在栈顶弹出元素
bool Pop(SeqStack &S, int &x) {
// 栈顶指针等于-1，栈为空，不可删除
if(S.top == -1) {
return false;
}
// 注意：虽然在此处出栈操作栈顶指针减一，可视为删除成功
// 但实际上数据仍然保留在存储单元中，只是从逻辑上删除了
// 将栈顶元素赋给x，x为引用变量，可从外部获取弹出的数据
x = S.data[S.top];
// 栈顶指针减一
S.top = S.top - 1;
// 以上操作等价于x= S.data[S.top--]
return true;
}
1.6 取栈顶元素
// 读取栈顶元素
// 与出栈操作类似，但并不会改变栈顶指针的值
bool GetTop(SeqStack S, int &x) {
// 栈顶指针等于-1，栈为空，不可删除
if(S.top == -1) {
return false;
}
// 栈顶元素
x = S.data[S.top];
return true;
}
1.7 弹出并输出栈中所有元素
// 输出栈中所有元素
// 由于栈只能从一端进行操作，所以想要输出所有元素，就必须要将所有元素弹出并输出
void PrintStack(SeqStack S) {
if(StackEmpty(S)) {
printf("the stack is empty!");
}
while(!StackEmpty(S)) {
int x;
Pop(S, x);
printf("pop:%dn", x);
}
}
2.完整代码
#include3.运行截图#define MaxSize 10 // 定义栈中元素最大个数 typedef struct { // 定义顺序栈 int data[MaxSize]; // 静态数组存放栈中元素 int top; // 栈顶指针：指向目前栈顶元素的位置 } SeqStack; // 初始化 void InitStack(SeqStack &S) { // 初始化栈顶指针，由于在顺序栈中，0表示栈底部的位置 // 所以初始应赋小于0的值，常用-1 S.top = -1; } // 判断栈空 bool StackEmpty(SeqStack S) { // 空栈条件：栈顶指针等于-1！！！ // 说明栈中没有任何元素 if(S.top == -1) { return true; } else { return false; } } // 进栈操作 // 类似于线性表的插入操作，即“增”操作 // 但由于栈的特殊性，只允许在栈顶进行操作，所以可称为进栈操作 // 即在栈顶增加元素 bool Push(SeqStack &S, int x) { // 判断栈是否已满，由于top是静态数组最后一个元素的下标（栈顶元素下标） // 所以只需要判断top值是否已经达到静态数组最大长度-1即可 if(S.top == MaxSize - 1) { return false; } // top指针+1-->下标加一，指向数组后一位 S.top = S.top + 1; // 新元素入栈 S.data[S.top] = x; // 以上操作等价于S.data[++S.top] = x; return true; } // 出栈操作 // 类似于线性表的删除操作，即“删”操作 // 但由于栈的特殊性，只允许在栈顶进行操作，所以可称为出栈操作 // 即在栈顶弹出元素 bool Pop(SeqStack &S, int &x) { // 栈顶指针等于-1，栈为空，不可删除 if(S.top == -1) { return false; } // 注意：虽然在此处出栈操作栈顶指针减一，可视为删除成功 // 但实际上数据仍然保留在存储单元中，只是从逻辑上删除了 // 将栈顶元素赋给x，x为引用变量，可从外部获取弹出的数据 x = S.data[S.top]; // 栈顶指针减一 S.top = S.top - 1; // 以上操作等价于x= S.data[S.top--] return true; } // 读取栈顶元素 // 与出栈操作类似，但并不会改变栈顶指针的值 bool GetTop(SeqStack S, int &x) { // 栈顶指针等于-1，栈为空，不可删除 if(S.top == -1) { return false; } // 栈顶元素 x = S.data[S.top]; return true; } // 输出栈中所有元素 // 由于栈只能从一端进行操作，所以想要输出所有元素，就必须要将所有元素弹出并输出 void PrintStack(SeqStack S) { if(StackEmpty(S)) { printf("the stack is empty!"); } while(!StackEmpty(S)) { int x; Pop(S, x); printf("pop:%dn", x); } } int main() { SeqStack S; InitStack(S); int x; Push(S, 3); GetTop(S, x); printf("push:%dn", x); Push(S, 5); GetTop(S, x); printf("push:%dn", x); Push(S, 7); GetTop(S, x); printf("push:%dn", x); PrintStack(S); return 0; }
