文章目录

• 一、栈的定义
• 二、栈的基本操作
• • （一） 栈的顺序存储结构（基于数组）
  • • 栈的创建
    • 栈的初始化
    • 入栈
    • 出栈
    • 栈的遍历输出
    • 完整代码
  • （二）栈的链式存储结构（基于链表）
  • • 栈的初始化
    • 判断是否为空栈
    • 入栈操作
    • 出栈操作
    • 获取栈顶元素
    • 获取栈的大小
    • 主函数：
    • 完整代码：
• 三、总结

一、栈的定义

栈(stack)是限定仅在表尾进行插入或者删除的线性表。对于栈来说，表尾端称为栈顶（top），表头端称为栈低（bottom）。不含元素的空表称为空栈。因为栈限定在表尾进行插入或者删除，所以栈又被称为后进先出的线性表。

二、栈的基本操作

（一） 栈的顺序存储结构（基于数组）

栈的创建

typedef struct
{
	int data[N];
	int top;
}Sqstack;

栈的初始化

void initSqStack(Sqstack *st){
    st->top = -1;
}

入栈

void Push(Sqstack *S, int n){
	if(S->top == N - 1){
		printf("栈已满！\n");
		return;
	}
	S->top++;
	S->data[S->top] = n;
}

出栈

void Pop(Sqstack *S, int *x){
	if(S->top == -1){
		return;
	}
	*x = S->data[S->top];
}

栈的遍历输出

void Print(Sqstack *S){
	while(S->top > -1){
		printf("%d\n", S->data[S->top--]);
	}
}

完整代码

#include<stdio.h>
#define N 5

typedef struct
{
	int data[N];
	int top;
}Sqstack;



void initSqStack(Sqstack *st){
    st->top = -1;
}


void Push(Sqstack *S, int n){
	if(S->top == N - 1){
		printf("栈已满！\n");
		return;
	}
	S->top++;
	S->data[S->top] = n;
}

void Print(Sqstack *S){
	while(S->top > -1){
		printf("%d\n", S->data[S->top--]);
	}
}

void Pop(Sqstack *S, int *x){
	if(S->top == -1){
		return;
	}
	*x = S->data[S->top];
}

int main()
{
	int x;
	Sqstack s;
	initSqStack(&s);
	Push(&s, 1);
	Push(&s, 2);
	Push(&s, 3);
	Push(&s, 4);
	Push(&s, 5);
	Pop(&s, &x);
	printf("出栈的元素：%d\n", x);
	Print(&s);
	return 0;	
}

（二）栈的链式存储结构（基于链表）

typedef struct node{      //定义结点
    int data;
    node *next;
}Node, *pNode;
 
typedef struct{    //定义栈
    pNode top;   //栈顶
    int count;
}LinkStack,*pLinkStack;

栈的初始化

void init(pLinkStack s){
	s->top = NULL;
	s->count = 0;
}

判断是否为空栈

int isEmpty(pLinkStack s){
	if(s->top == NULL){
	 return 1;
	} else {
	return 0;
	}
}

入栈操作

void push(pLinkStack s, int a){
    pNode p = (pNode)malloc(sizeof(Node));
    p->data = a;
    p->next = s->top;
    s->top = p;
    s->count++;
}

出栈操作

int pop(pLinkStack s){
	pNode p = s->top;
	int a = p->data;
	s->top = p->next;
	s->count--;
	free(p);
	return a;
}

获取栈顶元素

int ding(pLinkStack s){
	return s->top->data;
}

获取栈的大小

int length(pLinkStack s){
	return s->count;
}

主函数：

int main(){
	int len, top, t;
    LinkStack s;
    init(&s);
    push(&s, 1);
    push(&s, 3);
    push(&s, 5);
    push(&s, 7);
    top=ding(&s);
    len=length(&s);
    printf("top: %d, len: %d\n", top, len);
    while(!isEmpty(&s)){
	    t = pop(&s);
        printf("删除的顶部元素为:%d\n", t);
    }
    system("pause");
}

完整代码：

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

typedef struct node{      //定义结点
    int data;
    node *next;
}Node, *pNode;
 
typedef struct{    //定义栈
    pNode top;   //栈顶
    int count;
}LinkStack,*pLinkStack;

void init(pLinkStack s){
	s->top = NULL;
	s->count = 0;
}

int isEmpty(pLinkStack s){
	if(s->top == NULL){
	    return 1;
	} else {
	    return 0;
	}
}

void push(pLinkStack s, int a){	
    pNode p = (pNode)malloc(sizeof(Node));
    p->data = a;
    p->next = s->top;
    s->top = p;
    s->count++;
}

int pop(pLinkStack s){
	pNode p = s->top;
	int a = p->data;
	s->top = p->next;
	s->count--;
	free(p);
	return a;
int ding(pLinkStack s){
	return s->top->data;
}
int length(pLinkStack s){
	return s->count;
}

int main(){
	int len, top, t;
    LinkStack s;
    init(&s);
    push(&s, 1);
    push(&s, 3);
    push(&s, 5);
    push(&s, 7);
    top=ding(&s);
    len=length(&s);
    printf("top: %d, len: %d\n", top, len);
    while(!isEmpty(&s)){
	    t = pop(&s);
        printf("删除的顶部元素为:%d\n", t);
    }
    system("pause");
}

三、总结