关于栈的一些总结

数据结构真的是好东西啊！！！！！我真心喜欢他！

栈(STACK)

栈的定义：栈是一个后进先出（Last In Fist Out, LIFO）的线性表，它要求只在表尾进行删除和插入操作。
所谓的栈，其实就是一个特殊的线性表（顺序表、链表），但是它在操作上有一些特殊的要求和限制：

• 栈的元素必须“后进先出”
• 栈的操作只能在这个线性表的表尾进行。
• 对于栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）。

栈的基本操作

• InitStack(&S):初始化一个空栈S。
• StackEmpty(S）:判断一个栈是否为空，若栈空则返回TURE，否则返回FALSE。
• Push(&S,x):进栈，若S未满，则把x加入使之成为新栈顶。
• Pop(&S,&x):出栈，若S非空，则弹出栈顶元素，并用x返回。
• GetTop(S,&x):读取栈顶元素，若S非空，则用x返回栈顶元素。
• DestroyStack(&S):销毁栈，并释放栈S占用的存储空间。

栈的顺序存储结构

因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也分为栈的顺序存储结构和栈的连式存储结构。
最开始栈中不包含任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。
关于出栈入栈，动图示范如下：

物理结构与逻辑结构

首先，先来认识一下数据结构中的两个重要概念：物理结构和逻辑结构。
当谈到“物理”和“逻辑”一词时，我们可以会想到数据库中的逻辑删除和物理删除。
所谓的物理删除是指通过删除命令真实的将数据从物理结构中删除的过程；而逻辑删除是指通过修改命令将数据更改为“已删除”的状态，并非真实的删除数据。
这里的逻辑结构和物理结构和上面的概念类似，所谓的物理结构是指可以将数据存储在物理空间中，比如数组和链表都属于物理数据结构；而逻辑结构则是用于描述数据间的逻辑关系的，比如栈就属于逻辑结构。
可能有些人看到这里就蒙了，没关系，我这里举一个例子你就明白了。
如果用人来表示物理结构和逻辑结构的话，那么真实存在的有血有肉的人就属于物理结构，而人的思想和信念就属于逻辑结构了。

顺序栈的实现

采用顺序存储方式的栈为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top)指示当前栈顶元素的位置。
栈的顺序存储类型可描述为：

#define MaxSize 50
typedef struct{
Elemtype data[MaxSize];
int top;
}SqStack;

栈顶指针：S.top，初始设置S.top=-1；栈顶元素：S.data[S.top]。
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。
出栈操作：栈非空时，先取栈顶元素，再将栈顶元素减1。
栈空条件：S.top=-1;栈满条件：S.top==MaxSize-1;栈长：S.top+1。
当然，顺序栈有其优缺点：

• 优点: 节省空间, 操作简单,学习成本较低,易于理解.
• 缺点: 栈的大小一开始就声明’死’了,不利于使用.这种情况可能会因为空间不足产生上溢。

顺序栈基本运算实现

1.初始化

void InitStack(SqStack &S){
S.top=-1;
}

2.栈判空

bool StackEmpty(SqStack S){
if(S.top=-1)
return true;
else 
return false;
}

3.进栈

bool Push(SqStack &S,ElemType x){
if(S.top=MaxSize-1)
return false;
S.data[++S.top]=x;
return true;
}

当栈不满时，top先加1。
4.出栈

bool Pop(SqStack &S,ElemType x){
if(S.top==-1)
return false;
S.data[S.top--]=x;
retuen true;
}

5.读取顶元素

bool GetTop(SqStack S,ElemType &x){
if(S.top==-1)
return false;
x=S.data[S.top];
return true;
}

代码实现

下面，我们就用代码来实现一个顺序栈的一系列操作。

#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20//存储空间初始分配量

typedef int Status;
typedef char SElemType;//定义结构类型

/*构造一个数组*/
typedef struct
{
    SElemType data[MAXSIZE];
    int top;
}SqStack;

Status visit(SElemType c)
{
    printf("%d", c);
    return OK;
}

/*构造一个空栈S，栈初始化*/
Status InitStack(SqStack* S)
{
    S->top = -1;
    return OK;
}

/*把S置为空栈*/
Status ClearStack(SqStack* S)
{
    S->top = -1;
    return OK;
}

/*若栈为空，则返回TRUE，否则返回FALSE*/
Status StackEmpty(SqStack S)
{
    if (S.top == -1)
        return TRUE;
    else
        return FALSE;
}

/*返回S的元素个数，即栈的长度*/
int StackLength(SqStack S)
{
    return S.top + 1;
}
/*若栈不空，则用e返回S的栈顶元素，并返回OK否则返回ERROR*/
Status GetTop(SqStack S, SElemType *e)
{
    if (S.top == -1)
        return ERROR;
    else
        *e = S.data[S.top];
    return OK;
}

/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S, SElemType e) 
{
    if(S->top == MAXSIZE - 1)
    {
        return ERROR;
    }
    S->top++;
    S->data[S->top] = e;
    return OK;
}
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR*/
Status Pop(SqStack* S, SElemType *e)
{
    if (S->top == -1)
        return ERROR;
    *e = S->data[S->top];
    S->top--;
    return OK;
}

/*从栈底到栈顶依次对栈中每个元素显示*/
Status StackTraverse(SqStack S)
{
    int i;
    i = 0;
    while (i <= S.top)
    {
        visit(S.data[i++]);
    }
    printf("\n");
    return OK;
}

int main()
{
    int j;
    SqStack s;
    int e;
    /*1.初始化栈*/
    InitStack(&s);
    printf("初始化栈成功\n");

    /*2.判断栈s是否为空*/
    printf("2.栈空否：%d(1:空 0:否）\n", StackEmpty(s));

    /*3.依次进栈abcde*/
    Push(&s, ‘a‘);
    Push(&s, ‘b‘);
    Push(&s, ‘c‘);
    Push(&s, ‘d‘);
    Push(&s, ‘e‘);
    printf("3.abcde依次进栈完毕\n");

    /*4.判断栈s是否非空*/
    printf("2.栈空否：%d(1:空 0:否)\n", StackEmpty(s));

    /*5.输出出栈顺序*/
    printf("4.栈中元素依次为：");
        StackTraverse(s);

    /*6.判断栈s是否为空*/
    printf("5.栈空否：%d(1:空 0:否)\n", StackEmpty(s));

    /*释放栈*/
    ClearStack(&s);
    printf("6.栈释放完毕！");
    printf("释放栈后，栈空否:%d(1.空 0:否)\n", StackEmpty(s));
    system("pause");
    return 0;
}

栈的链式结构

1.栈的链式存储描述

//链栈定义 
typedef struct StackNode{
	SElemType data;
	struct StackNode *next;
}StackNode,*LinkStack; 

2.链栈初始化

//链栈初始化
Status InitStack(LinkStack &S){
	S=NULL;
	return OK;
} 

3.链栈压栈

//链栈进栈
Status Push(LinkStack &S,SElemType e){
	//创建新结点，链栈没有上限 
	StackNode *p=new StackNode();
	if(!p) return ERROR;
	p->data = e;
	p->next=S;
	S=p;
	return OK;
}

4.链栈出栈

//链栈出栈
Status Pop(LinkStack &S,SElemType &e){
	//判断链栈是不是空
	if(!S) return ERROR;
	StackNode *p=S;
	e=S->data;
	S=S->next;
	delete p;
	return OK;
} 

5.链栈获取栈顶元素

//取链栈栈顶元素 
Status GetTop(LinkStack S,SElemType &e){
	//判断链栈是不是空
	if(!S) return ERROR;
	e=S->data;
	return OK; 
} 

6.链栈赋随机值

Status InStack(LinkStack &S,int n){
	for(int i=0;i<n;i++){
		Push(S,rand());
	}
	return OK;
}

7.链栈输出

Status PrintStack(LinkStack S){
	//判断链栈是不是空 
	if(!S) return ERROR;
	for(int i=0;S;i++){
		cout<<S->data<<" ";
		S=S->next;
	}
	cout<<endl;
	return OK;
} 

关于栈的一些总结

原文：https://www.cnblogs.com/xiaoay/p/14802701.html