C语言写栈
文章目录
- 一、栈的定义
- 二、栈的基本操作
- （一） 栈的顺序存储结构（基于数组）
- 栈的创建
- 栈的初始化
- 入栈
- 出栈
- 栈的遍历输出
- 完整代码
- （二）栈的链式存储结构（基于链表）
- 栈的初始化
- 判断是否为空栈
- 入栈操作
- 出栈操作
- 获取栈顶元素
- 获取栈的大小
- 主函数：
- 完整代码：
- 三、总结
一、栈的定义
栈(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");
}