栈的基本操作
程序员文章站
2024-02-19 22:12:22
...
1.栈的概念
栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除操作;进行数据插入和删除操作的一端称为栈顶(top),另一端称为栈底(bottom);不含任何元素的栈称为空栈;栈又称为后进先出的线性表。
2.栈特性
后进先出(LILO)特殊线性表
3.栈功能
将数据从一种序列改变成另一种序列
4.模块函数 【1.定义一个栈结构体】
- 定义一个数组
- 定义一个标记栈顶元素的变量
#define MAXSIZE 10
typedef int SDataType;
typedef struct Stack
{
SDataType _array[MAXSIZE];
int _top; //标记栈顶元素
}Stack;
【2.栈的初始化】
- 让栈顶元素指向空
void StackInit(Stack *ps)
{
assert(ps);
ps->_top = 0;
}
【3.压栈操作】
- 首先判断栈中元素是否已满,若满了直接返回
- 若未满将元素插入栈顶
void StackPush(Stack *ps, SDataType data)
{
assert(ps);
if (MAXSIZE == ps->_top)
{
printf("栈空间已满,无法插入!!!\N");
return;
}
ps->_array[ps->_top++] = data;
}
【4.出栈操作】
- 首先对栈进行判空操作,已空直接返回
- 非空,从栈顶中出一个元素
void StackPop(Stack *ps)
{
assert(ps);
if (StackEmpty(ps))
return;
ps->_top--;
}
【5.返回栈顶元素】
- 直接返回数组中为栈顶减一的元素下标
SDataType StackTop(Stack *ps)
{
assert(ps);
return ps->_array[ps->_top - 1];
}
【6.返回栈空间长度】
- 栈空间长度,即:栈顶所在位置,直接返回栈顶
int StackSize(Stack *ps)
{
assert(ps);
return ps->_top;
}
【6.栈是否为空】
- 判断栈顶元素是否为空
int StackEmpty(Stack *ps)
{
assert(ps);
return 0 == ps->_top;
}
5.完整代码块
/************************************/
//Stack.h
#define MAXSIZE 10
typedef int SDataType;
typedef struct Stack
{
SDataType _array[MAXSIZE];
int _top; //标记栈顶元素
}Stack;
//初始化
void StackInit(Stack *ps);
//压栈
void StackPush(Stack *ps, SDataType data);
//出栈
void StackPop(Stack *ps);
//返回栈顶元素
SDataType StackTop(Stack *ps);
//返回栈空间长度
int StackSize(Stack *ps);
//栈是否为空
int StackEmpty(Stack *ps);
/****************************************/
//Stack.c
#include <assert.h>
#include <stdio.h>
#include <string.h>
//初始化
void StackInit(Stack *ps)
{
assert(ps);
ps->_top = 0;
}
//压栈
void StackPush(Stack *ps, SDataType data)
{
assert(ps);
if (MAXSIZE == ps->_top)
{
printf("栈空间已满,无法插入!!!\N");
return;
}
ps->_array[ps->_top++] = data;
}
//出栈
void StackPop(Stack *ps)
{
assert(ps);
if (StackEmpty(ps))
return;
ps->_top--;
}
//返回栈顶元素
SDataType StackTop(Stack *ps)
{
assert(ps);
return ps->_array[ps->_top - 1];
}
//返回栈空间长度
int StackSize(Stack *ps)
{
assert(ps);
return ps->_top;
}
//栈是否为空
int StackEmpty(Stack *ps)
{
assert(ps);
return 0 == ps->_top;
}
/****************************************/
//test.c
#include "Stack.h"
void TestStack()
{
Stack s;
StackInit(&s);
StackPush(&s, 1);
StackPush(&s, 2);
StackPush(&s, 3);
StackPush(&s, 4);
printf("size = %d\n", StackSize(&s));
printf("top = %d\n", StackTop(&s));
StackPop(&s);
StackPop(&s);
printf("size = %d\n", StackSize(&s));
printf("top = %d\n", StackTop(&s));
StackPop(&s);
StackPop(&s);
printf("size = %d\n", StackSize(&s));
}
int main()
{
TestStack();
system("pause");
return;
}