栈

数据结构 › C
,
·本篇:1.5k字 大约需要: 6分钟

前言

栈的实现及相关操作

编程语言：C

栈

栈的抽象数据类型

栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表

  • 允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈
  • 栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构
  • 栈的插入操作叫作进栈，也称压栈、入栈
  • 栈的删除操作，叫作出栈，也有的叫作弹栈

基本操作的实现

  • 结构代码
1
2
3
4
5
6
7
8
9
10
11
12
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define sf scanf
#define pf printf
#define MAXSIZE 100

typedef struct
{
    int *data;
    int top;
} SqStack;
  • 初始化一个空栈
1
2
3
4
5
void InitSqStack(SqStack *S)
{
    S->data = (int *) malloc(MAXSIZE * sizeof(int));
    S->top = -1;
}
  • 判断栈是否已满
1
2
3
4
bool Full(SqStack *S)
{
    return S->top == MAXSIZE - 1;
}
  • 判断栈是否为空
1
2
3
4
bool Empty(SqStack *S) 
{
    return S->top == -1;
}
  • 向栈中插入元素
1
2
3
4
5
6
7
void Push(SqStack *S, int target) 
{
    if(Full(S))
        pf("栈满\n");
    else
        S->data[++S->top] = target;
}
  • 删除栈顶元素
1
2
3
4
5
6
7
void Pop(SqStack *S)
{
    if(Empty(S))
        pf("栈为空\n");
    else
        S->data[S->top--] = 0;
}
  • 将栈清空
1
2
3
4
5
6
7
void ClearStack(SqStack *S)
{
    if(!Empty(S))
        for(int i = 0; i <= S->top; i++)
            S->data[i] = 0;
    S->top = -1;
}
  • 返回栈顶元素
1
2
3
4
5
6
7
8
9
int GetTop(SqStack *S)
{
    int ans = -1;
    if(Empty(S))
        pf("栈为空\n");
    else
        ans = S->data[S->top];
    return ans;
}
  • 返回栈的元素个数
1
2
3
4
int StackLength(SqStack *S)
{
    return S->top + 1;
}
  • 遍历栈中的所有元素
1
2
3
4
5
6
7
8
9
void DisplayStack(SqStack *S)
{
    if(Empty(S))
        pf("栈为空\n");
    else
        for(int i = 0; i <= S->top; i++)
            pf("%d ", S->data[i]);
    pf("\n");
}

两栈共享空间

  • 我们可以用一个数组来存储两个类型相同的栈

  • 数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为数组的末端，即下标为数组长度n - 1处，这样两个栈如果增加元素，就是两端点向中间延伸

代码实现

  • 结构代码
1
2
3
4
5
6
7
8
9
10
11
12
#include<stdio.h>
#include<stdlib.h>
#define sf scanf
#define pf printf
#define MAXSIZE 10

typedef struct
{
    int *data;
    int top1; // 栈1栈顶指针
    int top2; // 栈2栈顶指针
} SqDoubleStack;
  • 初始化两栈空间
1
2
3
4
5
6
void InitSqDStack(SqDoubleStack *S)
{
    S->data = (int *) malloc(MAXSIZE * sizeof(int));
    S->top1 = -1;
    S->top2 = MAXSIZE;
}
  • 入栈
1
2
3
4
5
6
7
8
9
void Push(SqDoubleStack *S, int target, int stackNumber) // 判断是栈1还是栈2的参数stackNumber
{
    if(S->top1 + 1 == S->top2)
        pf("栈已满\n");
    else if(stackNumber == 1)
        S->data[++S->top1] = target;
    else if(stackNumber == 2)
        S->data[--S->top2] = target;
}
  • 出栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Pop(SqDoubleStack *S, int *target, int stackNumber) // 用target返回出栈的值
{
    if(stackNumber == 1)
    {
        if(S->top1 == -1)
            pf("栈1为空\n");
        else
            *target = S->data[S->top1--];
    }
    else if(stackNumber == 2)
    {
        if(S->top2 == MAXSIZE)
            pf("栈2为空\n");
        else
            *target = S->data[S->top2++];
    }
}
  • 遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Display(SqDoubleStack *S, int stackNumber)
{
    if(stackNumber == 1)
    {
        if(S->top1 == -1)
            pf("栈1为空\n");
        else
            for(int i = 0; i <= S->top1; i++)
                pf("%d ", S->data[i]);
        pf("\n");
    }
    else if(stackNumber == 2)
    {
        if(S->top2 == MAXSIZE)
            pf("栈2为空\n");
        else
            for(int i = MAXSIZE - 1; i >= S->top2; i--)
                pf("%d ", S->data[i]);
        pf("\n");
    }
}

栈的链式存储结构及实现

  • 栈的链式存储结构，简称为链栈

  • 将栈顶放在单链表的头部，通常对于链栈来说，是不需要头结点的

  • 那么链栈的空就是top = NULL

代码实现

  • 结构代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define sf scanf
#define pf printf

typedef struct StackNode
{
    int data;
    struct StackNode *next;
} StackNode;

typedef struct LinkStack
{
    StackNode *top; // 栈顶指针
    int count;
} LinkStack;
  • 初始化链栈
1
2
3
4
5
void InitLinkStack(LinkStack *L)
{
    L->top = NULL;
    L->count = 0;
}
  • 入栈
1
2
3
4
5
6
7
8
void Push(LinkStack *L, int target)
{
    StackNode *temp = (StackNode *) malloc(sizeof(StackNode));
    temp->data = target;
    temp->next = L->top;
    L->top = temp;
    L->count++;
}
  • 出栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Pop(LinkStack *L, int *target) // 用target保存出栈元素
{
    if(StackEmpty(L))
        pf("栈为空\n");
    else
    {
        StackNode *temp;
        *target = L->top->data;
        temp = L->top;
        L->top = L->top->next;
        free(temp);
        temp = NULL;
        L->count--;
    }
}
  • 判断链栈是否为空
1
2
3
4
bool StackEmpty(LinkStack *L)
{
    return L->top == NULL;
}
  • 遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Display(LinkStack *L)
{
    if(StackEmpty(L))
        pf("栈为空\n");
    else
    {
        StackNode *p = L->top;
        while(p != NULL)
        {
            pf("%d ", p->data);
            p = p->next;
        }
        pf("\n");
    }
}

顺序栈与链栈的对比

  • 它们在时间复杂度上是一样的，均为O(1)
  • 对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便；而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制
  • 如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些

总结

  • 栈是一种特殊的线性表，可以用数组或链表来实现它，栈的入栈和出栈操作时间复杂度都是O(1)
  • 两栈共享空间这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况，这样使用两栈共享空间存储方法才有比较大的意义。否则两个栈都在不停地增长，那很快就会因栈满而溢出了
  • 链栈的操作绝大部分都和单链表类似，只是在插入和删除上，特殊一些
  • 链栈的进展push和出栈pop操作都很简单，时间复杂度均为O(1)