坟头蹦迪是什么梗:栈、队列和多维数组

进栈│　
└→
┌─
退栈↓　

图3-1(a)

┯━┯━┯━┯━┓
│an│┄│a2│a1┃
┷━┷━┷━┷━┛
↑　　　　　↑
栈 顶　　　　栈底

胡同口
━━━━━━━━┓
⑤ ④ ③ ② ①┃
━━━━━━━━┛

图3-1(b) 死胡同

　　下面举例说明栈结构的特 征。
假设有一个很窄的死胡同，胡同里能容纳若干人，但每次只能容许一个人进出。现有五个人，分别编号为①～⑤，按编号的顺序胡同，如P43图3-1(b)所示。
此时若④要出来，必须等⑤退出后才有可能。若①要退出，则必须等到 ⑤④③②依次都退出后才行。这里，人进出胡同的原则是后进去的先出来。换句话说，先进去的后出来。
栈可以比作这里的死胡同，栈顶相当于胡同口，栈 底相当于胡同的另一端，进、出胡同可看作栈的插入、删除运算。插入、删除都在栈顶进行、进出都经过胡同口。这表明栈原则是后出(或称后进先出)。因此，栈 又称为后进先出线性表。
　　栈的基本运算至少应包括以下五种：
①初始化INISTACK(S),加工型运算，其作用是设置一个空栈S。
②进栈PUSH(S,H)，加工型运算，其作用是将元素x插入栈s中，使x成为栈s的栈的元素。
③退栈POP(S),加工型运算，其作用是当栈不空时删除栈顶元素。
④读栈TOP(S),引用型运算，其结果是栈顶元素；当栈S为空时结果为一特殊标志。与POP(S)不 同的是TOP(S)不改变栈的状态。
⑤判栈空EMPTY(S),引用型运算。若 栈S为空栈，则结果为true；否则结果为false。

二、栈的顺序实现
一般地，栈有两种实现方法：顺序实现和链接实现，这和线性表类似。
栈的顺序存储结构称为顺序栈。顺序栈通常由一个一维数组和一个记录栈顶位置的 变量组成。因为栈的操作仅在栈顶进行，栈底位置固定不变，所以可将栈底位置设置在数组两端的任意一个端点上。习惯上将栈底放在数组下标小的那端。假设用一 维数组sq(1:5)表示一个栈，则栈底下标值为1。另外需使用一个变量TOP记录当前栈顶下标值。即表示当前栈顶位置，通常称TOP为栈顶指针(注意它 并非指针类型变量)P44图3-2说明了这个顺序栈的几种状态。

5
4
3
2
1 top=1→

5
4
3 top=3→
2
1

5
4
3
2 top=2→
1

5 top=5→
4
3
2
1

5
4
3
2
1

top=0→
图3-2

(a)

0

(b)

0

(c)

0

(d)

0

 (e) 

0

　　(a)表示顺序栈为栈空， 这也是初始化运算得到的结果。此时栈顶指针top=0.此时如果作退栈运算，则产生“下溢”。
(b)表示醉中只含一个元素A，在(a)在基础 上用进栈运算PUSH(sq，A)，可以得到这种状态。此进栈顶指针top=1。
(c)表示在(b)基础上又有二个B,C先后进栈，此进栈顶 指针top=3。
(d)表示在(c)状态下栈顶元素C退栈，这可执行一次POP(sp)运算得到。此时(新)栈顶指针top=2。故B为当前 的栈顶元素(注意，数据元素C虽并未“擦去”，但已不起作用)。
(e)表示栈中有五个元素，这种状态可在(d)的基础上通过连续执行 PUSH(sq,F)，PUSH(sq,D)，PUSH(sq,E)得到。这种状态称为栈满。如果此时再作进栈运算，由于栈中已无空闲空间，因而发生“上 溢”。
顺序栈类型说明如下：
const sqstack maxsize=......;{顺序栈的容量}
type sqstack tp =record
data:array[1..sqstack maxsize] of datatype;
top:0..sqstack maxsize
end;
顺序栈被定义为一 个记录类型，它有两个域data和top。data为一个一维数组，用于存储栈中元素，datatype为栈元素的数据类型。top定义为子界型，它的取 值范围为0..sqstack maxsize。top=0表示栈空，top=sqstack maxsize表示栈满。
假设S是被定义成 sqstack_tp类型的变量,结合图3-2容易看出,若栈底位置固定在向量的低端,S.data[1]是栈低元素,而栈顶指针S.top是正向增长 的,即进栈时需将S.top加工厂,退栈时需将S.top减1.因此,S.top=0表示空栈,S.top=maxsize表示栈满。当栈满时再做进栈运 算必定产生溢出，简称“上溢”；当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免；下溢则可能是正常现象，因为栈在程 序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。
下面讲座栈的基本运算在顺序栈上的实现。
　1.进栈
进栈的主要操作是：①栈顶指针TOP加1;②将入栈元素放入到新的栈顶指针TOP 所指的位置上。
procedure push_sqstack(var sq:sqstack_tp; x:datatype);
//若 栈未满，将元素Ｘ压入栈sq中；否则给出出错信息“上溢”。//
begin
if sq.top=sqstack_maxsize
then error(“上溢”)
else [ sq.top:=sq.top+1; //栈顶下标加工厂//
sq.data[sq.top]:=x; ] //x放入栈中//
end;
　2.退栈
退栈只需将栈顶指针减１。
procedure pop_sqstack(var sq:sqstack_tp);
//栈非空时，删除栈 顶元素，否则给出出错信息//
begin
if sq.sop=0
then error(“下溢”)
else top:=top-1
end;
　3.判栈空
function empty_sqstack(sq:sqstack_tp):boolean;
//若栈空返回true;否则返回false//
begin
if sq.top=0
then return(true)
else return(false);
end;
　4.读栈顶元素
function top_sqstack(sq:sqstack_tp):datatype;
//返回栈顶元素//
begin
return(sq.data[sq.top])
end;
当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间两端，让两个栈 各自向中间延伸，这样当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间，只有当整个向量空间 被两个栈都占满(即两个栈顶相遇)时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为[m/2]的向量空间比较，前者 发生上溢的频率比后者要小得多。

三、栈的链接实现
栈的链接实现 是以某种形式的链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。
栈的链式存储结构称为链栈，其组织形式与单链表类似。由于只在链 栈的头部进行操作，故链栈没有必要设置头结点，见P47图3-3。其中，单链表的第一个结点 就是链栈栈顶结点。ls称为栈顶指旬，它相当于单链表的头指针。类似地，链栈由栈顶指针ls唯一确定。栈中的其它结点通过它们的next域链接起来。栈底 结点的next域为nil。因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况。

链栈的类型定义如下：
type 　linked_stack=↑node;
node=record
data:datatype;
next:linked_stack
end;
var ls:linked_stack;

data

next

ls→

┊

↓

┊

↓
┊
↓

nil

图3-3 链栈示意图

　　下面给出栈的基本运算在链 栈上的实现。
　1.初始化
栈初始化的作用是设置一个空栈。而一个空的链 栈可以用栈顶指针为nil来表示。
procedure init_lstack(var ls:linked_stack);
//初始化 栈ls//
begin
ls:=nel;
end;
2.进栈
进 栈算法的基本步骤包括：
①申请一个新结点,并将X的什送入该结点的data域;②将该结点链入栈中使之成为新的栈顶结点。
procedure push_lstack(var ls:linked_stack;x:datatype);
//将元素X压入栈ls中。//
begin
new(p); //生成新结点//
p↑.data:=x;
p↑.next:=ls; //链入//
ls:=p //修改栈顶指针//
end;
　3.退栈
procedure pop_lstack(var ls:linked_stack);
//若栈空给出出错信息"栈空";否则删除栈顶元素//
begin
if ls=nil
then error("栈空")
else[p:=ls;
ls:=ls↑.next;
displse(p)]
end;
栈的其他基本运算在链栈上的实现留给读者。