棧採用鏈式存儲結構

⑴ 棧只能順序存儲，這句話對嗎，為什麼

棧只能順序存儲，這句話不對。棧作為一種數據結構，是一種只能在一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)。

一個新元素只能從棧頂一端進入，刪除時，只能刪除棧頂的元素，即剛剛被插入的元素。所以棧也稱為後進先出表。線性表可以順序存儲，也可以鏈式存儲，因此棧也可以採用鏈式存儲結構。

(1)棧採用鏈式存儲結構擴展閱讀：

棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為後進先出表。

在計算機系統中，棧則是一個具有以上屬性的動態內存區域。程序可以將數據壓入棧中，也可以將數據從棧頂彈出。在i386機器中，棧頂由稱為esp的寄存器進行定位。壓棧的操作使得棧頂的地址減小，彈出的操作使得棧頂的地址增大。

棧在程序的運行中有著舉足輕重的作用。最重要的是棧保存了一個函數調用時所需要的維護信息，這常常稱之為堆棧幀或者活動記錄。堆棧幀一般包含如下幾方面的信息：

1、函數的返回地址和參數。

2、臨時變數：包括函數的非靜態局部變數以及編譯器自動生成的其他臨時變數。

鏈式存儲結構的特點：

1、比順序存儲結構的存儲密度小(鏈式存儲結構中每個結點都由數據域與指針域兩部分組成，相比順序存儲結構增加了存儲空間)。

2、邏輯上相鄰的節點物理上不必相鄰。

3、插入、刪除靈活 (不必移動節點，只要改變節點中的指針)。

4、查找節點時鏈式存儲要比順序存儲慢。

5、每個節點是由數據域和指針域組成。

6、由於簇是隨機分配的，這也使數據刪除後覆蓋幾率降低，恢復可能提高。

順序存儲結構的主要優點是節省存儲空間，因為分配給數據的存儲單元全用存放結點的數據（不考慮c/c++語言中數組需指定大小的情況），結點之間的邏輯關系沒有佔用額外的存儲空間。

採用這種方法時，可實現對結點的隨機存取，即每一個結點對應一個序號，由該序號可以直接計算出來結點的存儲地址。但順序存儲方法的主要缺點是不便於修改，對結點的插入、刪除運算時，可能要移動一系列的結點。

參考資料：網路-棧

參考資料：網路-鏈式存儲結構

參考資料：網路-順序存儲結構

⑵ 帶鏈棧是什麼

棧也是線性表，也可以採用鏈式存儲結構。帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結點，這種帶鏈的棧稱為可利用棧。

⑶ 簡述棧和隊列的順序存儲結構和鏈式存儲結構的優缺點

順序存儲結構是在內存中開辟一個連續的空間用來存儲數據,因此對於內存的需求和苛刻,必須是連續的空間.在數據查找(特別是不按照規律排列的數據),時間復雜度教少.效率高.
鏈式存儲結構是採取連表指針來指示數據的存儲位置,這就可以是在內存中隨意的存儲,沒有必須連續儲存空間的要求,對於內存的要求相對教容易.但是要是是從小到大順序排列的數據,鏈式存儲結構的時間復雜度教小,效率高.但是要是不規則排布的數據一般時間復雜度較高,效率更低

⑷ 棧的存儲結構

棧同順序表和鏈表一樣，棧也是用來存儲邏輯關系為 "一對一" 數據的線性存儲結構。

棧的具體實現
棧是一種 "特殊" 的線性存儲結構，因此棧的具體實現有以下兩種方式：
順序棧：採用順序存儲結構可以模擬棧存儲數據的特點，從而實現棧存儲結構；
鏈棧：採用鏈式存儲結構實現棧結構；

棧存儲結構與之前所學的線性存儲結構有所差異，這緣於棧對數據 "存" 和 "取" 的過程有特殊的要求：
棧只能從表的一端存取數據，另一端是封閉的；
在棧中，無論是存數據還是取數據，都必須遵循"先進後出"的原則，即最先進棧的元素最後出棧。

通常，棧的開口端被稱為棧頂；相應地，封口端被稱為棧底。因此，棧頂元素指的就是距離棧頂最近的元素。

⑸ 鏈棧如何構造，鏈棧新結點如何進棧

鏈式棧就是用鏈式存儲結構表示一個棧，也就是指針域。
根據棧的性質，知道棧是先進後出，所以只需要設置一個棧頂指針，還是說點C++吧
先構造一個結構模板
template<class
ElemType>
typedef
struct
Node
//建立
{
ElemType
data;//數據成員，用於存儲
struct
Node*next;//指針成員，用於連接邏輯結構
}LNode;
1.構造一個空棧，只需要：
LNode*head;//定義棧頂指針
head=(LNode*)malloc(sizeof(LNode));//分配空間
head->next=NULL;//下一個為空
2.新節點：比如新節點數據位1
入棧操作：
LNode*p;
p->data=1;
p->next=head;
head=p;
總之有點類似C語言里的鏈表
還有什麼不清楚的可以追問
希望對你有所幫助！！！

⑹ 請問「多個棧共存時,最好用鏈式存儲空間作為存儲結構」，這是為什麼啊

如果只有兩個棧，則可以將一個放在數組的低空間，一個放在高空間，兩者從兩頭向中間擴展，這樣沒有空間浪費
如果多於兩個棧時，還是採用順序存儲，則一個滿了另外棧空間雖然有空，但是必須要移動棧中元素才能使用別的浪費的空間，這樣演算法的效率就不高了，此時不如直接採用鏈接存儲好了

⑺ 棧和隊列通常採用的兩種存儲形式是

順序存儲結構和鏈式存儲結構

⑻ 分別就棧的順序存儲結構和鏈式存儲結構實現棧的各種基本操作。

順序存儲結構

#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;

}

⑼ 鏈棧和順序棧兩種存儲結構有什麼不同

存儲結構不同：
鏈棧動態分配內存存儲數據，不浪費內存，存儲的數據不連續。
順序棧使用固定大小數組保存數據，數據量小時浪費內存，過多時出問題，存儲數據連續。

它們的具體區別如下：
順序棧的實現在於使用了數組這個基本數據結構，數組中的元素在內存中的存儲位置是連續的，且編譯器要求我們在編譯期就要確定數組的大小，這樣對內存的使用效率並不高，一來無法避免因數組空間用光而引起的溢出問題。在系統將內存分配給數組後，則這些內存對於其他任務就不可用。而對於鏈棧而言，使用了鏈表來實現棧，鏈表中的元素存儲在不連續的地址，由於是動態申請內存，所以我們可以以非常小的內存空間開始，另外當某個項不使用時也可將內存返還給系統。

⑽ 簡述棧和隊列的順序存儲結構和鏈式存儲結構的優缺點

順序棧--入棧操作受數組上界的約束有可能發生棧上溢，且需要地址連續的存儲單元。
鏈棧--無須地址連續，便於多個棧共享存儲單元，且不存在棧滿上溢情況。
順序隊列--需地址連續且有假上溢現象（需改為循環隊列才可解決假上溢）
鏈式隊列--特別適合於數據元素變動比較大的情況，且不存在隊列滿而產生的溢出問題。