[马上理财]栈和队列 – 数据结构和算法23

栈和行列

让编程改动国际

Change the world by program

栈和行列

栈和行列

栈的界说

栈是一种重要的线性结构，能够这样讲，栈是前面讲过的线性表的一种具体方式。

就像咱们方才的比如，栈这种后进先出的数据结构运用是十分广泛的。

在生活中，例如咱们的阅读器，每点击一次“撤退”都是退回到最近的一次阅读网页。

例如咱们Word，Photoshop等的“吊销”功用也是如此。再例如咱们C言语的函数，也是运用栈的基本原理完成的。

官方界说：栈（Stack）是一个后进先出（Last in first out,LIFO）的线性表，它要求只在表尾进行删去和刺进操作。

小王八界说：所谓的栈，其实也便是一个特别的线性表（次序表、链表），可是它在操作上有一些特别的要求和约束：

栈的元素有必要“后进先出”。

栈的操作只能在这个线性表的表尾进行。

注：关于栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）。

栈的刺进和删去操作

栈的刺进操作（Push），叫做进栈，也称为压栈，入栈。相似子弹放入弹夹的动作。

栈的删去操作（Pop），叫做出栈，也称为弹栈。好像弹夹中的子弹出夹。

请看动画演示！

栈的次序存储结构

由于栈的实质是一个线性表，线性表有两种存储方式，那么栈也有分为栈的次序存储结构和栈的链式存储结构。

最开端栈中不含有任何数据，叫做空栈，此刻栈顶便是栈底。然后数据从栈顶进入，栈顶栈底别离，整个栈的当时容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当时容量变小。

妈呀，说啥呢？

请结合下图发挥想象力了解并记住：

栈和行列

typedef struct

{

? ? ? ? ElemType *base;

? ? ? ? ElemType *top;

? ? ? ? int stackSize;

}sqStack;

这儿界说了一个次序存储的栈，它包含了三个元素：base,top,stackSize。

其间base是指向栈底的指针变量，top是指向栈顶的指针变量，stackSize指示栈的当时可运用的最大容量。

创立一个栈

define STACK_INIT_SIZE 100 initStack(sqStack *s)

{

? ? ? ? s->base = (ElemType )malloc( STACK_INIT_SIZE sizeof(ElemType) );

? ? ? ? if( !s->base )

? ? ? ? ? ? ? ? exit(0);

? ? ? ? s->top = s->base;? ?// 最开端，栈顶便是栈底

? ? ? ? s->stackSize = STACK_INIT_SIZE;

}

入栈操作

入栈操作又名压栈操作，便是向栈中寄存数据。

入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针就要+1，知道栈满停止。

请看代码挺小王八具体解说：Push.c

出栈操作

出栈操作便是在栈顶取出数据，栈顶指针随之下移的操作。

每逢从栈内弹出一个数据，栈的当时容量就-1。

代码清单：

Pop(sqStack s, ElemType e)

{

? ? ? ? if( s->top == s->base )??// 栈已空空是也

? ? ? ? ? ? ? ? return;

? ? ? ? e = --(s->top);

}

视频下载

备用视频下载
技能, IT技能, 数据结构和算法, 栈顶