栈的基本操作

由于c语言中没有bool类型，所以可以自己定义一个bool类型

#define true 1  
#define false 0 

栈的结构体

typedef struct {
	int data[maxsize];
	int top;
} sqstack;

初始化栈

int initstack(sqstack* s)//初始化栈
{
	s->top = -1;
	return true;
}

栈的判空操作

int stackempty(sqstack* s)//栈判空
{
	if (s->top == -1)
		return true;
	else
		return false;
}

栈的进栈操作

int push(sqstack* s, int x)//进栈操作
{
	if (s->top == maxsize - 1)
		return false;
	s->top++;
	s->data[s->top] = x;
	return true;
}

栈的出栈操作

int pop(sqstack* s, int* x)//出栈操作
{
	if (s->top == -1)
		return false;
	*x = s->data[s->top];
	s->top--;
	return true;
}

读取栈顶元素

int gettop(sqstack* s, int* x)//读取栈顶元素
{
	if (s->top == -1)
		return false;
	*x = s->data[s->top];
	return true;
}

完整的测试代码

#define maxsize 10  
#define true 1  
#define false 0  
typedef struct {
	int data[maxsize];
	int top;
} sqstack;
int initstack(sqstack* s)//初始化栈
{
	s->top = -1;
	return true;
}
int stackempty(sqstack* s)//栈判空
{
	if (s->top == -1)
		return true;
	else
		return false;
}
int push(sqstack* s, int x)//进栈操作
{
	if (s->top == maxsize - 1)
		return false;
	s->top++;
	s->data[s->top] = x;
	return true;
}
int pop(sqstack* s, int* x)//出栈操作
{
	if (s->top == -1)
		return false;
	*x = s->data[s->top];
	s->top--;
	return true;
}
int gettop(sqstack* s, int* x)//读取栈顶元素
{
	if (s->top == -1)
		return false;
	*x = s->data[s->top];
	return true;
}
#include  
int main() {
	sqstack s;
	initstack(&s); //初始化栈  
	if (!stackempty(&s)) //栈判空  
		printf("栈不为空\n");
	else
		printf("栈为空\n");
	int x = 0;
	printf("要进栈的元素为：");
	scanf("%d", &x);
	if (push(&s, x)) //进栈操作  
		printf("进栈元素为%d\n", x);
	else
		printf("栈满，不能进栈%d\n", x);
	if (pop(&s, &x)) //出栈操作  
		printf("出栈元素为%d\n", x);
	else
		printf("栈为空，不能出栈\n");
	printf("%d\n", x);
	if (gettop(&s, &x)) //获取栈顶元素操作  
		printf("栈顶元素为%d\n", x);
	else
		printf("栈为空\n");
	return 0;
}

栈（stack）是一种线性结构，它具有的特性

1. 后进先出（LIFO，Last In First Out）：栈中元素的添加和删除都发生在同一端，称为栈顶。最后一个添加到栈中的元素将是第一个被删除的元素。
2. 只能在栈顶进行插入和删除操作：这意味着栈的底部（栈底）到顶部（栈顶）的方向是固定的。
3. 动态数据结构：栈可以根据需要创建和销毁。

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 5
typedef struct sqstack
{
	int data[MaxSize];
	int top;
}sqstack;
void initstack(sqstack* s)
{
	s->top = -1;
}
int stackempty(sqstack* s)
{
	if (s->top == -1)
		return 1;
	else
		return 0;
}
int push(sqstack* s,int x)
{
	if (s->top == MaxSize - 1)
	{
		printf("栈满，%d无法进栈", x);
		return;
	}
	s->top = s->top + 1;
	s->data[s->top] = x;
	return 1;
}
int pop(sqstack* s)
{
	if (s->top == -1)
		return 0;
	return s->data[s->top--];;
}
int gettop(sqstack* s,int x)
{
	if (s->top == -1)
	{
		printf("栈空");
		return;
	}
	return  s->data[s->top];
}
int main()
{
	sqstack s;
	initstack(&s);
	stackempty(&s);
	int i = 0;
	int x = 0;
	printf("请输入进栈的元素:\n");
	for (i = 0; i < 6; i++)
	{
		scanf("%d", &x);
		push(&s, x);
	}
	printf("\n出栈的元素依次为");
	while (!stackempty(&s))
	{
		printf("%d ", pop(&s));
	}
	return 0;
}

 

从这段代码可以看出

栈的最大容量为5，但是我依次输入了1，2，3，4，5，6，到6的时候，栈已经满了，所以不能再压入栈中。出栈的时候5后进入的，先出的栈。

栈的应用

将十进制转换为八进制

#include <stdio.h>  
#define OK 1  
#define ERROR 0  
typedef int Status;
#define MAXSIZE 100  
typedef struct
{
	int* base;
	int* top;
	int stacksize;
} SqStack;
Status InitStack(SqStack* S) 
{
	S->base = (int*)malloc(sizeof(int) * MAXSIZE); //动态分配内存  
	if (S->base ==NULL) {
		return ERROR; //内存分配失败，返回错误  
	}
	S->top = S->base;
	S->stacksize = MAXSIZE;
	return OK;
}
Status Push(SqStack* S, int e)
{
	if (S->top - S->base == S->stacksize) return ERROR;
	*S->top++ = e;
	return OK;
}
Status Pop(SqStack* S, int* e)  
{
	if (S->top == S->base) return ERROR;
	*e = *--S->top;
	return OK;
}
void conversion(int N)
{
	int e;
	SqStack S;
	InitStack(&S); 
	while (N)
	{
		Push(&S, N % 8); 
		N = N / 8;
	}
	while (S.top != S.base)
	{
		Pop(&S, &e); 
		printf("%d", e);
	}
}
int main()
{
	int N;
	printf("请输入要转换的十进制整数:\n");
	scanf("%d", &N);
	printf("十进制整数%d转换成八进制数为:", N);
	if (N > 0)
		conversion(N);
	else if (N == 0)
		printf("0");
	else {
		printf("-");
		conversion(-N);
	}
	printf("\n");
	return 0;
}