当前位置：首页 > news >正文

数据结构-顺序栈C++示例

news 2025/8/24 6:49:20

栈(stack)是限定仅在表尾进行插入或删除操作的线性表。

对栈来说，表尾端称为栈顶(top)，表头端称为栈底(bottom)，不含元素的空表称为空栈。

假设栈 $S=(a_1,a_2,a_3,\cdots,a_n)$ , 则称 $a_1$ 为栈底元素， $a_n$ 为栈顶元素，插入元素到栈顶(即表尾)的操作称为入栈，从栈顶(即表尾)删除最后一个元素的操作称为出栈。栈元素的修改是按后进先出的原则进行的，因此栈又称为后进先出(Last In First Out, LIFO)的线性表。

由于栈固有的后进先出特性，使得栈称为程序设计中的有用工具，另外，如果问题求解的过程具有“后进先出”的天然特性的话，则求解的算法中也需要利用“栈”，如：

数制转换
表达式求值
括号匹配的检验
八皇后问题
行编辑程序
函数调用
迷宫求解
递归调用的实现

抽象数据类型定义

ADT Stack{

数据对象: $D=\{{a_i}| a_i \in ElemSet, i=1,2,3,\cdots,n, n \geq 0\}$

数据关系: $R=\{<a_{i-1}, a_i> | a_{i-1},a_i \in D, i = 1,2,3,\cdots,n\}$

约定 $a_n$ 端为栈顶， $a_1$ 端为栈底。

基本操作：

InitStack(&S)

操作结果：构造一个空栈 $S$

DestroyStack(&S)

初始条件：栈 $S$ 已经存在

操作结果：栈 $S$ 被销毁

ClearStack(&S)

初始条件：栈 $S$ 已经存在

操作结果：将栈 $S$ 清空

StackEmpty(&S)

初始条件：栈 $S$ 已经存在

操作结果：若栈 $S$ 为空栈，则返回true，否则返回false

StackLength(&S)

初始条件：栈 $S$ 已经存在

操作结果：返回栈 $S$ 的元素个数，即栈的长度

GetTop(&S)

初始条件：栈 $S$ 已经存在且非空

操作结果：返回栈 $S$ 的栈顶元素

Push(&S,e)

初始条件：栈 $S$ 已经存在

操作结果：插入元素e为新的栈顶元素

Pop(&S,e)

初始条件：栈 $S$ 已经存在且非空

操作结果：删除S的栈顶元素，并且用e 返回其值

StackTraverse(&S,e)

初始条件：栈 $S$ 已经存在且非空

操作结果：从栈底到栈顶一次对S的每个数据元素进行访问

}ADT Stack

顺序栈

顺序栈是指利用顺序存储结构实现的栈。

初始化

bool InitStack(SqStack &S)
{S.base = new SElemType[MaxSize];if (!S.base){std::cerr << "内存分配失败" << std::endl;return false;}S.front = S.base;S.stacksize = MaxSize;return true;
}

销毁

bool DestroyStack(SqStack &S)
{if (S.base){delete[] S.base;S.stacksize = 0;S.base = S.front = nullptr;return true;}return false;
}

清空

bool ClearStack(SqStack &S)
{if (S.base){S.front = S.base;return true;}return false;
}

是否为空栈

bool StackEmpty(const SqStack &S)
{return S.base == S.front;
}

栈长度

int StackLength(const SqStack &S)
{return S.front - S.base;
}

入栈

bool Push(SqStack &S, const SElemType &e)
{if (S.front - S.base == S.stacksize){std::cerr << "顺序栈已满，无法插入新元素" << std::endl;return false;}*(S.front) = e;S.front++;return true;
}

出栈

bool Pop(SqStack &S, SElemType &e)
{if (StackEmpty(S)){std::cerr << "空栈无法取值" << std::endl;return false;}S.front--;e = *(S.front);return true;
}

获取栈顶元素

SElemType GetTop(const SqStack &S)
{if (StackEmpty(S)){std::cerr << "空栈无法取值" << std::endl;return false;}return *(S.front - 1);
}

遍历栈元素

void StackTraverse(const SqStack &S)
{for (int i = 0; i < S.front - S.base; i++){std::cout << "第 " << i + 1 << " 个元素为: " << S.base[i] << std::endl;}
}

头文件

#pragma once
#include <iostream>const int MaxSize = 100;
typedef int SElemType;
typedef struct _SqStack
{SElemType *base;  // 栈底SElemType *front; // 栈顶int stacksize;    // 栈可用的最大容量
} SqStack;bool InitStack(SqStack &S);
bool DestroyStack(SqStack &S);
bool ClearStack(SqStack &S);
bool StackEmpty(const SqStack &S);
int StackLength(const SqStack &S);
bool Push(SqStack &S, const SElemType &e);
bool Pop(SqStack &S, SElemType &e);
void StackTraverse(const SqStack &S);
SElemType GetTop(const SqStack &S);

测试文件

#include "include/stack.h"int main()
{SqStack S;InitStack(S);Push(S, 1);Push(S, 2);Push(S, 3);Push(S, 4);StackTraverse(S);SElemType top = GetTop(S);std::cout << "栈顶元素为: " << top << std::endl;int stack_len = StackLength(S);std::cout << "栈长度: " << stack_len << std::endl;Pop(S, top);StackTraverse(S);std::cout << "++++++++++++++" << std::endl;ClearStack(S);StackTraverse(S);DestroyStack(S);return 0;
}

链栈

链栈是指采用链式存储结构实现的栈。通常使用单链表来表示，由于栈的主要操作是在栈顶插入和删除，为了方便，这里将链表的头结点作为栈顶，且不需要头结点。

初始化

bool InitStack(LinkStack &S)
{S = nullptr;return true;
}

销毁

bool DestroyStack(LinkStack &S)
{while (S){StackNode *tmp = S->next;S = S->next;delete tmp;}return true;
}

清空

bool ClearStack(LinkStack &S)
{DestroyStack(S->next);S = nullptr;return true;
}

是否为空栈

bool StackEmpty(const LinkStack &S)
{return !S;
}

栈长度

int StackLength(const LinkStack &S)
{int len = 0;StackNode *tmp = S;while (tmp){len++;tmp = tmp->next;}return len;
}

入栈

bool Push(LinkStack &S, const ElemType &e)
{StackNode *p = new StackNode;p->data = e;p->next = S;S = p;return true;
}

出栈

bool Pop(LinkStack &S, ElemType &e)
{if (S){e = S->data;StackNode *tmp = S;S = S->next;delete tmp;return true;}return false;
}

获取栈顶元素

ElemType GetTop(const LinkStack &S)
{if (S)return S->data;else{return 0;}
}

遍历栈元素

void StackTraverse(const LinkStack &S)
{StackNode *tmp = S;int i = 0;while (tmp){i++;std::cout << "第 " << i << " 个元素为: " << tmp->data << std::endl;tmp = tmp->next;}
}

文章参考严蔚敏老师《数据结构 C语言版第2版》和青岛大学王卓数据结构视频课

查看全文

http://www.lryc.cn/news/175167.html