棧

隊(duì)列

解決“假溢出”問題的方法：

采用循環(huán)隊(duì)列方式：將數(shù)組的頭尾看作是相鄰的元素，
即將元素data[0]看作是data[maxlen-1]的下一個(gè)元素。如圖所示。
因此，插入和刪除以及狀態(tài)檢測需要作相應(yīng)的調(diào)整：
插入操作中移動(dòng)指示位置的計(jì)算：
if ( rear+1 == maxlen ) rear = 0;
else rear++;
或者：rear = ( rear + 1 ) % maxlen ;
或者：rear = ( rear + 1 == maxlen ) ? 0 : rear ++ ;
刪除操作：front = ( front + 1 ) % maxlen ;
隊(duì)列空條件： front == rear

入隊(duì)與出隊(duì)：
error_code queue::append(const elementtype x)
{
if ( full() ) return overflow;
rear = ( rear + 1 ) % maxlen ;
data[rear] = x;
count ++;
return success;
}

error_code queue::serve()
{
if ( empty() ) return underflow;
front = ( front + 1 ) % maxlen;
count --;
return success;
}
分析：
算法的時(shí)間復(fù)雜度均為O(1).

鏈棧

class stack{
public: // 函數(shù)成員
stack();
~stack();
bool empty()const;
bool full()const;
error_code get_top(elementtype &x) const;
error_code push(const elementtyoe x);
error_code pop();
private: // 數(shù)據(jù)成員
int count;
node * top; //棧頂指針
};
入棧運(yùn)算的實(shí)現(xiàn) 入棧就是將待插入元素裝入一個(gè)結(jié)點(diǎn)后，連接到鏈表的表頭上。
因此，操作包括：產(chǎn)生結(jié)點(diǎn)；裝入元素的值到結(jié)點(diǎn)中；
連接結(jié)點(diǎn)到表頭–

鏈隊(duì)列

class queue{public: // 函數(shù)成員queue();~queue();bool empty()const;bool full()const;error_code get_front(elmenttype &x)const;error_code append(const elementtype x);error_code serve();private: // 數(shù)據(jù)成員int count;node * front, * rear;

};

算法如下：
error_code queue::append(const elementtype x ){
node *s = new node;
s -> next = NULL;
s -> data = x; // 封裝
rear -> next = s;
rear = s; //插入
count ++;
return success;
}

總結(jié)

以上是生活随笔為你收集整理的【笔记 】栈底层 循环队列的处理 链栈 链队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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