如何理解“栈”?
后进先出(LIFO-last in first out):最后插入的元素最先出来。
关于“栈”,有一个非常贴切的例子,就是一摞叠在一起的盘子。我们平时放盘子的时候,都是从下往上一个一个放;取的时候,我们也是从上往下一个一个地依次取,不能从中间任意抽出。后进者先出,先进者后出,这就是典型的“栈”结构。
从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。
当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构。
实际上,栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,我们叫作顺序栈,用链表实现的栈,我们叫作链式栈。
顺序栈
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定,这里假设为int */
/* 顺序栈结构 */
//Sequence Stack
typedef struct {
SElemType data[MAXSIZE];
int top; //栈顶指针,这里的指针(记录位置)并非c中的指针,
} SqStack;
//1.初始化空栈
Status initStack(SqStack *S) {
S->top = -1;
return OK;
}
//2.置空栈
Status clearStack(SqStack *S) {
//这里不需要清空数组中的元素,编译器在编译阶段就知道该为这个数组分配多少内存了,这就叫静态分配,静态分配的内存在栈里,每进入一个函数时都会建栈,栈里会存放函数用到的参数、局部变量等信息,函数执行完以后,会出栈销毁栈,这个过程就会释放你静态分配的数组内存,这是由系统自动完成的。
S->top = -1;
return OK;
}
//3.判断栈空
Status stackEmpty(SqStack S) {
//结构体点语法
return S.top == -1;
}
//4.进栈push
Status stackPush(SqStack *s,SElemType e) {
//判断栈满
if (s->top == MAXSIZE-1) {
return ERROR;
}
//栈顶指针加一,将新插入的元素赋值给栈顶空间
s->data[++s->top] = e;
return OK;
}
//5.pop出栈,并且用e带回
Status pop(SqStack *s,SElemType *e) {
//判断栈空
if (stackEmpty(*s)) {
return ERROR;
}
//栈顶指针-1;
*e = s->data[s->top--];
return OK;
}
//6.获取栈顶元素
Status getTopElem(SqStack s,SElemType *e) {
//判断栈空
if (stackEmpty(s)) {
return ERROR;
}
*e = s.data[s.top];
return OK;
}
//7. 从栈底到栈顶依次打印栈中的每个元素
Status stackTraverse(SqStack s){
int i = 0;
printf("此栈中所有元素:\n");
while (i<=s.top) {
printf("%d ",s.data[i++]);
}
printf("\n");
return OK;
}
int main(int argc, const char * argv[]) {
printf("Hello, World!\n");
// SqStack *Sq = (SqStack *)malloc(sizeof(SqStack));//若使用指针要给指针开辟内存区域
SqStack Sq;//在函数中定义变量,系统会自动为变量分配内存保存到栈中
printf("%p",&Sq);
initStack(&Sq);
for (int i=0; i<10; i++) {
stackPush(&Sq, i);
}
stackTraverse(Sq);
return 0;
}
链式栈
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定,这里假设为int */
//链栈节点
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
//定义栈
typedef struct {
LinkStackPtr top;//栈顶指针
int count;
}LinkStack;
//1.创建一个空栈
Status InitStack(LinkStack *s) {
(s)->top = NULL;
(s)->count = 0;
return OK;
}
//2.置空
Status clearStack(LinkStack *s) {
LinkStackPtr p,q;
p = s->top;
while (p) {
q = p;
p = p->next;
free(q);
}
(s)->count = 0;
return OK;
}
//3.判断栈空
Status emptyStack(LinkStack s) {
if (s.count == 0) {
return TRUE;
} else {
return FALSE;
}
}
//4.返回栈长
int lentthStack(LinkStack s) {
return s.count;
}
//5.取栈顶元素
Status getTopElem(LinkStack s, SElemType *e) {
//判断栈空
if (emptyStack(s)) {
return ERROR;
}
*e = s.top->data;
return OK;
}
//6.push入栈
Status pushStack(LinkStack *s,SElemType e) {
//创建一个节点
LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
if (temp == NULL) {
return ERROR;
}
temp->data = e;
//头插入栈
temp->next = s->top;
s->top = temp;
s->count++;
return OK;
}
//7.遍历打印栈中的元素
void traverseStack(LinkStack s) {
LinkStackPtr p = s.top;
while (p) {
printf("%d ",p->data);
p = p->next;
}
}
Status popStack(LinkStack *s,SElemType *e) {
//判断栈空
if (emptyStack(*s)) {
return ERROR;
}
//头删
LinkStackPtr p;
p = s->top;
*e = p->data;
s->top = s->top->next;
free(p);
s->count--;
return OK;
}
int main(int argc, const char * argv[]) {
LinkStack p;
InitStack(&p);
for (int i = 0; i<10; i++) {
pushStack(&p, i);
}
traverseStack(p);
SElemType e;
popStack(&p, &e);
printf("\n%d", e);
traverseStack(p);
return 0;
}
网友评论