数据结构-栈和队列
?
栈和队列
栈和队列都是线性数据结构，逻辑结构和线性表相同。
栈和队列的插入和删除操作受到某些限制，与线性表不同，也被称为操作受限的线性表。
栈
栈是一种插入和删除都只能在表的同一端操作的线性表。
允许进行插入和删除操作的一端叫栈顶(Top)，也叫表尾；另一端叫做栈底(Bottom)，也叫表头。
栈中没有元素时称为空栈。
向栈中插入元素的操作称为进栈或入栈(push)，从栈中删除元素的操作称为退栈或出栈(pop)。
栈是按照先进后出(FILO,First In Last Out)或后进先出(LIFO,Last In First Out)的原则组织数据。
栈的基本操作
创建一个空栈；删除一个栈；判断栈是否为空；判断栈是否为满；栈顶插入一个元素；求栈顶元素的值；删除栈顶的一个元素；输出栈。
栈的抽象数据类型
顺序栈
采用顺序存储结构表示的栈称为顺序栈。
顺序栈需要分配一块连续的存储区域来存放栈中的元素。
顺序栈可以用一维数组实现。
栈底位置固定不变，可以吧栈底设置在一维数组任意一端。
栈顶位置随着进栈和出栈操作不断变化，因此用一个变量来指示当前栈顶位置。
顺序栈类模板：栈中最大元素个数为MaxSize,顺序类模板名称LinearStack
#include
using namespace std;
template<class T>
class LinearStack
{
public:
LinearStack(int LSMaxSize); //构造函数，创建空栈
~LinearStack(); //析构函数，删除栈
bool IsEmpty(); //栈空返回true,非空返回false
bool IsFull(); //栈满返回true,不满返回false
int GetElementNumber(); //求栈中元素的个数
bool Push(const T& x); //在栈顶插入元素x，成功返回true，失败返回false
bool Top(T& x); //求栈顶元素的值放入x，成功返回true，失败返回false
bool Pop(T& x); //从栈顶删除一个元素，并将该元素的值放入x中
void OutPut(ostream& out)const; //将顺序栈放到输出流out中输出
private:
int top; //用来表示栈顶
int MaxSize; //栈中最大元素个数
T *element; //一维动态数组
}; 将栈顶top赋值为-1，表示空栈。
当栈中已有MaxSize个元素，如果再进行进栈操作，就会产生溢出，称为上溢；对空栈进行出栈操作时也会产生溢出，称为下溢。
进行进栈出栈操作时，应先检查栈是否为满（IsFull）或是否为空（IsEmpty）；
IsEmpty()的算法是：return top==-1;
IsFull()的算法是：return top+1=MaxSize;
求栈中元素的个数GetElementNumber()的算法：return top+1;
进栈操作Push(const T& x)的算法：
//向栈顶插入一个元素x
if(IsFull())
return false;
else
{
top++;
element[top]=x;
return true;
}Pop(T& x)出栈操作算法：
if(IsEmpty())
return false;
else
{
x=element[top];
top--;
return true;
}顺序栈的基本操作实现
//实现构造函数
template<class T>
LinearStack::LinearStack(int LSMaxSize)
{
MaxSize=LSMaxSize;
element = new T[LSMaxSize];
top=-1;
}
//析构函数
template<class T>
LinearStack::~LinearStack()
{
delete []element;
}
//实现判断栈是否为空
template<class T>
bool LinearStack::IsEmpty()
{
return top==-1;
}
//实现判断是否为满
template<class T>
bool LinearStack::IsFull()
{
return top+1=MaxSize;
}
//实现进栈
template<class T>
bool LinearStack::Push(const T& x)
{
if(IsFull())
return false;
else
{
top++;
element[top]=x;
return true;
}
}
//求栈顶元素
template<class T>
bool LinearStack::Top(T& x)
{
if(IsEmpty())
return false;
else
{
x=element[top];
return true;
}
}
//实现出栈
template<class T>
bool LinearStack::Pop(T& x)
{
if(IsEmpty())
return false;
else
{
x=element[top];
top--;
return true;
}
}
//实现顺序栈的输出，栈底到栈顶的顺序输出
template<class T>
void LinearStack::OutPut(ostream& out) const
{
for(int i=0;i<=top;i++)
out<//重载插入运算符<<
template<class T>
ostream& operator<<(ostream& out,const LinearStack& x)
{
x.OutPut(out);
return out;
} 顺序栈的应用
//除基取余法
//将给定的十进制数n转换为基数为base的进制数
void conversion(int n,int base)
{
int x,y;
y=n;
LinearStack<int> s(100);
while(y!=0)
{
s.Push(y%base);
y = y/base;
}
cout<<"十进制数"<"转换为"<"进制为：\n";
while(!s.IsEmpty())
{
s.Pop(x);
cout< 链式栈
把栈组织成一个单向链表，即采用链接结构来表示栈，这样的数据结构称为链接栈。
每一个结点表示栈中的一个元素。
栈是在链表头部进行插入和删除操作，故链接栈不需要再设置表头结点。
链接栈具有动态分配元素结点的特点，内存足够的情况下，链接栈中最大元素的个数没有限制。没有判断栈满的方法，IsFull
其他操作和顺序栈基本操作含义相同。
链接栈存储结点类模板
template<class T>
class LinkNode //结点类
{
template<class T>
friend class LinkStack; //将链接栈类声明为友类
public:
LinkNode()//构造函数
{
next=NULL;
}
private:
T data; //结点元素
LinkNode *next; //指向下一个结点的指针
}
链接栈类模板
template<class T>
class LinkStack
{
public:
LinkStack(); //构造函数，创建空栈
~LinkStack(); //析构函数，删除栈
bool IsEmpty() const; //栈空返回true,非空返回false
bool Push(const T& x); //在栈顶插入元素x，成功返回true，失败返回false
bool Top(T& x); //求栈顶元素的值放入x，成功返回true，失败返回false
bool Pop(T& x); //从栈顶删除一个元素，并将该元素的值放入x中
void OutPut(ostream& out)const; //将顺序栈放到输出流out中输出
private:
LinkNode *top; //用来表示栈顶
int size; //栈中元素个数
}; 进栈操作Push：向链接栈的栈顶插入一个元素结点，先将待进栈的结点的指针域指向原来的栈顶结点，然后将栈顶指针top指向该结点。
出栈操作Pop：从链表的栈顶删除一个元素结点，先将栈顶元素取出放到x中，然后使栈顶指针top指向原栈顶结点的后继结点，然后物理上删除该结点。当top为空时，链接栈为空。
链接栈基本操作实现
//构造函数
template<class T>
LinkStack::LinkStack()
{
top=NULL;
size=0;
}
//析构函数
template<class T>
LinkStack::~LinkStack()
{
T x;
while(top!=NULL) //栈非空则元素依次出栈
Pop(x);
}
//判断栈是否为空
template<class T>
bool LinkStack::IsEmpty() const
{
return top==NULL;
}
//实现进栈
template<class T>
bool LinkStack::Push(const T& x)
{
LinkNode *p = new LinkNode;
if(p==NULL)
return false;
else
{
p->data=x; //为元素赋值
p->next=top; //将新结点插入栈顶
top=p; //top指向栈顶
size++;
return true;
}
}
//实现求栈顶元素
template<class T>
bool LinkStack::Top(T& x)
{
if(IsEmpty())
return false;
else
{
x=top->data;
return true;
}
}
//实现出栈
template<class T>
bool LinkStack::Pop(T& x)
{
LinkNode *p;
if(IsEmpty())
return false;
else
{
x=top->data; //删除元素的值放入x中
p=top; //得到待删除结点的指针
top=top->next; //top指向新的栈顶
delete p; //元素出栈
size--;
return true;
}
}
//实现链接栈的输出
template<class T>
void LinkStack::OutPut(ostream& out)const
{
LinkNode *p;
p=top;
for(int i=0;idata<next;
}
}
//重新载入运算符<<
template<class T>
ostream& operator<<(ostream& out,const LinkStack& x)
{
x.OutPut(out);
return out;
} 队列
队列是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。
队列的插入操作称为入队，允许入队的一端称为队尾(rear)。
队列的删除操作称为出队，允许出队的一端称为队头(front)。
不含元素的队列称为空队列。
队列是先进先出(FIFO,First In First Out)或后进后出（LILO,Last In Last Out）的线性表。
队列的基本操作
队列的抽象数据类型
顺序队列
采用顺序存储结构的队列称为顺序队列。
顺序队列用一个一维数组来存放队列中的数据元素，此外设置两个整型变量front和rear，分别指示队头和队尾，称为头指针和尾指针。
约定：为了运算方便，约定在非空队列里，front始终指向队头元素，rear始终指向队尾元素的下一个位置；初始化队列时，front和rear均置为0；在队列中，由front和rear共同反应队列中元素动态变化的情况。
入队操作：将新元素插入到rear所指位置，再将rear的值加1。
出队操作：删除front所指位置的元素后，再将front的值加1并返回被删元素。
队列为空的条件：front==rear
队列存在溢出问题：当队列满时，再做入队操作，称为上溢；当队列空时，再做出队操作，称为下溢。
假上溢：front和rear随着队列插入和删除操作变化，某种状态下，队列的实际可用空间没有占满，但尾指针已超越存储空间的上界，也不能做入队操作，此时称为假上溢。
循环队列
为避免假上溢出现，充分利用队列的存储空间，将顺序队列存储空间的最后一个位置和第一个位置逻辑上连接在一起，这样的队列称为循环队列。
实现：
假设当前队列最多容纳MaxSize个元素，逻辑上的循环通过头、尾指针加1操作实现，当头、尾指针指向存储空间的上界，通过下面逻辑将头、尾指针指向下界0：
front =(front+1)%(MaxSize); rear = (rear+1)%(MaxSize);
循环队列示意图
循环队列无法依据头尾指针相等判断队列是空是满。
判断循环队列是空是满的两种办法：
1、约定少用一个元素空间。入队前，如果关系（rear+1）%(MaxSize)==front 存在，就认为队列已满。这个方法rear始终指向那个空闲的元素空间。
2、使用一个计数器size记录当前队列的实际长度。如果size=0，当front==rear时，当前队列是空队列，可以进行入队操作;否则，当前队列满，不能入队。
顺序循环队列类模板
template<class T>
class LinearQueue
{
public:
LinearQueue(int LQMaxSize); //创建空队列，构造函数
~LinearQueue(); //删除队列，析构函数
bool IsEmpty(); //判断队列是否为空，空返回true，非空返回fasle
bool IsFull(); //判断队列是否为满，满返回true，不满返回false
bool Insert(const T& x); //入队，在队列尾部插入元素x
bool GetElement(T& x); //求队头元素的值放入x中
bool Delete(T& x); //出队，从队头删除一个元素，并将该元素的值放入x中
void OutPut(ostream& out) const; //输出队列
private:
int size; //队列的实际元素个数
int MaxSize; //队列的最大元素个数
int front,rear; //队列队头和队尾指针
T *element; //一维动态数组
}顺序循环队列的基本实现
//实现构造函数
template<class T>
LinearQueue::LinearQueue(int LQMaxSize)
{
MaxSize=LQMaxSize;
element=new T[MaxSize];
size=0;
front=0;
rear=0;
}
//实现析构函数
template<class T>
LinearQueue::~LinearQueue()
{
delete []element;
}
//实现判断队列是否为空
template<class T>
bool LinearQueue::IsEmpty()
{
return size==0;
}
//判断队列是否满
template<class T>
bool LinearQueue::IsFull()
{
return size==MaxSize;
}
//实现入队
template<class T>
bool LinearQueue::Insert(const T& x)
{
if(IsFull())
return false;
else
{
element[rear]=x;
rear=(rear+1)%(MaxSize);
size++;
return true;
}
}
//实现求队头元素
template<class T>
bool LinearQueue::GetElement(T& x)
{
if(IsEmpty())
return false;
else
{
x=element[front];
return true;
}
}
//实现出队
template<class T>
bool LinearQueue::Delete(T& x)
{
if(IsEmpty())
return false;
else
{
x=element[front];
front = (front+1)%(MaxSize);
size--;
return true;
}
}
//实现顺序队列的输出
template<class T>
void LinearQueue::OutPut(ostream& out) const
{
int index;
index = front;
for(int i=0;i1)%(MaxSize);
}
}
//重新载入运算符<<
template<class T>
ostream& operator<<(ostream& out,const LinearQueue& x)
{
x.OutPut(out);
return out;
} 顺序循环队列的应用
#include
using namespace std;
#include "LinearQueue.h"
/*输出第n行的空格，参数n为要输出的杨辉三角的行数，k为当前输出行数*/
void PrintSpce(int n,int k)
{
for(int i=1;i<=n-k;i++)
cout<<' ';
}
//输出杨辉三角的前n行（n>0）
void YangHui(int n)
{
LinearQueue<int> Q(n+2);
int x y;
PrintSpace(n,1); //输出第一行前面的空格
cout<<'1'<//输出第一行的1
Q.Insert(0); //添加行开始标识
Q.Insert(1); //第2行入队
Q.Insert(1); //第2行入队
for(int i=2;i<=n;i++)
{
Q.Insert(0); //添加行结束标识
PrintSpace(n,i); //输出第i行数字前面的空格
do
{
Q.Delete(x);
Q.GetElement(y);
if(y!=0)
cout<' ';
else
cout<Insert(x+y);
}while(y!=0);
}
cout<//主函数
int main()
{
int n;
cout<<"请输入要显示的杨辉三角的行数";
cin>>n;
YangHui(n);
return 0;
} 链接队列
采用链式存储结构的队列称为链接队列。
队列的链式存储结构是仅在表头删除结点和在表尾插入结点的单链表。
链接队列中，需要增加指向队头和队尾的两个指针front和rear。
链接队列由一个头指针front和一个尾指针rear唯一确定。
链接队列存储结点类模板
template<class T>
class LinkNode //结点类
{
template<class T>
friend class LinkQueue; //将链接队列类声明为友类
public:
LinkNode() //构造函数
{
next=NULL;
}
private:
T data; //结点元素
LinkNode *next; //指向下一个结点的指针
} 链接队列类模板
template<class T>
class LinkQueue
{
public:
LinkQueue(); //创建空队列，构造函数
~LinkQueue(); //删除队列，析构函数
bool IsEmpty(); //判断队列是否为空，空返回true，非空返回fasle
bool IsFull(); //判断队列是否为满，满返回true，不满返回false
bool Insert(const T& x); //入队，在队列尾部插入元素x
bool GetElement(T& x); //求队头元素的值放入x中
bool Delete(T& x); //出队，从队头删除一个元素，并将该元素的值放入x中
void OutPut(ostream& out) const; //输出队列
private:
int size; //队列的实际元素个数
LinkNode *front,*rear; //队列的队头和队尾指针
} 链接队列基本操作实现
//实现构造函数
template<class T>
LinkQueue::LinkQueue()
{
front=NULL;
rear=NULL;
size=0;
}
//实现析构函数
template<class T>
LinkQueue::~LinkQueue()
{
T x;
while(front!=NULL) //队列非空则元素依次出队
Delete(x);
}
//实现判断队列是否为空
template<class T>
bool LinkQueue::IsEmpty()
{
return size==0;
}
//实现入队
template<class T>
bool LinkQueue::Insert(const T& x)
{
LinkNode *p=new LinkNode;
if(p==NULL)
return false;
else
{
p->data=x; //为元素赋值
if(front==NULL) //插入前是空队列
{
rear=p;front=p;
}
else
{
rear->next=p; //插入新结点
rear=p; //指向新队尾
}
size++;
return true;
}
}
//实现求队头元素
template<class T>
bool LinkQueue::GetElement(T& x)
{
if(IsEmpty())
return false;
else
{
x=front->data;
return true;
}
}
//实现出队
template<class T>
bool LinkQueue::Delete(T& x)
{
LinkNode *p;
if(IsEmpty())
return false;
else
{
p=front;
x=front->data;
front=front->next;
delete p; //删除队头结点
size--;
return true;
}
}
//实现顺序队列的输出
template<class T>
void LinkQueue::OutPut(ostream& out) const
{
LinkNode *p;
p = front;
for(int i=0;idata<next;
}
}
//重新载入运算符<<
template<class T>
ostream& operator<<(ostream& out,const LinkQueue& x)
{
x.OutPut(out);
return out;
}
?