簡單定義：棧就是一種只允許在表尾進行插入和刪除操作的線性表

如何理解棧的概念

① 舉一個生活中的例子：我在一個儲物箱中，堆了一堆衣服，我的一件球衣在最下面，而我要拿這件衣服，就意味著我必須將上面的衣服全部拿出來才可以，但是由于箱子只有一個口，我也只能從上面拿東西，心里還默默想著，當初就不該將球衣早早的放進去，導致結(jié)果就是先進后出！

你就不能舉個計算機中的例子？這就安排！

② 計算機中很多操作都是使用棧的原理來實現(xiàn)的，我們就比如常見的瀏覽器中的 “前進鍵” “后退鍵” 就可以利用棧的原理來實現(xiàn)，我們來用圖說明一下

我們想要實現(xiàn)前進后退，可以使用兩個棧（暫時稱作 M、N）來實現(xiàn)

• 我們分別瀏覽了頁面A、頁面B、頁面C，所以我們將這些頁面依次壓入棧，即圖中打開頁面部分

• 當用戶點擊后退時，我們需要退回到頁面B中去，但是由于頁面C在B上方，我們就必須將頁面C從棧M中先彈出，放到棧N中，即圖中后退部分

• 但是如果用戶突然又想回到頁面C去，原理相似的，只需要把棧N中的頁面C彈出，重新壓入棧M即可

• 而如果用戶在瀏覽B界面的時候，打開了新的界面D，那么C就無法通過前進后退訪問了，所以棧M中壓入頁面D的同時還需要清空棧N

image

棧的術(shù)語說明

棧頂：允許進行插入和進行刪除操作的一段成為棧頂

棧底：表的另一端稱為棧底 （第一個元素進入的位置）

壓棧：在棧頂位置插入元素的操作叫做壓棧，或入棧、進棧

出棧：刪除棧頂元素的操作叫做出棧，也叫作彈棧，或者退棧

空棧：不含元素的空表

棧溢出：當棧滿的時候，如果再有元素壓棧，則發(fā)生上溢，當?？盏臅r候，再出棧則發(fā)生下溢

image

棧的抽象數(shù)據(jù)類型

#ifndef _STACK_H_
#define _STACK_H_
#include <exception>
using namespace std;


template <class T>
class Stack { 
public: 
    virtual bool empty() const = 0; 
    virtual int size() const = 0; 
    virtual void push(const T &x) = 0; 
    virtual T  pop() = 0;              
    virtual T getTop() const = 0;  
    virtual void clear() =0;
    virtual ~Stack() {}
};

/*
    自定義異常類
*/

// 用于檢查范圍的有效性
class outOfRange:public exception {
public:    
   const char* what()const throw()    
   {    return "ERROR! OUT OF RANGE.\n";    } 
};  

// 用于檢查長度的有效性
class badSize:public exception {
public:    
   const char* what()const throw()    
   {    return "ERROR! BAD SIZE.\n";    }  
};

#endif

順序?！獥５捻樞虼鎯Y(jié)構(gòu)

開頭我們就已經(jīng)提過了，棧實際上就是一種線性表的特例，所以棧的實現(xiàn)和線性表一樣，均使用數(shù)組實現(xiàn)，我們使用一個一維數(shù)組來存儲元素，那么總得有個頭阿，我們就需要確定棧底的位置，通常我們選擇 0 的一端作為棧底，這樣更加方便理解與操作，特別的是，我們設(shè)置了一個整型變量top 用來存放棧頂元素的位置（下標），也稱作棧頂指針

(一) 順序棧的類型描述

初始的時候，給top賦值-1，表示棧為空，元素進棧以后，top + 1，元素出棧后，top - 1

//  array-based stack: definition and implementation for some methods 
 
#ifndef _SEQSTACK_H_
#define _SEQSTACK_H_

#include "Stack.h" 
 
template <class T>   
class seqStack : public Stack<T> {       
private:
    T * data;
    int top;
    int maxSize;
    void resize();
public:
    seqStack(int initSize = 100) {
        if(initSize<=0) throw badSize();
        data = new T[initSize];
        maxSize = initSize ;    
        top = -1;  
    }      
    ~seqStack(){ delete [] data;}
    bool empty() const{ return top == -1;}      
    int size() const{ return top + 1; } 
    void clear() { top = -1; }              // 清空棧內(nèi)容 
    void push(const T &value);   
    T  pop();   
    T  getTop() const;        
}; 

#endif

(二) 進棧

template <class T>
void seqStack<T>::push(const T &value) {    
    if (top == maxSize - 1) resize();
    data[++top] = value;
}   

(三) 出棧

template <class T>
T seqStack<T>::pop() {  
    if(empty())throw outOfRange();
    return data[top--]; 
}   

(四) 取棧頂元素

template <class T>
T seqStack<T>::getTop() const{
    if(empty())throw outOfRange();
    return data[top];
}

(五) 擴容

template <class T>
void seqStack<T>::resize(){
    T * tmp = data;
    data = new T[2 * maxSize];
    for (int i = 0; i < maxSize; ++i)
        data[i] = tmp[i];
    maxSize *= 2;
    delete[] tmp;
} 

(六) 兩棧共享空間

棧這種數(shù)據(jù)結(jié)構(gòu)相比較于線性表，沒了有插入和刪除的時候需要移動元素的情況，但是仍然有一個比較大的不足，那就是我們必須事先分配空間大小，如果一旦空間滿了，再有元素近棧就必須使用編程手段對數(shù)組進行擴容，還是比較麻煩的

而有時候我們往往需要多個棧，我們之前的處理手段就是盡量的根據(jù)實際問題設(shè)計大小合適的數(shù)組，但是這顯然是有一定難度的，而且常常是這樣的，一個棧已經(jīng)滿了，而另一個?？赡苓€空著很多空間，如果能將那些空閑的位置利用起來就好了，而我們下面就要來提到一個這樣的技巧的思路

image

我們其實就是將兩個棧的棧底全部放到了，數(shù)組的兩端，然后兩個棧處于相向位置，逐漸向中間靠攏，只要兩個top指針不相遇，兩個棧就可以一直用

鏈棧——棧的鏈式存儲結(jié)構(gòu)

鏈棧就是使用鏈式存儲結(jié)構(gòu)的棧，和我們在單鏈表中的鏈式存儲的感覺相似，我們會設(shè)置一個指向棧頂?shù)闹羔榯op，同時當top == NULL時為空棧

image

(一) 鏈棧的類型定義

#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
#include <iostream> 

#include "Stack.h" 

template <class T>
class linkStack : public Stack<T> 
{
private:
    struct Node {
        T data;
        Node* next;
        Node(){ next = NULL; }
        Node(const T &value, Node *p = NULL){ data = value; next = p;}
    };
    Node* top;
public:
    linkStack(){ top = NULL; }
    ~linkStack(){ clear(); }
    void clear();
    bool empty()const{ return top == NULL; }
    int size()const;
    void push(const T &value);
    T  pop();
    T getTop()const;
};
#endif

(二) 清空棧

template <class T>
void linkStack<T>::clear() {
    Node *p;
    while (top != NULL) {
        p = top;
        top = top->next;
        delete p;
    }
}

（三) 求棧中元素個數(shù)

template <class T>
int linkStack<T>::size()const {
    Node *p = top;
    int count = 0;
    while (p){
        count++;
        p = p->next;
    }
    return count;
}

(四) 進棧

template <class T>
void linkStack<T>::push(const T &value) {
    Node *p = new Node(value, top);
    top = p; 
}

(五) 出棧

template <class T>
T linkStack<T>::pop() {
    if (empty())throw outOfRange();
    Node *p = top;
    T value = p->data;
    top = top->next;
    delete p;
    return value;
}

(六) 獲取棧頂元素

template <class T>
    T linkStack<T>::getTop() const { 
    if(empty())throw outOfRange();
    return top->data;
}

結(jié)尾：

如果文章中有什么不足，或者錯誤的地方，歡迎大家留言分享想法，感謝朋友們的支持！

如果能幫到你的話，那就來關(guān)注我吧！如果您更喜歡微信文章的閱讀方式，可以關(guān)注我的公眾號

在這里的我們素不相識，卻都在為了自己的夢而努力 ?

一個堅持推送原創(chuàng)開發(fā)技術(shù)文章的公眾號：理想二旬不止

image