【数据结构】顺序栈及其基本操作

顺序栈

栈是一种数据结构，其主要特点是后进先出，相当于我们在瓶子里面放东西，后放进去的东西在上面，所以拿出来的时候自然是从上面取出来，所以后进去的先出来。
本文主要介绍的是栈的数组实现方法，即顺序栈。

目录：

• 顺序栈
  • 1. 栈的数组实现（创建）
    • 1.1. 栈的初始化
    • 1.2. 栈的增加（压栈）
    • 1.3. 栈的删除（弹栈）
    • 1.4. 栈的查询
    • 1.5. 栈的判空和判满

基本操作有以下几种：

1. 栈的数组实现（创建）

栈的数组实现起来相对简单。在定义的时候，我们只需要定义一个结构体即可

#define MAXSIZE 10000
typedef struct
{
    char data[MAXSIZE]; // 创建最大长度的数组
    int top;          // 当前顶部元素的位置
} Stack;
1
2
3
4
5
6

栈的结构体中需要一个数组来存储元素，还需要一个变量来记录当前栈顶元素的位置。

1.1. 栈的初始化

栈的初始化只需要让top为-1即可。

void InitStack(Stack &S)
{
    S.top = -1;
}
1
2
3
4

1.2. 栈的增加（压栈）

压栈即将元素压入栈中，压栈的时候，我们需要给函数传递需要压栈的元素和栈本身。

在压栈之前我们还需要判断栈是否已经满，若未满即可进行压栈。

在压栈的过程中我们需要让top加一，即让栈顶元素的位置加一，然后让新的元素赋值到新的数组的top位置上。

void Push(Stack &S,char x)
{
    if(S.top==MAXSIZE-1)
    {
        printf("栈已满，无法插入元素！\n");
        return;
    }
    S.top++;
    S.data[S.top]=x;
}
1
2
3
4
5
6
7
8
9
10

1.3. 栈的删除（弹栈）

当我们需要弹栈的时候，只需要返回数组top位置的元素，然后让top减一即可。

int Pop(Stack &S)
{
    if(S.top!=-1)
    {
        return S.data[S.top--];
    }
}
1
2
3
4
5
6
7

1.4. 栈的查询

由于栈的特性，我们在查询的时候一般查询栈的栈顶元素。当我们需要查询栈顶元素的时候，只需要返回数组top位置的元素即可。如果需要对栈的其他元素进行查询，需要逐个遍历。

int GetTop(Stack S)
{
    if(S.top!=-1)
    {
        return S.data[S.top];
    }
}
1
2
3
4
5
6
7

1.5. 栈的判空和判满

栈的判空和比较简单，在判空时只需要判断top是否等于-1即可，在判满的时候只需要判断top是否等于MAXSIZE-1即可。

bool StackEmpty(Stack S)
{
    if(S.top==-1)
    {
        return true;
    }
}
1
2
3
4
5
6
7

bool StackFull(Stack S)
{
    if(top==MAXSIZE-1)
    {
        return true;
    }
}
1
2
3
4
5
6
7