棧的兩種存儲(chǔ)結(jié)構(gòu)

棧的特點(diǎn)：

在固定一端進(jìn)行插入刪除，在棧頂進(jìn)行

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義（不帶頭結(jié)點(diǎn)）：

class StackNode { public:int data;StackNode *next;StackNode():next(NULL){}}; class StackLine { public:StackNode *top;int count;StackLine():top(NULL),count(0){}//無初始化函數(shù)因?yàn)闊o需頭結(jié)點(diǎn)void pop(StackLine *t);void push(StackLine *t,int x);bool isempty(StackLine *t);int Get_Top(StackLine *t); }; 鏈?zhǔn)綏＝Y(jié)構(gòu)定義

出棧操作： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

入棧操作：

判斷棧空：top是否等于NULL

根據(jù)上述寫出鏈?zhǔn)浇Y(jié)構(gòu)的基本操作，同時(shí)設(shè)置計(jì)數(shù)器來計(jì)算堆棧的元素個(gè)數(shù)

#include<iostream> #include<string> #include<cstring> using namespace std; //鏈棧結(jié)構(gòu)書上為帶頭節(jié)點(diǎn)的鏈棧結(jié)構(gòu)，此為不帶頭結(jié)點(diǎn)的鏈棧結(jié)構(gòu) class StackNode { public:int data;StackNode *next;StackNode():next(NULL){}}; class StackLine { public:StackNode *top;int count;StackLine():top(NULL),count(0){}//無初始化函數(shù)因?yàn)闊o需頭結(jié)點(diǎn)void pop(StackLine *t);void push(StackLine *t,int x);bool isempty(StackLine *t);int Get_Top(StackLine *t); }; void StackLine::pop(StackLine *t) {if (t->count == 0)cout << "此時(shí)棧空\(chéng)n";else {StackNode *tem;tem = t->top;//top指向待釋放的節(jié)點(diǎn)top = t->top->next;//順序?yàn)橄却_定指向在釋放節(jié)點(diǎn)delete tem;}t->count--; } void StackLine::push(StackLine *t, int x) {//創(chuàng)建一個(gè)新節(jié)點(diǎn)再確定指向StackNode *s = new StackNode();s->data = x;if (t->count!=0){//棧非空s->next = t->top;t->top = s;}else {//棧空s->next = NULL;t->top = s;}t->count++; } bool StackLine::isempty(StackLine *t) {if (t->count == 0)return true;else return false; } int StackLine::Get_Top(StackLine *t) {return t->top->data;}

順序存儲(chǔ)結(jié)構(gòu)：

如下圖所示，數(shù)組大小為max=5，用top變量來指示棧頂元素

備注：在進(jìn)行入棧操作時(shí)，

1.stack.s[s.top]=x;

?2. s.top++;

這兩句語句的執(zhí)行順序可以不同，具體情況根據(jù)top初始化的值來確定：若top=-1,則2語句先執(zhí)行，若top=0,則語句1先執(zhí)行

?

?則順序結(jié)構(gòu)基本操作：

#include<iostream> #include<string> #include<cstring> const int max = 100; using namespace std; class Stack { public:int s[max];int top;Stack(){top = -1;memset(s,0,sizeof(s));}//構(gòu)造函數(shù)void push(int x);void pop();int Get_Top();bool Notempty();}; void Stack::push(int x) {//判斷有效性if (top>=max-1)cout << "棧滿\n";else s[++top] = x; }//top位置 void Stack::pop() {//判斷有效性if (top <=-1)cout << "棧空\(chéng)n";else --top; } int Stack::Get_Top() {//取棧頂元素的操作應(yīng)發(fā)生在判斷非空之后return s[top ]; } bool Stack::Notempty() {if (top == -1)return false;else return true; } 順序結(jié)構(gòu)頭文件

測(cè)試主函數(shù)

#include<iostream> #include<string> #include"順序.h" #include"鏈表.h" using namespace std; //節(jié)點(diǎn)數(shù)據(jù)域均為int類型 int main() {//測(cè)試順序存儲(chǔ)結(jié)構(gòu)/*Stack *testone=new Stack();for (int i = 0; i < 5; i++)testone->push(i);cout << "此時(shí)棧頂元素為:" << testone->Get_Top() << endl;;cout << "棧中元素依次出棧\n";while (testone->Notempty())//非空{(diào)cout << testone->Get_Top() << " ";testone->pop();}*///測(cè)試鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)StackLine *testtwo = new StackLine();for (int i = 0; i < 5; i++)testtwo->push(testtwo,i);cout << "此時(shí)棧頂元素為:" << testtwo->Get_Top(testtwo) << endl;while (!testtwo->isempty(testtwo))//非空 {cout << testtwo->Get_Top(testtwo) << " ";testtwo->pop(testtwo);}}

重點(diǎn)理解：

1.在棧頂一端進(jìn)行插入刪除操作，在兩種存儲(chǔ)結(jié)構(gòu)下，插入刪除操作均在top指向的棧頂一端進(jìn)行操作

2.同時(shí)top指向棧頂元素

?堆棧習(xí)題：

重點(diǎn)理解為：求堆棧無論順序存儲(chǔ)或鏈?zhǔn)蕉褩Ｖ泄?jié)點(diǎn)個(gè)數(shù)時(shí)，利用堆棧彈出元素直至棧空為止。

則傳入的不是指針類型參數(shù)，即在求節(jié)點(diǎn)的函數(shù)中可對(duì)堆棧改變，而不能將此改變傳入主函數(shù)中改變堆棧的結(jié)構(gòu)。

實(shí)則也是對(duì)指針的理解

轉(zhuǎn)載于:https://www.cnblogs.com/zlspace/p/6919975.html

總結(jié)

以上是生活随笔為你收集整理的栈的两种存储结构的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。