㈠ 簡述棧和隊列的順序存儲結構和鏈式存儲結構的優缺點
順序棧--入棧操作受數組上界的約束有可能發生棧上溢，且需要地址連續的存儲單元。
鏈棧--無須地址連續，便於多個棧共享存儲單元，且不存在棧滿上溢情況。
順序隊列--需地址連續且有假上溢現象（需改為循環隊列才可解決假上溢）
鏈式隊列--特別適合於數據元素變動比較大的情況，且不存在隊列滿而產生的溢出問題。
㈡ 棧的鏈式存儲結構是什麼
若是棧中元素的數目變化范圍較大或不清楚棧元素的數目，就應該考慮使用鏈式存儲結構。人們將用鏈式存儲結構表示的棧稱作「鏈棧」。鏈棧通常用一個無頭結點的單鏈表表示。由於棧的插入、刪除操作只能在一端進行，而對於單鏈表來說，在首端插入、刪除結點要比在尾端進行相對容易一些，所以將單鏈表的首端作為棧的頂端，即將單鏈表的頭指針作為棧頂指針。鏈棧如圖1所示。
圖1鏈棧的存儲示意
㈢ 分別就棧的順序存儲結構和鏈式存儲結構實現棧的各種基本操作。
順序存儲結構
#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;
}
㈣ 棧的順序存儲和鏈表存儲的差異
順序存儲： 線性表的順序表：指的是用一組地址連續的存儲單元，依次存儲線性表的數據元素。
線性表的順序存儲結構具備如下兩個基本特徵： 1、線性表中的所有元素所佔的存儲空間是連續的（即要求內存中可用存儲單元的地址必須是連續的）。 2、線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。 即：線性表邏輯上相鄰、物理也相鄰（邏輯與物理統一：相鄰數據元素的存放地址也相鄰），則已知第一個元素首地址和每個元素所佔位元組數，則可求出任一個元素首地址。 優點： 1、
無須為表示結點間的邏輯關系而增加額外的存儲空間。
2、
可以方便的隨機存取表中的任一結點。
3、
存儲密度大（＝1），存儲空間利用率高。 缺點： 1、
插入和刪除運算不方便，需移動大量元素。 2、
由於要求佔用連續的存儲空間，存儲分配只能按最大存儲空間預先進行，致使存儲空間不能得到充分利用。
3、
表的容量難以擴充。 鏈表存儲： 線性表的鏈式存儲：指用一組任意的存儲單元存儲線性表中的數據元素。
線性表的鏈式存儲結構具備的基本特徵： 鏈式存儲時，相鄰數據元素可隨意存放，但所佔存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針。 優點： 1、
插入、刪除操作很方便，可通過修改結點的指針實現，無須移動元素。
2、
方便擴充存儲空間。
缺點： 1、
不能隨機存取元素。
2、
存儲密度小（<1），存儲空間利用率低。 總結： 1、
順序表適宜於做查找這樣的靜態操作；
鏈表宜於做插入、刪除這樣的動態操作。 2、若線性表的長度變化不大，且其主要操作是查找，則採用順序表； 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則採用鏈表。
㈤ 簡述棧和隊列的順序存儲結構和鏈式存儲結構的優缺點
順序存儲結構是在內存中開辟一個連續的空間用來存儲數據,因此對於內存的需求和苛刻,必須是連續的空間.在數據查找(特別是不按照規律排列的數據),時間復雜度教少.效率高.
鏈式存儲結構是採取連表指針來指示數據的存儲位置,這就可以是在內存中隨意的存儲,沒有必須連續儲存空間的要求,對於內存的要求相對教容易.但是要是是從小到大順序排列的數據,鏈式存儲結構的時間復雜度教小,效率高.但是要是不規則排布的數據一般時間復雜度較高,效率更低