Hexo
0%

栈

Posted on Edited on In

什么是栈？

[TOC]

一、栈的基本概念

1.栈的定义

**栈(stack)**是一种线性表，这种线性表只在一端进行插入或者删除。可以形象地理解为平时吃的罐装的乐事薯片，只能从开口拿出或者放入薯片。

栈又称为后进先出(Last In Frist Out)的线性表，简称LIFO结构

**栈顶(top)**：线性表允许插入的那一端。

**栈底(bottom)**：不允许插入和删除的那一端，与栈顶相对。

2.栈的常见基本操作

·InitStack(&S)：初始化一个空栈S。

·StackEmpty(S)：判断一个栈是否为空，若为空则返回true否则返回false

·Push(&S,x)：进栈(栈的插入操作)，若栈未满则将x加入使之成为新栈顶

·pop(&S,&x)：出栈(栈的删除操作)，若栈S非空，则弹出栈顶元素，

·GetTop(S,&x)：读取栈顶元素，若栈S非空，则用x返回栈顶元素。

·DestroyStack(&S)：栈销毁，并释放S所占用的空间。(‘’&”表示引用调用)

二、栈的顺序储存结构

我们可以通过代码实现栈的插入、删除、判断栈是否为空、为满

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
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
}Stack;

// 初始化栈
void initStack(Stack *stack) {
    stack->top = -1;
}

// 检查栈是否为空
int isEmpty(Stack *stack) {
    return stack->top == -1;
} 

// 检查是否栈满
int isFull(Stack *stack) {
    return stack->top == MAX_SIZE -1;
}

// 入栈
void push(Stack *stack, int value) {
    if (isFull(stack)) {
        printf("栈已经满，无法入栈\n");
        return ;
    }
    stack->data[++stack->top] = value;
}

// 出栈
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("栈空，无法出栈\n");
        exit(1);
    }
    return stack->data[stack->top--];
}

// 获取栈顶元素
int top(Stack *stack) {
    if (isEmpty(stack)) {
        printf("栈空，无法获取栈顶元素\n");
        exit(1);
    }
    return stack->data[stack->top];
}
         
// 写个简单的函数测试一下
int main() {
    Stack s1;
    push(&s1, 10);
    push(&s1, 20);
    push(&s1, 30);
    push(&s1, 40);
    push(&s1, 50);
    int topele;
    for (int i = 0; i < 5; i++) {
        topele = top(&s1);
        pop(&s1);
        printf("%d ", topele);
    }
    printf("\n");
}

根据顺序栈容量(数组大小)是否可以根据需要进行扩展，可以分为静态顺序栈和动态顺序栈。

A.静态顺序栈

不能根据需要增大栈的存储空间；

==静态数组arr一旦创建就无法改变大小(n)！==

  • 实现方法:采用静态一维数组: T arr[n];

image-20240415192345007

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
//定义静态栈
typedef struct sqstack{
    ElemType stack_array[STACK_SIZE];  //静态数组
    int top;  //栈顶指针
    int bottom;  //栈底指针
}SqStack;


//初始化静态栈
SqStack Init_Stack(){
    SqStack S;
    //S.top = 0
    S.bottom = S.top = 0;  //栈底不一定要为0
    return(S);
}


//入栈，使数据元素e进栈成为新的栈顶
Status push(SqStack &S, ElemType e){
    if(S.top == STACK_SiZE - 1){  //栈满，返回错误标志
        return ERROR;
    }
    
    //方式1:空出a[0]的栈
    S.top ++;  //栈顶指针+1
    S.stack_array[S.top] = e;  //成为新的栈顶
    
    //方式2:空出a[n-1]的栈
    S.stack_array[S.top] = e;  //成为新的栈顶
    S.top ++;  //栈顶指针+1
    
    return OK;    //压栈成功
}


//出栈，弹出栈顶元素
Status pop(SqStack &S, ElemType *e){
    if(S.top == S.bottom){  //栈空，返回错误标志
        return ERROR;
    }
    
    //方式1:空出a[0]的栈
    *e = S.stack_array[S.top];
    S.top --;
    
    //方式2:空出a[n-1]的栈
    //S.top--;
    //*e = S.stack_array[S.top];
    
    return OK;
}

B.动态顺序栈

可以根据需要增大栈的存储空间；

  • 实现方法:采用动态一维数组:T *P = new T[n];

image-20240415192813256

==事实上，不管是静态|动态数组，空间一经分配，都无法更改大小！==

==只是动态数组由指针指向，程序后台帮助实现了[原数组.信息]的拷贝/迁移！==

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
61
62
63
64
65
66
67
68
69
70
71
72
73
//定义动态栈  - 由bottom指针标识此栈！
typedef struct sqstack{
    ElemType *bottom;   //栈底指针
    ElemType *top;  //栈顶指针
    int stacksize;  //当前已分配空间,以元素个数为单位
}SqStack;

//初始化动态栈
Status Init_Stack(SqStack &S, int n){
    S.bottom = new ElemType[n];  //动态分配内存空间
    //S.bottom = (ElemType *)malloc(sizeof(ELemType)*n);  //动态分配内存方式
    
    if(!S.bottom){  //内存分配不成功
        return ERROR;
    }
    
    S.top = S.bottom;  //初始时刻，栈顶和栈底指针相同
    S.stacksize = n;
    return OK;  //初始化成功
}

//入栈，使数据元素e进栈成为新的栈顶
Status push(SqStack &S, ElemType e){
    if((S.top - S.bottom) >= S.stacksize - 1){  //栈满，追加存储空间
        //C
        //S.bottom = (elemType *)realloc(size(ElemType)*(S.stacksize + STACK_INCREMENT));
        
        //C++
        //ElEmType temp = S.bottom;  //保留扩容前的数组
        //S.bottom = new ElemType[S.stacksize + STACK_INCREMENT];  //扩容
        //执行(b)
        //然后将原数组[temp]中的东西拷贝到新数组[S.bottom]
        //最后，删除原数组[temp]
        
        //(b)内存空间分配不成功
        if(!S.bottom){
            return ERROR;
        }
        
        //更新栈顶指针
        S.top = S.bottom + S.stacksize;
        
        //更新栈的大小
        S.stacksize += STACK_INCCREMENT;
    }
    
    //方式1:空出a[0]的栈
    //S.top++;  //栈顶指针加1
    //*S.top = e;  //成为新的栈顶
    
    //方式2:空出a[n-1]的栈
    //*S.top = e;  //成为新的栈顶
    //S.top++;栈顶指针加1
    
    return OK;  //压栈成功
}

//出栈，弹出栈顶元素
Status pop(SqStack &S, ElemType *e){
    if(S.top <= S.bottom){  //栈空，返回错误标志
        return ERROR;
    }
    
    //方式1:空出a[0]的栈
    *e = *S.top;
    S.top --;
    
    //方式2:空出a[n-1]的栈
    //S.top --;
    //*e = *S.top;
    
    return OK;
}

三、共享栈

当我们需要用多个栈存放相同类型的数据的时候，容易会出现栈未满的情况，造成空间的浪费。共享栈就能很好的解决这个问题

概念

利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置再共享栈的两端，两个栈顶向中间延伸。如图所示：

在这里插入图片描述

需要注意的是，top0=-1的时候1号栈为空，而top1=MaxSize1号栈为空；当两个栈的栈顶指针相邻，即top0+1=top1，栈满。对于0号栈来说，进栈的时候，top0先加1再赋值，出栈时先赋值后-1；对于1号栈来说，进栈的时候top1减1再赋值，出栈时先赋值后加。(具体课参考下面代码）

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
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 50
typedef int ElemType;
typedef struct{
	ElemType data[MAXSIZE];
	int top0;//0号栈的栈顶指针 
	int top1;//1号栈的栈顶指针 
}sqDoubleStack;

//初始化共享栈
void initSqDoubleStack(sqDoubleStack *s){
	s->top0 = -1;
	s->top1 = MAXSIZE;
} 

//共享栈进栈
Status Push(sqDoubleStack *s,Elemtype e,int stackNumber){ 
	//将e推入双栈sqDoubleStack中指定的栈stackNumber中。sq是结构体，储存两个站的相关信息；Elemtype是元素的数据类型；stackNumber表示要操作哪一个栈(0表示栈0，1表示栈1)
	if(s->top0+1 == s->top1){  //先判断是否栈满 
		return error;
	}
	if(stackNumber == 0){   //栈0有元素进栈 
		s->data[++s->top0] = e;  //若栈0则先top0+1再给数组元素赋值 
	}else if(satckNumber == 1){
		s->data[--s->top1] = e;  //若栈1则先top1-1再给数组元素赋值 
	}
	return OK; 
}

//共享栈出栈
//若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回error 
Status pop(SqDoubleStack *s,ElemType *e, int stackNumber){
	if(stackNumber == 0){
		if(s->top0 == -1){
			return error;  //说明栈0已经是空栈，溢出 
		}
		*e = s->data[s->top0--]; //将栈0的栈顶元素出栈，随后栈顶指针-1 
	}else if(stackNumber == 1){
		if(s->top1 == MAXSIZE){
			return error;  //说明栈1是空栈，溢出 
		}
		*e = s->data[s->top1++];  //将栈1的栈顶元素出栈，随后栈顶指针+1 
	}
	return OK;
}

四、栈的链式存储结构

1、链栈

采用链表的存储的栈为链栈，链表的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有的操作都是在单链表的表头进行的。这里规定链栈没有头节点，Lhead指向栈顶元素，如图所示。

在这里插入图片描述

当栈空的时候，即栈顶没有元素，所以头指针指向空，就是top = NULL的时候

链栈结构代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 50
typedef int ElemType;
//栈链式存储结构
//构造节点
typedef struct StackNode{
    ElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPrt;
//构造链表
typedef struct LinkStack{
    LinkStackPrt top;
    int count;
}LinkStack;

2、链表的基本算法

(1)链表的进栈

在这里插入图片描述

用代码实现，如下：

1
2
3
4
5
6
7
8
9
//插入元素e为新的栈顶元素
Status Push(LinkStack *s,ElemType e){
    LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));
    p->data = e;
    p->next = s->top;  //把当前的栈顶元素赋值给新节点的直接后继
    s->top = p;  //把新的节点s赋值给栈顶指针
    s->count++;
    return OK;
}

同理，出栈：

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
//若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回error
Status pop(LinkStack *s,ElemType *e){
    LinkStackPtr p;
    if(StackEmpty(*s)){
        return error;
    }
    *e = s->top->data;
    p = s->top;  //将栈顶节点赋值给p
    s->top = s->top->next;  //使得栈顶指针下移一位，指向后一节点
    free(p);  //释放节点p
    s->count--;
    return OK;
}

五、栈的应用