首页 > 代码库 > 栈的两种存储结构
栈的两种存储结构
内容：栈的两种存储结构
栈的特点：
在固定一端进行插入删除，在栈顶进行
链式存储结构（不带头结点）：
class StackNode {public: int data; StackNode *next; StackNode():next(NULL){}};class StackLine {public: StackNode *top; int count; StackLine():top(NULL),count(0){} //无初始化函数因为无需头结点 void pop(StackLine *t); void push(StackLine *t,int x); bool isempty(StackLine *t); int Get_Top(StackLine *t);};
出栈操作：
入栈操作：
根据图写出链式结构的头文件
#include<iostream>#include<string>#include<cstring>using namespace std;//链栈结构书上为带头节点的链栈结构，此为不带头结点的链栈结构class StackNode {public: int data; StackNode *next; StackNode():next(NULL){}};class StackLine {public: StackNode *top; int count; StackLine():top(NULL),count(0){} //无初始化函数因为无需头结点 void pop(StackLine *t); void push(StackLine *t,int x); bool isempty(StackLine *t); int Get_Top(StackLine *t);};void StackLine::pop(StackLine *t){ if (t->count == 0)cout << "此时栈空\n"; else { StackNode *tem; tem = t->top;//top指向待释放的节点 top = t->top->next;//顺序为先确定指向在释放节点 delete tem; } t->count--;}void StackLine::push(StackLine *t, int x){ //创建一个新节点再确定指向 StackNode *s = new StackNode(); s->data =http://www.mamicode.com/ x; if (t->count!=0) {//栈非空 s->next = t->top; t->top = s; } else { //栈空 s->next = NULL; t->top = s; } t->count++;}bool StackLine::isempty(StackLine *t){ if (t->count == 0)return true; else return false;}int StackLine::Get_Top(StackLine *t){ return t->top->data; }
顺序存储结构：如下图所示，数组大小为max=5，用top变量来指示栈顶元素
则顺序结构头文件：
#include<iostream>#include<string>#include<cstring>const int max = 100;using namespace std;class Stack {public: int s[max]; int top; Stack(){ top = -1; memset(s,0,sizeof(s)); }//构造函数 void push(int x); void pop(); int Get_Top(); bool Notempty(); };void Stack::push(int x){//判断有效性 if (top>=max-1)cout << "栈满\n"; else s[++top] = x;}//top位置void Stack::pop(){//判断有效性 if (top <=-1)cout << "栈空\n"; else --top;}int Stack::Get_Top(){//取栈顶元素的操作应发生在判断非空之后 return s[top ];}bool Stack::Notempty(){ if (top == -1)return false; else return true;}
测试主函数
#include<iostream>#include<string>#include"顺序.h"#include"链表.h"using namespace std;//节点数据域均为int类型int main(){ //测试顺序存储结构 /*Stack *testone=new Stack(); for (int i = 0; i < 5; i++) testone->push(i); cout << "此时栈顶元素为:" << testone->Get_Top() << endl;; cout << "栈中元素依次出栈\n"; while (testone->Notempty())//非空 { cout << testone->Get_Top() << " "; testone->pop(); }*/ //测试链式存储结构 StackLine *testtwo = new StackLine(); for (int i = 0; i < 5; i++) testtwo->push(testtwo,i); cout << "此时栈顶元素为:" << testtwo->Get_Top(testtwo) << endl; while (!testtwo->isempty(testtwo))//非空 { cout << testtwo->Get_Top(testtwo) << " "; testtwo->pop(testtwo); } }
重点理解：在栈顶一端进行插入删除操作，在两种存储结构下，插入删除操作均在top指向的栈顶一端进行操作
栈的两种存储结构
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。