栈的顺序存储及实现（一）

布满荆棘的人生 2022-06-03 08:46 160阅读 0赞

继续学习数据结构，今天我们来学习栈的相关知识。其实学习没有捷径，如果抱着一种吃快餐的态度进行学习，那是学不到东西，各种技术都是浅尝辄止，那注定学习是不会有太大的效果。不知道你们讨不讨厌 某某语言从入门到精通的这类书籍？我在想，有这么牛逼么，一本书直接都从入门到精通了，只不是吸引那些初学者的鳌头吧了。算法都是老前辈们留下来解决某一类问题非常行之有效的方法，不管什么时候都不会过时。虽然很多算法，在很多书上或者网上都有，但是我们得自己去敲一遍，才能有所收获。

不扯了，首先我们来看一下栈的相关定义。

**栈（stack）是限定仅在表尾进行插入和删除操作的线性表。**

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又被称为后进先出（LastIn First Out）的线性表，简称LIOF结构。

首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。

**它的特殊之出在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这使得：栈底是固定的，最先进栈的只能在栈底。**

**栈的插入叫 进栈也称 压栈、入栈。**

**栈的删除叫出栈，也称弹栈。**

**当然 压栈和出栈是栈最重要的算法。**

**实际上栈在程序中用的是特别多的，比如浏览器的前进后退，文档的撤销操作等都是用的栈的方式。**

接下来我们用数组也就是顺序存储结构来实现栈的相关算法。

下面是我们栈的数据结构

typedef struct SeqStack \{  
EleType data\[MAXSIZE\];//存储栈数据  
int top;//栈顶位置  
\}SeqStack;

进栈操作：

栈未满的情况下，插入元素为新的栈顶，栈顶指针相应加1。

![Center][]

出栈操作：

若栈不为空，则删除stack的栈顶元素，栈顶减一，返回删除元素值。

当为栈空时 top=-1。

下面通过代码来实现栈的相关算法实现。

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <math.h>
    #include <stdlib.h>
    #define MAXSIZE 100
    #define ERROR 0
    #define OK 1
    #define TRUE 1
    #define FALSE 0
    typedef int EleType;
    //顺序存储结构的栈的数据结构
    typedef struct SeqStack {
    	EleType data[MAXSIZE];//存储栈数据
    	int top;//栈顶位置
    }SeqStack;
    /*
    初始化链表，直接将栈顶置为-1，就代表，栈内所有位置可用。
    */
    int initStack(SeqStack* stack) {
    	if (NULL == stack) {
    		return ERROR;
    	}
    	stack->top = -1;
    	return OK ;
    }
    /*
    压栈，很简单，在空间允许情况下往栈顶上面一个位置进行压入元素
    */
    int push(SeqStack * stack, EleType e) {
    	if (NULL == stack || MAXSIZE == stack->top + 1) {
    		return ERROR;
    	}
    	stack->data[stack->top + 1] = e;
    	stack->top++;
    	return OK;
    }
    /*
    弹栈，一样的道理，在非空栈中弹出元素，通过指针将元素值进行返回。
    */
    void pop(SeqStack* stack, EleType* e)
    {
    	if (NULL == stack || NULL == e || stack->top == -1) {
    		return ERROR;
    	}
    	*e = stack->data[stack->top];
    	stack->top--;
    	return OK;
    }
    /*
    从栈顶向下展示元素值
    */
    void showStack(SeqStack* stack) {
    	if (NULL == stack||stack->top==-1) {
    		return;
    	}
    	int i = stack->top;
    	for (; i >=0; i--)
    	{
    		printf("%d\n", stack->data[i]);
    	}
    	return;
    }
    /*
    清空栈
    */
    int clearStack(SeqStack* stack) {
    	if (NULL == stack) {
    		return ERROR;
    	}
    	stack->top = -1;
    	return OK;
    }
    /*
    判断栈是否为空
    */
    int stackEmpty(SeqStack* stack) {
    	if (NULL == stack) {
    		return ERROR;
    	}
    	if (stack->top == -1) {
    		return TRUE;
    	}
    	return FALSE;
    }
    int getTop(SeqStack* stack,EleType *e) {
    	if (NULL == stack) {
    		return ERROR;
    	}
    	*e = stack->data[stack->top];
    	return OK;
    }
    /*
    栈元素个数
    */
    int getStackLength(SeqStack* stack) {
    	if (NULL == stack) {
    		return ERROR;
    	}
    	return stack->top + 1;
    }
    
    int main(int argc, char *argv[])
    {
    	SeqStack stack;//创建顺序栈
    	initStack(&stack);//初始化
    	push(&stack, 5);
    	push(&stack, 4);
    	push(&stack, 3);
    	push(&stack, 2);
    	push(&stack, 1);
    	printf("压入元素个数%d\n", getStackLength(&stack));
    	puts("分别为：");
    	showStack(&stack);
    	puts("弹出2个元素后：");
    	EleType e1,e2;
    	pop(&stack, &e1);
    	pop(&stack, &e2);
    	showStack(&stack);
    	printf("弹出元素为:%d,%d\n", e1, e2);
    	return 0;
    }

栈的相关算法，还是比较容易理解的。

验证结果截图：

![Center 1][]

[Center]: /images/20220603/6fbc91e542a943e6bddabe7a1df95492.png
[Center 1]: /images/20220603/958318f009564734bdb4822a311b7a55.png