【笔记】栈底层循环队列的处理链栈链队列

╰半橙微兮° 2022-10-22 02:51 150阅读 0赞

## 栈 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]

## 队列 ##

### 解决“假溢出”问题的方法： ###

采用循环队列方式：将数组的头尾看作是相邻的元素，  
即将元素data\[0\]看作是data\[maxlen-1\]的下一个元素。如图所示。  
因此，插入和删除以及状态检测需要作相应的调整：  
插入操作中移动指示位置的计算：  
if ( rear+1 == maxlen ) rear = 0;  
else rear++;  
或者：rear = ( rear + 1 ) % maxlen ;  
或者：rear = ( rear + 1 == maxlen ) ? 0 : rear ++ ;  
删除操作：front = ( front + 1 ) % maxlen ;  
队列空条件： front == rear

入队与出队：  
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;  
\}  
分析：  
算法的时间复杂度均为O(1).

## 链栈 ##

class stack\{  
public: // 函数成员  
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: // 数据成员  
int count;  
node \* top; //栈顶指针  
\};  
入栈运算的实现 入栈就是将待插入元素装入一个结点后，连接到链表的表头上。  
因此，操作包括：产生结点；装入元素的值到结点中；  
连接结点到表头–

# 链队列 #

class queue{
          public:     // 函数成员
                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:           // 数据成员
               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;  
\}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]: /images/20221022/1b98e986858347a1a1c5dd6f1084e39d.png