栈

栈的概念

栈（stack）是一种特殊的线性表存储结构，其一端可以进行插入和弹出的操作，而另一端是封死的。

可以把栈想象成是一个柱状的容器。就比如一个乒乓球筒，我们只能在筒的一段进行乒乓球的放入和取出。

栈顶和栈的两种操作

栈顶就是栈的开口端，每次都是在栈顶处插入元素和删除元素。
（1）入栈：将新元素存入栈中，并作为新的栈顶元素；
（2）出栈：将栈顶元素弹出，并将其下面的元素作为新的栈顶元素。

栈的特性

栈有着先进先出的特性。假如入栈元素依次是 1、2、3 ，且中途没有元素出栈，那么最后所有元素出栈的顺序是 3、2、1 。

---

顺序栈

顺序栈基本概念

顺序栈是用数组来实现栈的存储结构，一般会定义一个栈顶 top，初始情况下 top 值为-1，表示栈为空，此时栈中无任何元素。
每当有元素入栈，top 就 +1 ; 有元素出栈， top 就 -1 。

顺序栈的入栈操作

顺序栈入栈操作图解

初始情况下的栈

元素1入栈

元素2入栈

元素3入栈

顺序栈入栈操作代码

//元素入栈
void push(SqStack *s, Elemtype x){
    if(s->top == MAXSIZE - 1) return;  //栈满
    s->data[++s->top] = x;
}

---

顺序栈的出栈操作

顺序栈出栈操作图解

元素3出栈

元素2出栈

元素1出栈

顺序栈出栈操作代码

//元素出栈
void pop(SqStack *s, Elemtype *x){
    if(s->top == -1) return;  //栈空
    *x = s->data[s->top--];
}

---

顺序栈完整程序

源代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1000

typedef int Elemtype;
typedef struct{

    Elemtype data[MAXSIZE];
    int top;                //栈顶指针

}SqStack;

//初始化栈
void Init_SqStack(SqStack *s){
    s->top = -1;
}

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

//元素入栈
void push(SqStack *s, Elemtype x){
    if(s->top == MAXSIZE - 1) return;
    s->data[++s->top] = x;
}

//元素出栈
void pop(SqStack *s, Elemtype *x){
    if(s->top == -1) return;
    *x = s->data[s->top--];
}

//取栈顶元素
Elemtype top(SqStack *s){
    if(IsEmpty(s)){
	printf("栈为空\n");
	return -1;
    }
    return s->data[s->top];
}

int main(){
    SqStack mystack;
    Init_SqStack(&mystack);

    for(int i = 1; i <= 5; i++)
	push(&mystack, i);
    printf("当前栈顶元素为: %d\n", top(&mystack));

    int e;
    pop(&mystack, &e);
    printf("出栈元素为: %d\n", e);
    printf("当前栈顶元素为: %d\n", top(&mystack));

    printf("全部元素出栈：\n");
    while(!IsEmpty(&mystack)){
    	printf("%d ", top(&mystack));
    	pop(&mystack, &e);
    }
}

顺序栈运行测试

---

链栈

链栈基本概念

链栈是用链式存储结构实现的，在实现过程中，需要定义一个 top 指针保持指向当前栈顶。操作过程和链表有些相似。

链栈的入栈操作

链栈入栈操作图解

初始情况下的链栈

元素1入栈

元素2入栈

元素3入栈

链栈入栈操作代码

//入栈
void LinkStack_push(LinkStack *S, ElemType e){
    LinkStacknode *node;            
    node = (LinkStacknode *) malloc(sizeof(LinkStack));
    node->data = e;            
    node->next = S->top;       //新节点的next指向此时的top
    S->top = node;             //top指针指向新的节点

    S->length++;
}

---

链栈的出栈操作

链栈出栈操作图解

元素3出栈

元素2出栈

元素1出栈

链栈出栈操作代码

//出栈
void LinkStack_pop(LinkStack *S, ElemType *e){
    if(IsEmpty(S))               //栈空
        return;                  
    LinkStacknode *del = S->top; 
    *e = del->data;              
    S->top = del->next;          //top跳过出栈节点，指向出栈节点的下一节点

    S->length--;
    free(del);                   //释放内存
}

---

链栈完整程序

源代码

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

//定义数据类型
typedef int ElemType;

//链栈的节点结构
typedef struct LinkStacknode
{

    ElemType data;              //存数据
    struct LinkStacknode *next; //存下个节点的地址

} LinkStacknode;

//链栈的整体结构  
typedef struct {

    LinkStacknode *top;
    int length;
    
} LinkStack;


//初始化链栈
void Create_LinkStack(LinkStack *S){
    S->top = NULL;
    S->length = 0;
}

//判断栈为空
bool IsEmpty(LinkStack *S){
    return S->length == 0;
}

//入栈
void LinkStack_push(LinkStack *S, ElemType e){
    LinkStacknode *node;            
    node = (LinkStacknode *) malloc(sizeof(LinkStack));
    node->data = e;            
    node->next = S->top;       //新节点的next指向此时的top
    S->top = node;             //top指针指向新的节点

    S->length++;
}

//出栈
void LinkStack_pop(LinkStack *S, ElemType *e){
    if(IsEmpty(S))               //栈空
        return;                  
    LinkStacknode *del = S->top; 
    *e = del->data;              
    S->top = del->next;          //top跳过出栈节点，指向出栈节点的下一节点

    S->length--;
    free(del);                   //释放内存
}

//取栈顶
ElemType LinkStack_getTop(LinkStack *S){
    if(IsEmpty(S)){
        printf("栈为空\n");
        return -1;
    }
    return S->top->data;
}

int main(){
    LinkStack S;
    Create_LinkStack(&S);

    ElemType e;
    ElemType a[5] = {3,6,7,9,10};
    for(int i = 0; i < 5; i++)
        LinkStack_push(&S, a[i]);

    printf("栈顶元素：%d\n", LinkStack_getTop(&S));

    LinkStack_pop(&S, &e);
    printf("出栈元素：%d\n", e);   

    printf("全部元素出栈：\n");
    while(!IsEmpty(&S)){
        printf("%d ", LinkStack_getTop(&S));
        LinkStack_pop(&S, &e);
    }
    return 0;
}

链栈运行测试

---