栈·初识入门

今天药忘吃喽~ 2024-04-03 09:11 140阅读 0赞

#### 文章目录 ####

*  栈
 *   *  概念
     *  顺序栈
     *   *  有关top指针的位置·设定
         *  常见操作
         *   *  初始化
             *  销毁
             *  入栈
             *  出栈
             *  获取栈顶
             *  求栈的长度
             *  判空
     *  链栈【具体操作先省略】
     *   *  设定
         *  说明
 *  顺序栈和链栈的比较。

## 栈 ##

![在这里插入图片描述][1bf87ac99d1f4fd2aee0e8a06e148b70.png]

### 概念 ###

*  栈：
    
     *  ***一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。***
     *  ***进行数据插入和删除操作的一端。称为栈顶，另一端称为栈底。***
     *  ***栈中的数据元素遵守后进先出LIFO（Lastin FirstOut）的原则。***
     *  ***压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶***
     *  ***出栈：栈的删除操作叫做出栈。出数据也在栈顶***
     *  可通过顺序表或者链表实现。  
        ![在这里插入图片描述][ad4c74e7135e40f68b63ef05318a8f62.png]

### 顺序栈 ###

#### 有关top指针的位置·设定 ####

*  如果初始化时，top指向的是0【数组的首地址】，意味着top指向栈顶数据的下一个。
 *  如果初始化时，top指向的是-1【数组的首地址的前一个地址】，意味着top指向栈顶数据。
 *  当然，top还有第三种的设定，使用两个指针base、top同时指向数组的首地址。  
    ![在这里插入图片描述][a0a1ec149be54d77912fecffcf11666a.png]

#### 常见操作 ####

*  定义的结构体

typedef int STDataType;
    typedef struct  Stack
    {
        
    	STDataType* a;
    	int top;
    	int capacity;
    } ST;

##### 初始化 #####

*  初识的top设定：top指向栈顶数据的下一个

void StachInit(ST* ps);

void StachInit(ST* ps) {
        
    	assert(ps);
    	ps->a = NULL;
    	ps->top = 0;
    	ps->capacity = 0;
    }

##### 销毁 #####

void StackDestroy(ST* ps);

void StackDestroy(ST* ps) {
        
    	assert(ps);
    	free(ps->a);
    	ps->a = NULL;
    }

##### 入栈 #####

void StackPush(ST* ps,STDataType x);

void StackPush(ST* ps, STDataType x) {
        
    	assert(ps);
    	//判断是否为空
    	if (ps->top == ps->capacity) {
        
    		//设置初始的长度为4，否则长度变原来的2倍
    		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    		//开辟空间
    		STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType)*newCapacity);
    		if (tmp == NULL) {
        
    			cout << "realloc fail\n" ;
    		}
    		//更新数组的地址、容量
    		ps->a = tmp;
    		ps->capacity = newCapacity;
    	}
    	//入栈 先入数据，后改变指针
    	ps->a[ps->top] = x;
    	ps->top++;
    }

##### 出栈 #####

void StackPop(ST* ps);

void StackPop(ST* ps) {
        
    	assert(ps);
    	assert(!StackEmpty(ps));
    	ps->top--;
    }

##### 获取栈顶 #####

STDataType StackTop(ST* ps);

STDataType StackTop(ST* ps) {
        
    	assert(ps);
    	assert(!StackEmpty(ps));
    	return ps->a[ps->top - 1];
    }

##### 求栈的长度 #####

int StackSize(ST* ps);

int StackSize(ST* ps) {
        
    	assert(ps);
    	return ps->top;
    }

##### 判空 #####

bool StackEmpty(ST* ps);

bool StackEmpty(ST* ps) {
        
    	assert(ps);
    	return ps->top == 0;
    }

### 链栈【具体操作先省略】 ###

#### 设定 ####

![在这里插入图片描述][e01c80d765824fc8983584a380707463.png]![在这里插入图片描述][682346e029094f2baf91811124ca12bd.png]

#### 说明 ####

① ***链栈不必设头结点，因为栈顶（表头）操作频繁，只在栈顶插入和删除，不在其他位置插入和删除，代码统一***；  
② ***采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。***

## 顺序栈和链栈的比较。 ##

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>顺序栈</th> 
   <th>链栈</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>时间性能</td> 
   <td>相同，都是常数时间O(1)。</td> 
   <td>相同，都是常数时间O(1)。</td> 
  </tr> 
  <tr> 
   <td>空间性能</td> 
   <td>有元素个数的限制和空间浪费的问题。</td> 
   <td>没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。【开辟节点也会产生消耗】</td> 
  </tr> 
 </tbody> 
</table>

*  总结：***当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。***

[1bf87ac99d1f4fd2aee0e8a06e148b70.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/314b68ec54bb439d850c520d8a862cfc.png
[ad4c74e7135e40f68b63ef05318a8f62.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/865700dd19ba49279226f7c4871d7a79.png
[a0a1ec149be54d77912fecffcf11666a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c85439309d0441d3b9a0fa61ef480ad7.png
[e01c80d765824fc8983584a380707463.png]: https://img-blog.csdnimg.cn/e01c80d765824fc8983584a380707463.png
[682346e029094f2baf91811124ca12bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/70f2b121297d41488e0ea4dd8e24b1df.png