栈和链栈的实现及其相关操作详解

一、概述

队列简称队（先进先出），是一种只允许在表的一端进行插入操作，在另一端进行删除操作的线性表。允许插入的一端被称为队尾，队尾元素由rear指出，允许删除的一端被称为队首，由front指出。

栈和链栈的实现及其相关操作详解

我们得struct需要三个数据成员：data（数组）、队首指针（front）、队尾指针（rear）。

#ifndef STACK_H
#define STACK_H
#include<iostream>
using namespace std;
//顺序栈
const int STACK_SIZE = 10;
class SqStack
{
public:
SqStack(int size );
~SqStack();
//入栈操作
void push(int val);
//出栈操作
void pop();
//获取栈顶元素
int top();
//判断栈空
bool empty();
//判断栈满
bool full();
private:
int *mpstack;
int mtop;
int msize;
};

#endif

代码实现（c++）：

#include"Stack.h"
#include<iostream>
using namespace std;
SqStack::SqStack(int size = 10)
{
mpstack = new int[size];
mtop = -1;
msize = size;
}
SqStack:: ~SqStack()
{
delete []mpstack;
mpstack = NULL;

}
//入栈操作
void SqStack:: push(int val)
{
if(full())
return ;
mpstack[++mtop] = val;
}
//出栈操作
void SqStack::pop()
{
if(empty())
return;
--mtop;
}
//获取栈顶元素
int SqStack::top()
{
return mpstack [mtop];
}
//判断栈空
bool SqStack::empty()
{
return mtop == -1;
}
//判断栈满
bool SqStack::full()
{
return mtop == msize-1;
}

链栈：

#include <iostream>
#include <typeinfo>
using namespace std;
/*用模板实现链式栈和链式队列，采用继承结构*/

template<typename T>
class DSBase
{
public:
virtual void push(const T &val) = 0;
virtual void pop() = 0;
virtual void show() = 0;
virtual T front()const = 0;
virtual T back()const = 0;
};
template<typename T>
class Stack : public DSBase<T>
{
public:
//构造析构重写5个抽象方法
Stack();
~Stack();
virtual void push(const T &val) ;
virtual void pop() ;
virtual void show() ;
virtual T front()const ;
virtual T back()const ;
private:
struct Node
{
public:
Node(T data = T())
:mdata(data), mpnext(NULL),mprio(NULL){}
T mdata;
Node *mpnext;
Node *mprio;
};
Node *mpbottom;
Node *mptop;
};
template<typename T>
Stack<T>::Stack()
{
mpbottom = new Node();
mptop = new Node();
mpbottom->mprio = mptop;
mptop->mpnext = mpbottom;

}
template<typename T>
Stack<T>::~Stack()
{
if(NULL == mptop)
return;
Node* pcur = mptop;
while(mptop != mpbottom)
{
mptop = mptop->mpnext;
delete pcur;
pcur = mptop;

}
}
template<typename T>
void Stack<T>:: push(const T &val)
{
Node* pnode = new Node(val);
pnode->mprio = mptop;
pnode->mpnext = mptop->mpnext;
mptop->mpnext = pnode;
pnode->mpnext->mprio = pnode;

}
template<typename T>
void Stack<T>:: pop()
{
if(mpbottom == mptop) return;
Node* pcur = mptop ;
mptop = mptop->mpnext;
delete pcur;

}
template<typename T>
void Stack<T>::show()
{
Node* pcur = mptop->mpnext;
while(pcur != mpbottom)
{
cout<<pcur->mdata<<" ";
pcur = pcur->mpnext;
}
cout<<endl;
}
template<typename T>
T Stack<T>::front()const
{
if(mptop == mpbottom)return 0;
return mpbottom->mprio->mdata;
}
template<typename T>
T Stack<T>::back()const
{
if(mptop == mpbottom)return 0;
return mptop->mpnext->mdata;
}

int main()
{
Stack<int> stack1;
stack1.push(1);
stack1.push(2);
stack1.push(3);
stack1.push(4);
stack1.show();
cout<<stack1.back()<<endl;
cout<<stack1.front()<<endl;
stack1.pop();
stack1.show();
return 0;
}

栈和链栈的实现及其相关操作详解

相关推荐