栈的顺序存储结构

1. 栈的顺序存储和链表存储的差异

顺序存储： 线性表的顺序表：指的是用一组地址连续的存储单元，依次存储线性表的数据元素。
线性表的顺序存储结构具备如下两个基本特征： 1、线性表中的所有元素所占的存储空间是连续的（即要求内存中可用存储单元的地址必须是连续的）。 2、线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 即：线性表逻辑上相邻、物理也相邻（逻辑与物理统一：相邻数据元素的存放地址也相邻），则已知第一个元素首地址和每个元素所占字节数，则可求出任一个元素首地址。 优点： 1、
无须为表示结点间的逻辑关系而增加额外的存储空间。
2、
可以方便的随机存取表中的任一结点。
3、
存储密度大（＝1），存储空间利用率高。 缺点： 1、
插入和删除运算不方便，需移动大量元素。 2、
由于要求占用连续的存储空间，存储分配只能按最大存储空间预先进行，致使存储空间不能得到充分利用。
3、
表的容量难以扩充。 链表存储： 线性表的链式存储：指用一组任意的存储单元存储线性表中的数据元素。
线性表的链式存储结构具备的基本特征： 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 优点： 1、
插入、删除操作很方便，可通过修改结点的指针实现，无须移动元素。
2、
方便扩充存储空间。
缺点： 1、
不能随机存取元素。
2、
存储密度小（<1），存储空间利用率低。 总结： 1、
顺序表适宜于做查找这样的静态操作；
链表宜于做插入、删除这样的动态操作。 2、若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

2. 栈的入栈顺序和出栈顺序的各种可能

栈中的数据只有一种方式出栈，即先进后出，所以出栈的可能数目跟入栈的可能排列数目是一致的。a的出入有2中可能，b的出入有2种可能，c的出入有2种可能，d只需要关系入，只有一种可能。所以可能的出栈方式数为2*2*2*1=8种

入栈顺序：a、b、c、d。出栈顺序可以是：d、c、b、a；a、b、c、d;b、a、c、d很多，但要把栈想象成一个没盖子的纸箱，取出东西时只能从最上层取，放进东西也只能放在最上层，所以栈是一个“后进先出”或“先进后出”的顺序存储结构。

(2)栈的顺序存储结构扩展阅读：

栈的顺序存储结构是利用内存中的一片起始位置确定的连续存储区域来存放栈中的所有元素，另外为了指示栈顶的准确位置，还需要引入一个栈顶指示变量top，采用顺序存储结构的栈称为顺序栈（sequence stack)。设数组data[MAXSIZE]为栈的存储空间，其中MAX-SIZE是一个预先设定的常数，为允许进栈结点的最大可能数目，即栈的容量。

初始时栈空，top等于0。当top不等于0时，data[0]为栈底元素，即为当前停留在栈中时间最长的元素；而data[top-1]为最后入栈的元素，即为栈顶元素。

3. 栈的存储结构

栈同顺序表和链表一样，栈也是用来存储逻辑关系为 "一对一" 数据的线性存储结构。

栈的具体实现
栈是一种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种方式：
顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
链栈：采用链式存储结构实现栈结构；

栈存储结构与之前所学的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：
栈只能从表的一端存取数据，另一端是封闭的；
在栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。

通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素。

4. 栈是不是顺序存储的线性结构啊

不一定。

栈分顺序栈和链式栈。顺序栈为栈的顺序实现，顺序栈为利用顺序存储结构实现的栈。

采用地址连续的存储空间（数组)依次存储栈中数据元素，由于人栈和出栈运算都是在栈顶进行，而栈底位置是固定不变的，可以将栈底位置设置在数组空间的起始处；栈顶位置为随入栈和出栈操作而变化的，故需用一个整型变量top来记录当前栈顶元素在数组中的位置。

链式栈为一种数据存储结构，可以通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。

(4)栈的顺序存储结构扩展阅读

栈作为一种数据结构，为一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

在计算机系统中，栈为一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。

5. 栈的顺序存储结构

这是结果，需要的话给我个邮箱
/*
在vc++6.0中的输出结果：
------------------------
初始化栈.....
创建一个包含5个不大于100的正整数值的栈（5个值由计算机随机产生）...
栈中的元素从栈底到栈顶为：41 67 34 0 69
请输入要插在栈顶的元素e = 100
栈中的元素从栈底到栈顶为：41 67 34 0 69 100
弹出的栈顶元素 e = 100
栈中的元素从栈底到栈顶为：41 67 34 0 69
栈中元素个数是5
输出从栈顶到栈底的所有元素：69 0 34 67 41
Press any key to continue
------------------------------
*/

6. 分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。

顺序存储结构

#include<iostream>
typedef char ElemType;
#define MaxSize 100
using namespace std;
typedef struct
{
ElemType data[MaxSize];
int top;
}sqStack;
void InitStack(sqStack *&s);//初始化栈
void ClearStack(sqStack *&s);//摧毁栈
int StackLength(sqStack *s);//返回栈的长度
bool StackEmpty(sqStack *s);//判断栈是否为空
int Push(sqStack *&s,ElemType e);//进栈
int Pop(sqStack *&s,ElemType &e);//出栈
int GetTop(sqStack *s,ElemType &e);//取栈顶元素
void DispStack(sqStack *s);//显示栈中元素值
int main()
{

return 0;
}

void InitStack(sqStack *&s)//初始化栈
{
s=new sqStack;
s->top=-1;
}
void ClearStack(sqStack *&s)//摧毁栈
{
delete s;
}

int StackLength(sqStack *s)//返回栈的长度
{
return (s->top+1);
}

bool StackEmpty(sqStack *s)//判断栈是否为空
{
return (s->top==-1);
}

int Push(sqStack *&s,ElemType e)//进栈
{
if(s->top==MaxSize-1)
return 0;
s->top++;
s->data[s->top]=e;
return 1;
}

int Pop(sqStack *&s,ElemType &e)//出栈
{
if(s->top==-1)
return 0;
e=s->data[s->top];
s->top--;
return 1;

}

int GetTop(sqStack *s,ElemType &e)//取栈顶元素
{
if(s->top==-1)
return 0;
e=s->data[s->top];
return 1;
}

void DispStack(sqStack *s)//显示栈中元素值
{
for(int i=s->top;i>=0;i--)
cout<<s->data[i]<<" ";
cout<<endl;
}

链式存储结构

typedef char ElemType;

typedef struct linknode
{
ElemType data;
struct linknode *next;
}LiStack;
void InitStack(LiStack *&s);//初始化栈
void ClearStack(LiStack *&s);//摧毁栈
int StackLength(LiStack *s);//返回栈的长度
bool StackEmpty(LiStack *s);//判断栈是否为空
void Push(LiStack *&s,ElemType e);//进栈
int Pop(LiStack *&s,ElemType &e);//出栈
int GetTop(LiStack *s,ElemType &e);//取栈顶元素
void DispStack(LiStack *s);//显示栈中元素值

int main()
{
return 0;
}

void InitStack(LiStack *&s)//初始化栈
{
s=new LiStack;
s->next=NULL;
}

void ClearStack(LiStack *&s)//摧毁栈
{
for(LiStack *p=s->next;p;p=p->next)
{
delete s;
s=p;
p=p->next;
}
delete s;
}

int StackLength(LiStack *s)//返回栈的长度
{
int i=0;
for(LiStack *p=s->next;p;p=p->next)
i++;
return i;
}

bool StackEmpty(LiStack *s)//判断栈是否为空
{
return (s->next==NULL);
}

void Push(LiStack *&s,ElemType e)//进栈
{
LiStack *p=new LiStack;
p->data=e;
p->next=s->next;
s->next=p;
}

int Pop(LiStack *&s,ElemType &e)//出栈
{
LiStack *p;
if(s->next==NULL)
return 0;
p=s->next;
e=p->data;
s->next=p->next;
delete p;
return 1;

}
int GetTop(LiStack *s,ElemType &e)//取栈顶元素
{
if(s->next==NULL)
return 0;
e=s->next->data;
return 1;
}
void DispStack(LiStack *s)//显示栈中元素值
{
LiStack *p=s->next;
for(;p;p=p->next)
cout<<p->data<<" ";
cout<<endl;

}

7. 简述栈和队列的顺序存储结构和链式存储结构的优缺点

顺序存储结构是在内存中开辟一个连续的空间用来存储数据,因此对于内存的需求和苛刻,必须是连续的空间.在数据查找(特别是不按照规律排列的数据),时间复杂度教少.效率高.
链式存储结构是采取连表指针来指示数据的存储位置,这就可以是在内存中随意的存储,没有必须连续储存空间的要求,对于内存的要求相对教容易.但是要是是从小到大顺序排列的数据,链式存储结构的时间复杂度教小,效率高.但是要是不规则排布的数据一般时间复杂度较高,效率更低

8. 栈的入栈和出栈的顺序规律是什么

入栈的顺序规律是排在前面的先进，排在后面的后进。

栈中的数据只有一种方式出栈，即先进后出，所以出栈的可能数目跟入栈的可能排列数目是一致的。a的出入有2中可能，b的出入有2种可能，c的出入有2种可能，d只需要关系入，只有一种可能。所以可能的出栈方式数为2*2*2*1=8种。

入栈顺序：a、b、c、d。出栈顺序可以是：d、c、b、a；a、b、c、d;b、a、c、d很多，但要把栈想象成一个没盖子的纸箱，取出东西时只能从最上层取，放进东西也只能放在最上层，所以栈是一个“后进先出”或“先进后出”的顺序存储结构。

相关介绍：

栈又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。

向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

9. 数据结构中什么叫做顺序栈

顺序栈

栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
1、
顺序栈的类型定义

#define
StackSize
100
//假定预分配的栈空间最多为100个元素

typedef
char
DataType;//假定栈元素的数据类型为字符

typedef
struct{

DataType
data[StackSize];

int
top;

}SeqStack;

注意：
①顺序栈中元素用向量存放

②栈底位置是固定不变的，可设置在向量两端的任意一个端点

③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置
2、
顺序栈的基本操作

前提条件：

设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S-＞data[0]是栈底元素。
（1）
进栈操作

进栈时，需要将S-＞top加1

注意：

①S-＞top==StackSize-1表示栈满
②"
上溢
"现象--当栈满时，再做进栈运算产生空间溢出的现象。

上溢是一种出错状态，应设法避免。
（2）
退栈操作

退栈时，需将S-＞top减1

注意：
①S-＞top<0表示空栈

②"
下溢
"现象——当栈空时，做退栈运算产生的溢出现象。

下溢是正常现象，常用作程序控制转移的条件。
顺序栈在进栈和退栈操作时的具体变化情况【参见动画演示】
3、顺序栈的基本运算
（1）
置栈空

void
InitStack（SeqStack
*S）

{//将顺序栈置空

S->top=-1;

}
（2）
判栈空

int
StackEmpty（SeqStack
*S）

{

return
S->top==-1;

}
（3）
判栈满

int
StackFull（SeqStack
*SS）

{

return
S->top==StackSize-1;

}
（4）
进栈

void
Push（S，x）

{

if
(StackFull(S))

Error("Stack
overflow");
//上溢，退出运行

S->data[++S->top]=x;//栈顶指针加1后将x入栈

}
（5）
退栈

DataType
Pop（S）

{

if(StackEmpty(S))

Error("Stack
underflow");
//下溢，退出运行

return
S->data[S->top--];//栈顶元素返回后将栈顶指针减1

}
（6）
取栈顶元素

DataType
StackTop（S）

{

if(StackEmpty(S))

Error("Stack
is
empty");

return
S->data[S->top];

}
4、两个栈共享同一存储空间

当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。

只有当整个向量空间被两个栈占满（即两个栈顶相遇）时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为 └ m/2┘和┌m/2┐的向量空间比较，前者发生上溢的概率比后者要小得多。

10. 什么是顺序栈

举一个例子吧。入栈顺序：a、b、c、d
出栈顺序可以是：d、c、b、a;a、b、c、d;b、a、c、d很多啦，
但要把栈想象成一个没盖子的纸箱，取出东西时只能从最上层取，放进东西也只能放在最上层，所以栈是一个“后进先出”或“先进后出”的顺序存储结构。