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

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

一.顺序栈的实现

       栈(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

 1 //stack.h
 2 
 3 #define TRUE        1  
 4 #define FALSE       0  
 5 #define OK          1  
 6 #define ERROR       0  
 7 #define OVERFLOW    -1  
 8 #define UNDERFLOW   -2  
 9 
10  
11 
12 //定义函数返回值类型  
13 typedef int  Status;  
14 //定义顺序栈的数据元素的类型  
15 typedef int  ElemType;
16 
17    
18 //定义顺序栈的存储结构  
19 
20 #define STACK_INIT_SIZE 100 //初始分配空间大小
21 
22 #define INCREMENTSIZE   10 //存储空间分配增量  
23 struct SeqStack{  
24     ElemType    *bottom;    //栈底指针  
25     ElemType    *top;       //栈顶指针  
26     int      size;       //栈存储空间大小  
27 };
28 
29 //声明顺序栈的基本操作  
30 Status  InitStack(SeqStack &s);  //构造一个空栈
31 Status  DestroyStack(SeqStack &s);  //销毁一个栈
32 Status  ClearStack(SeqStack &s);  //把栈置空
33 Status  StackEmpty(SeqStack s);  //判断是否为空栈
34 Status  StackLength(SeqStack s);  //返回栈的长度(即元素个数)
35 Status  Push(SeqStack &s,ElemType e);  //元素入栈
36 Status  Pop(SeqStack &s,ElemType &e);  //元素出栈
37 Status  GetTop(SeqStack s,ElemType &e);  //返回栈顶元素
38 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){  
 10         cout<<"严重错误:顺序栈初始存储空间分配失败,程序退出";  
 11         exit(ERROR);  
 12     }   
 13     s.top=s.bottom;
 14     s.size=STACK_INIT_SIZE;   
 15     return OK;  
 16 }  
 17 
 18 Status  DestroyStack(SeqStack &s)  
 19 //初始条件:栈s已存在  
 20 //操作结果:栈s已被销毁  
 21 {  
 22     free(s.bottom);   
 23     s.bottom=s.top=NULL;  //s.bottom的值为NULL,表示顺序栈不存在   
 24     s.size=0;  
 25     return OK;  
 26 }  
 27 
 28 Status  ClearStack(SeqStack &s)  
 29 //初始条件:栈s已存在  
 30 //操作结果:将s清为空栈  
 31 {   
 32     s.top=s.bottom;  //s.top == s.bottom作为顺序栈空的标记  
 33     return OK;  
 34 }  
 35 
 36 Status  StackEmpty(SeqStack s)  
 37 //初始条件:栈s已存在  
 38 //操作结果:若栈s为空栈,则返回TRUE,否则FALSE  
 39 {  
 40     if(s.top == s.bottom)  
 41         return TRUE;  
 42     else 
 43         return FALSE;  
 44 }  
 45 
 46 Status StackLength(SeqStack s)  
 47 //初始条件:栈s已存在  
 48 //操作结果:返回s的元素个数,即栈的长度  
 49 {  
 50     return s.top-s.bottom;  
 51 }  
 52 
 53 Status  Push(SeqStack &s,ElemType e)  
 54 //初始条件:栈s已存在  
 55 //操作结果:插入元素e成为新的栈顶元素  
 56 {       
 57    if(s.top-s.bottom >= s.size ){   
 58         s.bottom=(ElemType*)realloc(s.bottom,(s.size+INCREMENTSIZE)*sizeof(ElemType));  
 59         if(s.bottom == NULL){  
 60             cout<<"严重错误:顺序栈增量存储空间分配失败,程序退出!";  
 61             exit(OVERFLOW);  
 62         }    
 63         s.top=s.bottom+s.size;   
 64         s.size+=INCREMENTSIZE;  
 65     }   
 66 
 67    // *s.top=e;
 68     //s.top++;  
 69    *s.top++ = e;
 70     return OK;  
 71 }  
 72 
 73 Status  Pop(SeqStack &s,ElemType &e)  
 74 //初始条件:栈s已存在且非空  
 75 //操作结果:删除s的栈顶元素,并且用e返回其值  
 76 {  
 77     if(StackEmpty(s) == TRUE){  
 78         cout<<"顺序栈为空,出栈失败!"<<endl;  
 79         exit(UNDERFLOW);  
 80     }  
 81    // s.top--;
 82    // e=*s.top;  
 83     e = *--s.top;
 84     return OK;  
 85 }   
 86  
 87 Status  GetTop(SeqStack s,ElemType &e)  
 88 //初始条件:栈s已存在且非空  
 89 //操作结果:用e返回s的栈顶元素  
 90 {  
 91     if( StackEmpty(s) == TRUE ){  
 92         cout<<"访问栈顶元素发生错误:栈为空"<<endl;  
 93         exit(UNDERFLOW);  
 94     }   
 95     return *(s.top-1);  
 96 }  
 97 
 98 Status  StackTraverse(SeqStack s)  
 99 //初始条件:栈s已存在且非空  
100 //操作结果:从栈底开始依次输出
101 {  
102     if(s.bottom == NULL){  
103         cout<<"严重错误:栈不存在,程序退出!";  
104         exit(ERROR);  
105     }   
106     for(int i=0;i < StackLength(s);i++)   
107     //    cout<<s.bottom[i]<<endl;   
108         cout<<s.bottom[i]<<endl;  
109     return OK;  
110 }

测试函数:

 1 //test.cpp
 2 
 3 #include "stack.h"   
 4 #include <iostream>
 5 using namespace std;
 6 
 7 //获取随机整数  
 8 int RangedRand( int range_min, int range_max)   
 9 {   
10    // Generate random numbers in the half-closed interval   
11    // [range_min, range_max). In other words,   
12    // range_min <= random number < range_max   
13    int u =(int)( (double)rand() / (RAND_MAX + 1) * (range_max - range_min)   
14             + range_min );    
15    return u;   
16 }   
17   
18   
19 int main()   
20 {   
21     struct SeqStack s;   
22     InitStack(s);     
23     ElemType data[10];   
24     for(int i=0;i<10;i++){   
25         data[i]=RangedRand(-500,500);   
26         Push(s,data[i]);   
27     }   
28   
29     StackTraverse(s);   
30     cout<<"顺序栈的长度是:"<<StackLength(s)<<endl;   
31   
32     ElemType e;   
33     Pop(s,e);   
34     cout<<"栈顶元素"<<e<<"出栈"<<endl;   
35     cout<<"此时的顺序栈:"<<endl;   
36     StackTraverse(s);   
37     cout<<"顺序栈的长度是:"<<StackLength(s)<<endl;   
38   
39     DestroyStack(s);   
40     StackTraverse(s);   
41     cout<<"顺序栈的长度是:"<<StackLength(s)<<endl;   
42 
43 
44     return 0;   
45 }

二.两栈共享空间

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

      我们的做法如下图,数组有两个端点,两个栈有两个栈底,让一个栈的栈底为数组的始端,即下标为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。插入元素的代码如下:

 1 Status Push(SqDoubleStack *s , ElemType e , int stackNumber)
 2 {
 3     if(s->top1+1 == s->top2)       //栈已满,不能再push新元素了
 4         return ERROR;
 5     if(stackNumber == 1)           //栈1有元素进栈
 6         s->data[++s->top1] = e;    //若栈1则先top+1后给数组元素赋值
 7     else if(stackNumber == 2)      //栈2有元素进栈
 8         s->data[--s->top2] = e;    //若栈2则先top2-1后给数组元素赋值
 9     return OK;
10 
11 }

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

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

 1 //若栈不空,则删除s的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
 2 Status Pop(SqDoubleStack *s , ElemType *e , int stackNumber)
 3 {
 4     if(stackNumber == 1)
 5     {
 6         if(s->top1 == 1)
 7             return ERROR;            //说明栈1已经是空栈,溢出
 8         *e = s->data[s->top1--];     //将栈1的栈顶元素出栈 
 9     }
10     else if(stackNumber == 2)
11     {
12         if(s->top2 == MAXSIZE)
13             return ERROR;            //说明栈2已经是空栈,溢出
14         *e = s->data[s->top2++];     //将栈2的栈顶元素出栈
15     }
16     return OK;
17 }

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LinkedList实现原理分析(Java源码剖析)

Java中的LinkedList类实现了List接口和Deque接口,是一种链表类型的数据结构,支持高效的插入和删除操作,同时也实现了Deque接口,使得Lin...

863
来自专栏张俊红

数据结构-栈和队列

我们把类似于弹夹那种先进后出的数据结构称为栈,栈是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的...

1162
来自专栏拭心的安卓进阶之路

Java 集合深入理解(8):AbstractSequentialList

今天有点无聊,来学学 AbstractSequentialList 解解闷 吧! AbstractSequentialList 没有什么特别的,这里介绍是为了...

2186
来自专栏haifeiWu与他朋友们的专栏

死磕Java之聊聊LinkedList源码(基于JDK1.8)

我们主要看研究一下下面的几个方法,LinkedList其他方法都是通过调用这几个方法来实现功能,包括LinkedList的双端队列的方法也是。

1334
来自专栏文武兼修ing——机器学习与IC设计

栈与栈的实现栈栈的基本操作栈的实现

栈 栈是一种基础的数据结构,只从一端读写数据。基本特点就”后进先出“,例如顺序入栈1,2,3,4,5,再顺序出栈是5,4,3,2,1 栈的基本操作 栈的基本操作...

3225
来自专栏mathor

LeetCode78.子集

 dfs经典题,对每一个数字都有一个boolean数组去对应,没选过就是false,选过就是true,在边界条件中进行枚举,将所有结果为true的下标对应的数值...

1971
来自专栏LinkedBear的个人空间

设计模式笔记(五)——代理模式 原

通过实现一个与被代理对象的类相同的接口,完成被代理对象的实际方法调用。(接口性多态)

773
来自专栏老马说编程

(39) 剖析LinkedList / 计算机程序的思维逻辑

上节我们介绍了ArrayList,ArrayList随机访问效率很高,但插入和删除性能比较低,我们提到了同样实现了List接口的LinkedList,它的特点与...

2118
来自专栏小灰灰

JDK容器学习之LinkedList:底层存储&读写逻辑

LinkedList的底层结构及读写逻辑 链表容器,通常适用于频繁的新增删除,遍历的方式访问数据元素的场景 LinkedList 底层数据结构为链表,非线程安...

2008
来自专栏CSDN技术头条

Java中的十个“单行代码编程”(One Liner)

本文列举了十个使用一行代码即可独立完成(不依赖其他代码)的业务逻辑,主要依赖的是 Java8 中的 Lambda 和 Stream 等新特性以及 try-wit...

1493

扫码关注云+社区

领取腾讯云代金券