算法数据结构栈

数据结构-栈

4FGR2025-01-072025-01-07

前情提要: 数据结构-线性表 | 4FGR の Blog

参考资料: 数据结构与算法分析 –Mark Allen Weiss

栈模型

栈是限制在插入和删除在末端的线性表，这决定了它的特性是”后进先出”(LIFO)。在解决一些问题时，我们很容易想到通过栈这种结构来解决，例如，对多项式的求解。

对于栈而言，基本的操作是Pop和Push,尽管有时通过Top返回栈顶元素的值。

注意：栈顶元素是栈中唯一可见的元素。

栈的实现

由于栈是一个表，因此任何实现表的方法都可以实现栈，这里给出两种方法：

栈的数组实现

为了讲解的便利和简洁，这里我们通过静态数组的方式实现，大家可以自己实现下动态分配的方法。

定义

#define MAXSIZE 1000

typedef struct {
    int data[MAXSIZE];
    int top;
}*stack;

基本操作

void initialStack(stack s){
    s->top = -1; //置空
}

bool isEmpty(stack s){ //判断栈是否为空
    return s->top == -1;
}

bool isFull(stack s){   //判断栈是否满
    return s->top == MAXSIZE-1;
}

void Pop(stack s, int &e){ //出栈
    if(isEmpty(s)) {
        printf("栈空\n");
        exit(1);
    }
    else
    e = s->data[s->top--];
}

void Push(stack s, int e){ //入栈
    if(isFull(s)){
        printf("栈满\n");
        exit(1);
    }
    else
    s->data[++s->top] = e;
}

void GetTop(stack s, int &e){ //取栈顶元素
    if(isEmpty(s)){
        printf("栈空\n");
        exit(1);
    }
    else
    e = s->data[s->top];
}

栈的链表实现

链式栈的实现更加灵活，不用像顺序栈被空间所束缚。

定义

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

基本操作

void initialStack(stack &s){
    s = (stack)malloc(sizeof(StackNode));
    s->next = NULL; 
}

bool isEmpty(stack s){
    return s->next == NULL; 
}

void Push(stack s, int e){
    StackNode *p = (StackNode*)malloc(sizeof(StackNode));
    p->data = e;
    p->next = s->next;
    s->next = p;
}

void Pop(stack s, int &e){
    if(isEmpty(s)){
        printf("栈空\n");
        exit(1);
    }
    StackNode *p = s->next;
    e = p->data;
    s->next = p->next;
    free(p);
}

void GetTop(stack s, int &e){
    if(isEmpty(s)){
        printf("栈空\n");
        exit(1);
    }
    e = s->next->data;
}