HOME

堆栈操作的存储结构

引言

堆栈是一种线性数据结构，它遵循后进先出（LIFO）的原则进行操作。在计算机科学中，堆栈被广泛应用于多种场景，如函数调用、表达式求值等。本文将深入探讨堆栈的基本概念及其常见的存储结构，包括顺序存储和链式存储。

基本概念

后进先出原则

堆栈的核心特点是后进先出（LIFO），即最晚进入堆栈的数据元素会最先被移除。这种特性使得堆栈非常适合解决需要逆序处理的问题。

主要操作

堆栈的基本操作包括：

常见存储结构

顺序存储结构

顺序存储结构通过数组来实现堆栈。在数组中，每个元素都分配一个固定的索引位置，并且用一个指针指向当前的堆栈顶。这种方式的优点是访问速度快，因为可以直接通过索引来获取或设置值；缺点是插入和删除操作相对复杂。

数据结构定义

typedef struct {
    int *base;  // 基地址
    int top;   // 栈顶指针
    int stacksize;  // 数组容量
} SqStack;

链式存储结构

链式存储结构使用链表来实现堆栈。每个节点包含一个数据元素和指向下一个节点的指针，最顶层的数据元素由头指针直接指向。这种方式的优势在于插入和删除操作简单快捷，不需要移动其他元素；缺点是相比顺序存储需要额外的空间来存储指针。

数据结构定义

typedef struct Node {
    int data;  // 节点数据
    struct Node *next;  // 指向下一个节点的指针
} LNode;

实现示例

顺序堆栈实现（C语言）

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

#define MAXSIZE 100

typedef struct {
    ElemType data[MAXSIZE];
    int top;
} SqStack;

// 初始化空栈
void InitStack(SqStack *S) {
    S->top = -1;
}

// 入栈操作
bool Push(SqStack *S, ElemType e) {
    if (S->top == MAXSIZE - 1)
        return false; // 栈满，无法入栈
    else {
        S->data[++S->top] = e;
        return true;
    }
}

// 出栈操作
bool Pop(SqStack *S, ElemType *e) {
    if (S->top == -1)
        return false; // 栈空，无法出栈
    else {
        *e = S->data[S->top--];
        return true;
    }
}

// 获取栈顶元素
bool GetTop(SqStack *S, ElemType *e) {
    if (S->top == -1)
        return false; // 栈空，无法获取
    else {
        *e = S->data[S->top];
        return true;
    }
}

链式堆栈实现（C语言）

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct Node {
    ElemType data;
    struct Node *next;
} LNode, *LinkStack;

// 初始化空链表
void InitList(LinkStack *L) {
    (*L) = (LinkStack)malloc(sizeof(LNode));
    if (!(*L)) exit(0);
    (*L)->next = NULL; // 链表头指针初始化为空
}

// 入栈操作
bool Push(LinkStack L, ElemType e) {
    LinkStack p = (LinkStack)malloc(sizeof(LNode));
    if (!p)
        return false; // 内存分配失败，无法入栈
    p->data = e;
    p->next = L->next;
    L->next = p;
    return true;
}

// 出栈操作
bool Pop(LinkStack *L, ElemType *e) {
    LinkStack p;
    if ((*L)->next == NULL)
        return false; // 栈空，无法出栈
    else {
        p = (*L)->next;
        *e = p->data;
        (*L)->next = p->next;
        free(p);
        return true;
    }
}

// 获取栈顶元素
bool GetTop(LinkStack L, ElemType *e) {
    if (L->next == NULL)
        return false; // 栈空，无法获取
    else {
        *e = L->next->data;
        return true;
    }
}

结语

堆栈作为一种重要的数据结构，在实际应用中有着广泛的应用。选择合适的存储结构可以有效提高算法的效率和性能。无论是顺序存储还是链式存储，都可以根据具体需求进行优化设计。