数据结构中栈的实现以及其基本操作

梦里梦外; 2022-08-14 01:38 155阅读 0赞

栈和队列是两种特殊的线性表，它们限定只能在表的一端进行删除、插入元素等运算。对于栈，通常称固定插入、删除的一端为栈顶（Top），而另一端称为栈底（Bottom）。位于栈顶和栈低的元素分别称为顶元和底元。当表中没有元素时，则称为空栈。由于栈只能在栈顶进行操作，因此栈遵循后进先出的原则，栈又被称为后进先出表（LIFO——Last In First Out）。在计算机程序设计中，函数的嵌套调用和递归调用时借用栈来控制返回地址的。

栈和线性表类似，也可以利用动态数组来进行描述顺序栈的存储结构，如下所示：

#define stack_init_size 100
    #define stackincrement	10
    #define elementype	int
    
    typedef	 struct sqstack
    {
    	elementype	*base;		//栈底指针;
    	elementype	*top;		//栈顶指针;
    	int		stacksize;	//当前已分配的空间，以栈元素个数为单位；
    } sqstack;

1、栈的初始化是在内存中动态分配一块连续的存储区域，并且指定栈顶指针top与栈底指针base相等。栈顶指针top始终比顶元超前一个位置，因此栈满的条件是

top-base=stacksize。栈的初始化函数如下：

//构造空栈;
    int stackInit(sqstack &s)
    {
    	s.base=(elementype*)malloc(stack_init_size*sizeof(elementype));
    
    	if(!s.base)
    	{
    		return 0;
    	}	
    
    	s.top=s.base;
    	s.stacksize=stack_init_size;
    	return 1;		
    }

2、栈顶取元素，由于栈的top指针超前顶元，故栈顶取元素取得是栈顶指针指向的下一个元素，如下：

//从栈顶取元素;
    int getTop(sqstack& s,elementype &e)
    {
    	if(s.base==s.top)		//栈为空;
    	{
    		return 0;
    	}
    
    	e=*(s.top-1);
    
    	return 1;
    }

3、插入元素，栈中插入一个元素，是把元素插入到栈顶，并且栈顶指针top需要向上偏移，如果已经是满栈，则需要再次申请内存，以防止栈顶溢出的情况发生。如下：

//插入元素;
    int push(sqstack &s,elementype e)
    {
    	int size=s.top-s.base;
    
    	if((s.top-s.base)>=s.stacksize)  //若栈满，则追加存储空间;
    	{
    		s.base=(elementype*)realloc(s.base,(s.stacksize+stackincrement)*sizeof(elementype));
    		if(!s.base)
    		{
    			return 0;
    		}
    
    		s.top=s.base+s.stacksize*sizeof(elementype);
    		s.stacksize+=stackincrement;
    	}
    
    	*(s.top++)=e;
    	return 1;
    }

4、删除元素，删除元素则需要把栈顶指针向下偏移。

int Pop(sqstack&s,elementype& e)
    {
    	if(s.top==s.base)
    	{
    		return 0;
    	}	
    
    	e=*(--s.top);
    
    	return 1;
    }

5、判断栈是否为空，只需要判断栈顶指针是否和栈底指针相等即可。

//判断栈是否为空;
    int stackempty(sqstack s)
    {
    	if(s.base==s.top)
    	{
    		return 1;
    	}
    	return 0;	
    }

6、清空栈，只需设置栈顶指针与栈底指针相等即可。

//清空栈;
    void stackclear(sqstack &s)
    {
    	s.top=s.base;
    }