栈的顺序存储C实现

基本概念

  首先看一下线性表定义:线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,其中n为表长,当n==0时线性表时一个空表。

栈(Stack)只允许在一端进行插入或删除操作的线性表。也就是说这种数据结构是一种有限制的线性表,其逻辑结构与普通的线性表相同,但只允许在表头或表尾进行插入删除操作。

示意图:

 栈顶、栈底、空栈、入栈、出栈

1614085267675

 空栈:当这个栈里没有任何元素的时候为空栈.

 栈底:数据元素在栈的最底部不允许插入和删除的一端,比如图中a0元素就是在栈底的位置。

 栈顶:允许插入和删除的一端。

 入栈出栈:入栈和出栈只发生在同一端。

出入顺序

 后进后出(Last In First Out)LIFO

定义结构体

1
2
3
4
5
6
#define MaxSize 10
typedef struct
{
int data[MaxSize];
int top; // 栈顶指针,存储的是数组下标
}SqStack;

栈的初始化

 栈顶指针也就是数组下标,指向栈顶的位置。如果一开始就指向0的位置是不合理的,所以可以将其赋值未-1。当我们在判断一个栈的时候,如果其栈顶值为-1的时候,就可以确定其是一个空栈。

1
2
3
4
5
// 初始化
void initStack(SqStack& s)
{
s.top = -1;
}

栈的判空操作

1
2
3
4
5
// 判空操作 (为空返回true)
bool stackEmpty(SqStack s)
{
return s.top == -1;
}

入栈

 传入一个栈和需要入栈的元素,首先判断栈是否已满,如果该栈已满则无法完成入栈操作,返回false。

 可以通过栈顶指针来判断栈是否已满,由于结构体中是通过数组进行定义的,且数组开辟的连续空间为MaxSize个,数组下标是从0开始的,所以当栈顶指针值为MaxSize-1时,该栈已满。

 完成栈顶是否已满的判断后,栈顶指针首先指向下一个存储单元(top+1)操作,此时栈顶指针指向了需要插入数据元素的内存空间,然后进行数据赋值操作最终完成入栈。

入栈操作示意图:

image-20210306000010673

  • 入栈前:栈顶指针指向-1,表示空栈。
  • 第一次入栈:栈顶指向0,数据被放入数组data[0]中,栈顶指针指向最上方的数据地址。
  • 第二次入栈:栈顶指向1,数据被翻入数组data[1]中,栈顶指针依然指向最上方数据地址。
1
2
3
4
5
6
7
8
9
// 进栈操作
bool push(SqStack& s, int e)
{
if (s.top == MaxSize - 1)
return false; // 栈满,报错
s.top = s.top + 1;
s.data[s.top] = e;
return true;
}

出栈

 首先判断栈是否为空,为空返回false。通过引用变量&e来接收需要出栈的数据(栈顶指向的数据),此时栈顶指针因-1,当栈中所有的数据都已出栈后,栈顶指针值为-1,表示该栈为空栈

1
2
3
4
5
6
7
8
9
// 出栈操作(使用e返 回数据)
bool pop(SqStack &s, int& e)
{
if (s.top == -1)
return false; // 空栈
e = s.data[s.top];
s.top = s.top - 1;
return true;
}

读取栈顶元素

1
2
3
4
5
6
7
8
// 读栈顶元素
bool getTop(SqStack s, int &e)
{
if (s.top == -1)
return false;
e = s.data[s.top];
return true;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<stdio.h>
#include<stdlib.h>

#define MaxSize 10
typedef struct
{
int data[MaxSize];
int top; // 栈顶指针,存储的是数组下标
}SqStack;

// 初始化
void initStack(SqStack& s)
{
s.top = -1;
}

// 判空操作 (为空返回true)
bool stackEmpty(SqStack s)
{
return s.top == -1;
}

// 进栈操作
bool push(SqStack& s, int e)
{
if (s.top == MaxSize - 1)
return false; // 栈满,报错
s.top = s.top + 1;
s.data[s.top] = e;
return true;
}

// 出栈操作(使用e返 回数据)
bool pop(SqStack &s, int& e)
{
if (s.top == -1)
return false; // 空栈
e = s.data[s.top];
s.top = s.top - 1;
return true;
}

// 读栈顶元素
bool getTop(SqStack s, int &e)
{
if (s.top == -1)
return false;
e = s.data[s.top];
return true;
}


void main()
{
SqStack s;
initStack(s);
}

// 其它
// 1. 共享栈,两个栈同学同一片存储空间,两个栈从两边往中间增长

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!