程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++ 棧和隊列的介紹與使用

C++ 棧和隊列的介紹與使用

編輯:C++入門知識

C++ 棧和隊列的介紹與使用


使用標准庫的棧和隊列時,先包含相關的頭文件

#include

#include

定義棧如下:

stack stk;

定義隊列如下:

queue q;

棧提供了如下的操作

s.empty()               如果棧為空返回true,否則返回false
s.size()                返回棧中元素的個數
s.pop()                 刪除棧頂元素但不返回其值
s.top()                 返回棧頂的元素,但不刪除該元素
s.push()                在棧頂壓入新元素

隊列提供了下面的操作

 

q.empty()               如果隊列為空返回true,否則返回false
q.size()                返回隊列中元素的個數
q.pop()                 刪除隊列首元素但不返回其值
q.front()               返回隊首元素的值,但不刪除該元素
q.push()                在隊尾壓入新元素
q.back()                返回隊列尾元素的值,但不刪除該元素

 

c++stack(堆棧)

 

它是一個容器的改編,它實現了一個先進後出的數據結構(FILO)

使用該容器時需要包含#include頭文件;

定義stack對象的示例代碼如下:

stacks1;

stacks2;

stack的基本操作有:

1.入棧:如s.push(x);

2.出棧:如 s.pop().注意:出棧操作只是刪除棧頂的元素,並不返回該元素。

3.訪問棧頂:如s.top();

4.判斷棧空:如s.empty().當棧空時返回true。

5.訪問棧中的元素個數,如s.size();

下面舉一個簡單的例子:

    #include  
    #include  
    using namespace std;  
    int main(void)  
    {  
        stacks;//定義一個棧  
        for(int i=0;i<10;i++)  
            s.push(i);  
        while(!s.empty())  
        {  
            printf("%lf\n",s.top());  
            s.pop();  
        }  
        cout<<"棧內的元素的個數為:"<

棧的定義:

棧是限定僅在表尾進行插入或刪除操作的線性表,因此表尾端成為棧頂,相應的,表頭端成為棧底,不含有任何元素的棧稱為空棧。 棧的修改遵循後進先出的原則,因此棧又稱為後進先出的線性表,簡稱LIFO結構。 棧一般采用數組作為其存儲結構,這樣做可以避免使用指針,簡化程序,當然數組需要預先聲明靜態數據區的大小,但這不是問題,因為即便是頻繁進出入棧操作,任何時刻棧元素的實際個數也不會很多,為棧預留一個足夠大但又不占用太多空間並不是很困難,如果不能做到這一點,那麼節省內存的方法就是使用鏈表存儲棧。 線性表實現棧的基本操作
    #include  
    #include  
    using namespace std;  
    typedef struct Stacknode//定義鏈式棧的結構體  
    {  
        int data;//數據域  
        Stacknode *next;//下一節點的指針域  
    }Stacknode,*Stack;  
    //初始化一個鏈式棧(返回一個鏈式棧的頭節點)  
    Stack InitStack()  
    {  
        Stack stack=(Stack)malloc(sizeof(Stacknode));  
        stack->next=NULL;  
        return stack;  
    }  
    //入棧  
    void Push(Stack stack,int newData)  
    {  
        //判斷是否為空  
        if(stack==NULL)  
        {  
            printf("棧未初始化,請初始化以後再使用\n");  
            return;  
        }  
        //找到最後一個節點  
       Stacknode *lastnode=stack;  
       while(lastnode->next)  
        {  
        lastnode=lastnode->next;  
        }  
       lastnode->next=(Stacknode*)malloc(sizeof(Stacknode*));  
       lastnode->next->data=newData;  
       lastnode->next->next=NULL;  
       printf("入棧成功!\n");  
    }  
    //出棧  
    int Pop(Stack stack)  
    {  
        //判斷棧是否為空  
        if(!stack->next)  
        {  
            printf("棧為空,無法出棧\n");  
            return -1;//-1只是一個自定義的錯誤代碼  
        }  
        //找到最後一個節點的錢一個節點  
        //tempNode:最後一個節點的前一個節點  
        Stacknode *tempNode=stack;  
        while(tempNode->next->next)  
        {  
            tempNode=tempNode->next;  
        }  
        int data=tempNode->next->data;  
        free(tempNode->next);  
        tempNode->next=NULL;  
        return data;  
    }  
      
    int main()  
    {  
        Stack stack=InitStack();  
        Push(stack,3);//3進棧  
        Push(stack,4);//4進棧  
        Push(stack,5);//5進棧  
        printf("%d\n",Pop(stack));  
        printf("%d\n",Pop(stack));  
        printf("%d\n",Pop(stack));  
        printf("%d\n",Pop(stack));//第4次出棧,應該出錯  
        return 0;  
    }  

 

C++ Queue(隊列)

 

queue模版類的定義在頭文件中。

queue與stack模版非常類似,queue模版也需要定義兩個模版參數,一個是元素類型,一個是容器類型,元素類型是必要的,容器類型是可選的,默認為dqueue類型。

定義queue對象的示例代碼如下:

queueq1;

queueq2;

queue的基本操作有:

1.入隊:如q.push(x):將x元素接到隊列的末端;

2.出隊:如q.pop() 彈出隊列的第一個元素,並不會返回元素的值;

3,訪問隊首元素:如q.front()

4,訪問隊尾元素,如q.back();

5,訪問隊中的元素個數,如q.size();

二.優先隊列

頭文件中,還定義了一個非常有用的模版類priority_queue(優先隊列),優先隊列與隊列的差別在於優先隊列不是按照入隊的順序出隊,而是按照隊列中元素的優先權順序出隊(默認為大者優先,也可以通過指定算子來指定自己的優先順序)默認是一個大根堆。

priority_queue模版類有三個模版參數,元素類型,容器類型,比較算子。其中後兩個都可以省略,默認容器為vector,默認算子為less,即小的往前排,大的往後排(出隊時序列尾的元素出隊)。

定義priority_queue對象的示例代碼如下:

priority_queueq1;

priority_queue >q2;

priority_queue,greater >q3;//定義小的先出隊

priority_queue的基本操作均與queue相同

初學者在使用priority_queue時,最困難的可能就是如何定義比較算子了。如果是基本數據類型,或已定義了比較運算符的類,可以直接用STL的less算子和greater算子——默認為使用less算子,即小的往前排,大的先出隊。如果要定義自己的比較算子,方法有多種,這裡介紹其中的一種:重載比較運算符。優先隊列試圖將兩個元素x和y代入比較運算符(對less算子,調用xy),若結果為真,則x排在y前面,y將先於x出隊,反之,則將y排在x前面,x將先出隊。

看下面這個簡單的示例:

    #include  
    #include  
    #include  
    using namespace std;  
    class T  
    {  
    public:  
        int x,y,z;  
        T(int a,int b,int c):x(a),y(b),z(c)  
        {  
        }  
    };  
    bool operator<(const T&t1,const T&t2)  
    {  
        return t1.zq;  
        q.push(T(4,4,3));  
        q.push(T(2,2,5));  
        q.push(T(1,5,4));  
        q.push(T(3,3,6));  
        while(!q.empty())  
        {  
            T t=q.top();  
            q.pop();  
            cout<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved