数据结构之栈专题

退隐网络

栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。表尾端称栈顶（top），表头端称栈底（bottom）。
若有栈 S=（s0，s1，…，sn-1）则s0为栈底结点，sn-1为栈顶结点。通常称栈的结点插入为进栈，栈的结点删除为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的特点。

栈有两种存储结构：顺序栈和链栈
顺序栈即栈的顺序存储结构是，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示栈顶元素的当前位置。
栈也可以用链表实现，链式存储结构的栈简称链栈。若同时需两个以上的栈，则最好采用这种结构。对于栈上的操作，总结如下，大家可以仔细看一下这些程序，一个大的程序都是由一些对数据结构的小的操作组成的。
顺序存储的栈的基本操作如下：
判断栈满：
int stackfull(seqstack *s)
{


return (s->top= =stacksize-1);
}


进栈：
void
push(seqstack *s,datatype
x)
{

if (stackfull(s))
error(“stack verflow”);

s->data[++s->top]=x;
}


判断栈空：
int stackempty(seqstack *s)
{

return (s->top= = -1);
}


出栈：
datatype pop(seqstack *s)
{
if (stackempty(s))



error(“stack underflow”);
x=s->data[top];
s->top--;
return (x);
}
链接存储栈：用链表实现的栈，链表第一个元素是栈顶元素，链表的末尾是栈底节点，链表的头指针就是栈顶指针，栈顶指针为空则是空栈。若同时需要两个以上的栈，最好采用链表作存储结构。链接存储的栈的操作如下：


进栈：
Void push(linkstack *p,datatype x)

{

stacknode *q q=(stacknode*)malloc(sizeof(stacknode));

q–>data=x;

q–>next=p–>top;

p–>top=q;
}


出栈：
Datatype
pop(linkstack
*p)
{

datatype
x;

stacknode
*q=p–>top;

if(stackempty(p)

error(“stack underflow.”);

x=q–>data;

p–>top=q–>next;

free(q);

return x;

}


多栈处理
栈浮动技术：
n 个栈共享一个数组空间V[m]
n设立栈顶指针数组 t [n+1] 和
栈底指针数组 b [n+1]，t和b分别指示第 i 个栈的栈顶与栈底，b[n]作为控制量，指到数组最高下标各栈初始分配空间 s = m/n指针初始值
， t[0] = b[0] = -1 ，
b[n] = m-1
，t = b = b[i-1] + s， i = 1, 2, …, n-1 。

cherie

越办越好~~~~~~~~~`  

不变的信仰

精神世界充实。  

清露

呵呵，找个机会...  

ctdsb2011

好帖子，谢楼主

anything

支持一下吧  

土豆

不错哦，顶起  

titmc

顶你一下，好贴要顶！  

土豆

ding   支持  

anything

先看看怎么样！