【数据结构】如何通过数组模拟实现栈

旧城等待， 2022-11-14 10:29 169阅读 0赞

## 前言 ##

对其他数据结构的定义，如读者有需要，请查阅：

链表：https://blog.csdn.net/qq\_45690050/article/details/115265083?spm=1001.2014.3001.5501

## 1. 栈的定义 ##

不同于数组，栈是一种先进后出（FILO）的数据结构。即：先进到栈中的元素后弹出。根据这条定义，我们可以设计我们的ADT：

typedef struct {
        
    	ElementType data[length];
    	int top;
    }Stack;

其中，`data`为`ElementType`类型的数组，length表示所定义的栈的长度；  
`top`为`int`类型的变量，用于指向栈顶元素，即用整型变量模拟栈顶指针；  
`Stack`则为我们用于声明ADT的抽象数据类型

## 2. 初始化栈 ##

初始化栈的操作主要有两步：

1.  创建一个空栈对象，待使用；
2.  初始化栈顶指针

如下：

void init(Stack *&s){
        
    	s = new Stack;
    	s->top = -1;
    }

这里将栈顶指针初始化为1主要是为了体现栈的**空**，因为下标是从0开始的，一旦有元素进入，该元素的下标就为0，初始化为0显然不太合适

## 3. 入栈和出栈 ##

栈的重要操作主要就是入栈和出栈操作，这里将两者放在同一章内讲解是因为其比较相似

### 3.1 入栈 ###

入栈，顾名思义就是向栈内压入元素，入栈操作同样通过循环进行：

#define MAXSIZE 100
    
    bool push(Stack *&s, ElementType e){
        
    	if(s->top==MAXSIZE-1){
        
    		return false;
    	}
    	s->top +=1;
    	s->data[s->top] = e;
    	return true;
    }

这里我将本方法的返回值类型定义为布尔类型的原因为：用于确定本次操作是否成功。成功与否的判断标准则为**元素入栈时栈是否已满**。如果满了，元素肯定是不能入栈的，则代表本次入栈操作失败；反之亦然。

这里设计得很巧妙地一点是，利用栈顶指针自增1（这里我写的是+=的形式，其实top++和++top在这里效果相同），指向待插入位置的下标。

### 3.2 出栈 ###

出栈则是将栈顶的元素弹出，如果有需要可以将其弹出至栈空。

ElementType pop(Stack *&s){
        
    	if(s->top==-1){
        
    		return ;
    	}
    	ElementType tmp = s->data[s->top];
    	s->top -= 1;
    	return tmp;
    }

出栈操作不仅要做到将其弹出，还要做到返回栈顶元素。这里用临时变量存储栈顶元素（即待弹出元素），待栈顶指针下降1后弹出；若栈顶指针指向-1，则说明此时栈**已空**。

## 4. 关于链栈 ##

上课时老师可能会讲到链栈这个概念，即每个栈空间的内存地址分配不是连续的。是的，其实链栈就是链表，只不过你需要一个操作叫**快慢指针**。

注：这里说的链表不是单链表，而是双链表，便于栈顶指针的移动。关于双链表，之后我会另发布一篇新文章来讲解

发表评论取消回复

表情：

评论列表（有 0 条评论，169人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构之模拟栈

package com.qiangqiang.stack; public class Stack<T> { //采用链表来实现

不念不忘少年蓝@/ 2023年01月01日 08:00/ 0 赞/ 123 阅读

相关【数据结构】如何通过数组模拟实现栈

前言对其他数据结构的定义，如读者有需要，请查阅：链表：https://blog.csdn.net/qq\_45690050/article/details/1152

旧城等待，/ 2022年11月14日 10:29/ 0 赞/ 170 阅读

相关【数据结构】一个数组实现两个栈

面对这个问题，我首先想到的是将一个数组的空间一分为二来为两个栈使用。可以将一个栈的底设在数组的起始位置，另一个栈的底设在数组的中间位置。但是这样并不能有效地利用数组的空间，比如

╰+哭是因爲堅強的太久メ/ 2022年09月27日 14:22/ 0 赞/ 182 阅读

相关【数据结构】栈的数组实现

1.栈的顺序存储实现构建结构体Stack，其中数组Date存放栈中数据，Top存放栈顶元素的下标。对栈进行初始化时将Top赋值为-1，表示栈为空。MaxSize为栈的最大

傷城~/ 2022年09月27日 13:28/ 0 赞/ 173 阅读

相关数据结构--＞栈－数组实现

数据结构—>栈栈同样也是有序表，但是插入，删除操作限定在表的同一端，向栈里添加元素的操作称为入栈`push`，从栈里面删除元素的操作称为出栈`pop`；当

我不是女神ヾ/ 2022年06月07日 11:30/ 0 赞/ 214 阅读

相关结构体模拟实现栈

栈是很基本也很重要的数据结构，这里通过结构体模拟实现顺序栈，使用上节的顺序表实现，还有链栈（使用链表），本篇仅包含顺序栈的实现。我们知道C++的STL中有对栈的实现，直接提供了

比眉伴天荒/ 2022年05月28日 13:06/ 0 赞/ 196 阅读

相关数据结构之栈的数组实现

\栈的特点：\ 1.栈是一种线性的数据结构，相比于数组，栈的操作是数组的子集； 2.栈只能从一端添加元素，也只能从一端删除元素，添加元素的操作叫做进栈（void pus

向右看齐/ 2022年05月25日 09:48/ 0 赞/ 206 阅读

相关 java: 数据结构--栈(数组)

栈: 规则\[ 先进来的数据, 必须最后出来\] 实现方式: ==> 新的数据, 追加到数组后面, 取数据时, 从最后的索引开始

怼烎@/ 2022年05月20日 02:39/ 0 赞/ 193 阅读

相关数据结构==基于数组实现栈

一、[自定义动态数组][Link 1] 二、定义Stack接口 public interface Stack<E> { /

迈不过友情╰/ 2022年03月28日 15:19/ 0 赞/ 216 阅读

相关数据结构之数组实现栈

栈描述栈，先进后出（Last In First Out） ,它是一种只能在表尾进行插入和删除的特殊线性表。由于栈是一个表，所以数组和链表都可以实现一个栈，数组是一

喜欢ヅ旅行/ 2022年02月23日 13:16/ 0 赞/ 209 阅读