栈的两种存储结构

栈的两种存储结构

栈的特点：

在固定一端进行插入删除，在栈顶进行

链式存储结构定义（不带头结点）：

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); }; 链式栈结构定义

出栈操作：                                                                                                            

入栈操作：

判断栈空：top是否等于NULL

根据上述写出链式结构的基本操作，同时设置计数器来计算堆栈的元素个数

#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 = 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变量来指示栈顶元素

备注：在进行入栈操作时，

1.stack.s[s.top]=x;

 2. s.top++;

这两句语句的执行顺序可以不同，具体情况根据top初始化的值来确定：若top=-1,则2语句先执行，若top=0,则语句1先执行

 

 则顺序结构基本操作：

#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);}}

重点理解：

1.在栈顶一端进行插入删除操作，在两种存储结构下，插入删除操作均在top指向的栈顶一端进行操作

2.同时top指向栈顶元素

 堆栈习题：

重点理解为：求堆栈无论顺序存储或链式堆栈中节点个数时，利用堆栈弹出元素直至栈空为止。

则传入的不是指针类型参数，即在求节点的函数中可对堆栈改变，而不能将此改变传入主函数中改变堆栈的结构。

实则也是对指针的理解

转载于:https://www.cnblogs.com/zlspace/p/6919975.html

总结

以上是生活随笔为你收集整理的栈的两种存储结构的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。