c语言之栈结构

1.什么是栈

栈是一种只能在一端进行插入或者删除操作的线性表（说明栈还是线性表结构，只是操作受限而已）。其中允许进行插入或者删除操作的一端称为栈顶。栈的插入和删除一般叫入栈和出栈。栈的顺序存储结构叫做顺序栈，栈的链式存储结构叫做链栈。

2.栈的特点

栈的特点是后进先出。老师都喜欢举那个将盘子压入箱子的例子来解释栈的特点。举个例子：很多车开进死胡同，先进去的必须得等之前所有的车全出去才可以出去，所以第一个进去的车最后一个出来。最后进去的车第一个出来，所以这个就类似于栈，先进后出。

3.顺序栈

顺序栈的结构：

#define maxsize 100
typedef struct SqStack{
	int data[maxsize];
	int top;
}SqStack;

顺序栈的状态：

（1）栈空状态：

st.top=-1;

（2）栈满状态：

st.top=maxsize-1;

顺序栈的操作：

（1）进栈：先开辟空间，然后元素入栈

++st.top;
st.data[st.top]=x;

（2）出栈：元素先出栈，然后改变栈顶指针。

x=st.data[st.top];
--st.top;

顺序栈的实现：

#include<stdio.h>
#include<stdlib.h>
#define maxsize 100
typedef struct SqStack{
    int data[maxsize];
    int top;
}SqStack;
//初始化顺序栈
void initSqStack(SqStack *st){
    st->top=-1;
}
//判断栈是否为空
int SqStackEmpty(SqStack *st){
    return (st->top==-1?1:0);
}
//进栈
int push(SqStack *st,int x){
    if(st->top==maxsize-1){
        return 0;
    }
    st->data[++st->top]=x;
    return 1;
}
//出栈
int pop(SqStack *st,int *x){
    if(st->top ==-1){
        return 0;
    }
    *x=st->data[st->top--];
    return 1;
}
//打印栈元素
void printStack(SqStack *st){
    while(st->top !=-1){
        printf("栈元素：%d\n",st->data[st->top--]);
    }
}
void main(){
    int x;
    SqStack st={{1,2,3,4},3};
    push(&st,5);
    pop(&st,&x);
    printf("出栈元素：%d\n",x);
    printStack(&st);
}

结果：

注意：在出栈前一定要先判断栈是否为空，在入栈前一定要判断栈是否为满栈。

4.链栈

链栈的结构：

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

链栈的状态：

（1）栈空：

ln->next==NULL;

链栈的操作：

（1）进栈：

p->next=ln->next;
ln->next=p;

（2）出栈：

p=ln->next;
*x=p->data;
ln->next=p->next;
free(p);

链栈的实现：

#include<stdio.h>
#include<stdlib.h>
typedef struct Lnode{
	int data;
	struct Lnode *next;
}Lnode;
//初始化链栈
void initStack(Lnode *ln){
	ln=(Lnode *)malloc(sizeof(Lnode));
	ln->next=NULL;
}
//判断链栈是否为空
int StackEmpty(Lnode *ln){
	return (ln->next==NULL?1:0);
}
//进栈
void push(Lnode *ln,int x){
	Lnode *p;
	p=(Lnode *)malloc(sizeof(Lnode));
	if(p ==NULL){
		printf("ERROR");
		exit(0);
	}
	p->next=NULL;
	p->data=x;
	p->next=ln->next;
	ln->next=p;
}
//出栈
int pop(Lnode *ln,int *x){
	Lnode *p=ln->next;
	if(p ==NULL){
		return 0;
	}
	*x=p->data;
	ln->next=p->next;
	free(p);
	return 1;
}
void printStack(Lnode *ln){
	Lnode *p=ln->next;
	while(p!=NULL){
		printf("%d\n",p->data);
		p=p->next;
	}
}
void main(){
	Lnode ln;
	int x;
	initStack(&ln);
	push(&ln,2);
	push(&ln,3);
	push(&ln,4);
	push(&ln,5);
	pop(&ln,&x);
	printf("出栈元素为：%d\n",x);
	printStack(&ln);
}

结果：