顺序栈的实现和两栈共享空间

顺序栈的实现和两栈共享空间

 以后慢慢启用个人博客：http://www.yuanrengu.com/

一.顺序栈的实现     

       栈(stack)是限定仅在表尾进行插入或删除操作的线性表。我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。

理解栈的定义需要注意：

1. 首先他是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过他是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
2. 他的特殊之处就在于限制了这个线性表的插入和删除位置，他始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。

      栈的插入操作，叫作进栈，也称压栈、入栈。栈的删除操作，叫出栈，也称弹栈。

     顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。

顺序栈的定义：

typedef struct{
ElemType *bottom;
ElemType *top;
int StackSize;
}SqStack;

其中，StackSize指示栈的当前可使用的最大容量。栈的初始化操作为：按设定的初始状态分配量进行第一次存储分配，bottom可称为栈底指针，在顺序栈中，他始终指向栈底的位置，如bottom的值为NULL，则表明栈结构不存在。称top为栈顶指针，其初值指向栈底，即top=bottom可作为栈空的标记，每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。如下图所示。

base = NULL;
//栈结构不存在
top = base;
//栈空

顺序栈的实现：

头文件stack.h

//stack.h

#define TRUE
1
#define FALSE
0
#define OK
1
#define ERROR
0
#define OVERFLOW
-1
#define UNDERFLOW
-2



//定义函数返回值类型

typedef int
Status;
//定义顺序栈的数据元素的类型

typedef int
ElemType;


//定义顺序栈的存储结构


#define STACK_INIT_SIZE 100 //初始分配空间大小

#define INCREMENTSIZE
10 //存储空间分配增量

struct SeqStack{

ElemType
*bottom;
//栈底指针


ElemType
*top;
//栈顶指针


int
size;
//栈存储空间大小

};

//声明顺序栈的基本操作

Status
InitStack(SeqStack &s);
//构造一个空栈
Status
DestroyStack(SeqStack &s);
//销毁一个栈
Status
ClearStack(SeqStack &s);
//把栈置空
Status
StackEmpty(SeqStack s);
//判断是否为空栈
Status
StackLength(SeqStack s);
//返回栈的长度（即元素个数）
Status
Push(SeqStack &s,ElemType e);
//元素入栈
Status
Pop(SeqStack &s,ElemType &e);
//元素出栈
Status
GetTop(SeqStack s,ElemType &e);
//返回栈顶元素
Status
StackTraverse(SeqStack s);
//遍历栈

实现函数：stack.cpp

1 #include "stack.h"

2 #include <iostream>

3 using namespace std;

4

5 Status
InitStack(SeqStack &s)

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


7 {

8
s.bottom=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

9
if(s.bottom == NULL){

cout<<"严重错误：顺序栈初始存储空间分配失败，程序退出";

exit(ERROR);

}

s.top=s.bottom;

s.size=STACK_INIT_SIZE;

return OK;
}

Status
DestroyStack(SeqStack &s)
//初始条件：栈s已存在
//操作结果：栈s已被销毁

{

free(s.bottom);

s.bottom=s.top=NULL;
//s.bottom的值为NULL，表示顺序栈不存在


s.size=0;

return OK;
}

Status
ClearStack(SeqStack &s)
//初始条件：栈s已存在
//操作结果：将s清为空栈

{

s.top=s.bottom;
//s.top == s.bottom作为顺序栈空的标记


return OK;
}

Status
StackEmpty(SeqStack s)
//初始条件：栈s已存在
//操作结果：若栈s为空栈，则返回TRUE，否则FALSE

{

if(s.top == s.bottom)

return TRUE;

else

return FALSE;
}

Status StackLength(SeqStack s)
//初始条件：栈s已存在
//操作结果：返回s的元素个数，即栈的长度

{

return s.top-s.bottom;
}

Status
Push(SeqStack &s,ElemType e)
//初始条件：栈s已存在
//操作结果：插入元素e成为新的栈顶元素

{

if(s.top-s.bottom >= s.size ){

s.bottom=(ElemType*)realloc(s.bottom,(s.size+INCREMENTSIZE)*sizeof(ElemType));

if(s.bottom == NULL){

cout<<"严重错误：顺序栈增量存储空间分配失败，程序退出！";

exit(OVERFLOW);

}

s.top=s.bottom+s.size;

s.size+=INCREMENTSIZE;

}


// *s.top=e;

//s.top++;


*s.top++ = e;

return OK;
}

Status
Pop(SeqStack &s,ElemType &e)
//初始条件：栈s已存在且非空
//操作结果：删除s的栈顶元素，并且用e返回其值

{

if(StackEmpty(s) == TRUE){

cout<<"顺序栈为空，出栈失败！"<<endl;

exit(UNDERFLOW);

}

// s.top--;

// e=*s.top;


e = *--s.top;

return OK;
}

Status
GetTop(SeqStack s,ElemType &e)
//初始条件：栈s已存在且非空
//操作结果：用e返回s的栈顶元素

{

if( StackEmpty(s) == TRUE ){

cout<<"访问栈顶元素发生错误：栈为空"<<endl;

exit(UNDERFLOW);

}

return *(s.top-1);
}

Status
StackTraverse(SeqStack s)
//初始条件：栈s已存在且非空
//操作结果：从栈底开始依次输出
{

if(s.bottom == NULL){

cout<<"严重错误：栈不存在，程序退出！";

exit(ERROR);

}

for(int i=0;i < StackLength(s);i++)

//
cout<<s.bottom[i]<<endl;


cout<<s.bottom[i]<<endl;

return OK;
}

测试函数：

//test.cpp

#include "stack.h"
#include <iostream>
using namespace std;

//获取随机整数

int RangedRand( int range_min, int range_max)
{

// Generate random numbers in the half-closed interval

// [range_min, range_max). In other words,

// range_min <= random number < range_max


int u =(int)( (double)rand() / (RAND_MAX + 1) * (range_max - range_min)

+ range_min );

return u;
}


int main()
{

struct SeqStack s;

InitStack(s);

ElemType data[10];

for(int i=0;i<10;i++){

data[i]=RangedRand(-500,500);

Push(s,data[i]);

}


StackTraverse(s);

cout<<"顺序栈的长度是："<<StackLength(s)<<endl;


ElemType e;

Pop(s,e);

cout<<"栈顶元素"<<e<<"出栈"<<endl;

cout<<"此时的顺序栈："<<endl;

StackTraverse(s);

cout<<"顺序栈的长度是："<<StackLength(s)<<endl;


DestroyStack(s);

StackTraverse(s);

cout<<"顺序栈的长度是："<<StackLength(s)<<endl;



return 0;
}

 

二.两栈共享空间

      如果我们有两个相同类型的栈，我们为他们各自开辟了数组空间，极有可能第一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲。这时，我们完全可以用一个数组两存储两个栈。

      我们的做法如下图，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为数组的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素，就是两端点向中间延伸。

     其实关键思路是：他们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，可以想象，只要他们两不见面，两个栈就可以一直使用。

     从这里也就可以分析出来，栈1为空时，就是top1等于-1时；而当top2等于n时，即是栈2为空时，那么什么时候栈满呢？

     想想极端的情况，若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2等于0时，为栈2满。但更多的情况，其实就是刚才说的，两个栈见面之时，也就是两个指针之间相差1时，即top1+1==top2为栈满。

     两栈共享空间的结构的代码如下：

typedef struct
{
ElemType data[MAXSIZE];
int top1;
//栈1栈顶指针
int top2;
//栈2栈顶指针
}SqDoubleStack;

      对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入元素的代码如下：

Status Push(SqDoubleStack *s , ElemType e , int stackNumber)
{

if(s->top1+1 == s->top2)
//栈已满，不能再push新元素了

return ERROR;

if(stackNumber == 1)
//栈1有元素进栈

s->data[++s->top1] = e;
//若栈1则先top+1后给数组元素赋值

else if(stackNumber == 2)
//栈2有元素进栈

s->data[--s->top2] = e;
//若栈2则先top2-1后给数组元素赋值

return OK;

}

      因为在开始已经判断了是否有栈满的情况，所以后面的top1+1或top2-1是不担心溢出问题的。

      对于两栈共享空间的pop方法，参数就只是判断栈1栈2的参数stackNumber，代码如下：

//若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status Pop(SqDoubleStack *s , ElemType *e , int stackNumber)
{

if(stackNumber == 1)

{

if(s->top1 == 1)

return ERROR;
//说明栈1已经是空栈，溢出

*e = s->data[s->top1--];
//将栈1的栈顶元素出栈 

}

else if(stackNumber == 2)

{

if(s->top2 == MAXSIZE)

return ERROR;
//说明栈2已经是空栈，溢出

*e = s->data[s->top2++];
//将栈2的栈顶元素出栈

}

return OK;
}

      事实上，使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。

      注意：这只是针对两个具有相同数据类型的栈。