棧和隊列的簡單介紹

棧

棧是一個“先進(jìn)后出”結(jié)構(gòu)

隊列

入隊演示

隊列是一種“先進(jìn)先出”的結(jié)構(gòu)

出隊演示

接下來我們開始本次的內(nèi)容

棧實現(xiàn)隊列

分析

1.我們可以老老實實的寫一個棧然后將所有的接口函數(shù)實現(xiàn)出來，最后再進(jìn)行實現(xiàn)隊列，但是顯然是效率低下的方法
2.我們使用數(shù)組模擬棧，然后再進(jìn)行實現(xiàn)隊列—可行
3.或者直接使用STL

算法演示

開始實現(xiàn)

class MyQueue {
public:
		//我們不需要使用他的函數(shù)，因為我不想傳參
		//定義兩個stack一個是輸入棧，一個是輸出棧
        stack<int> pushst;
        stack<int> popst;
    MyQueue() {
    }
    
    //將元素輸入到輸入棧中
    void push(int x) {
        pushst.push(x);
    }
    
    int pop() {
        int res;//定義一個int型的值，用來接受返回值
         
         //pop的時候是從輸出棧的棧頂出數(shù)據(jù)
         //如果輸出棧為空，判斷輸入棧有沒有數(shù)據(jù)，只有輸入棧有數(shù)據(jù)的時候才能進(jìn)行轉(zhuǎn)移
         //只有輸出棧有數(shù)據(jù)才能進(jìn)行pop
 		//我們可以將順序進(jìn)行轉(zhuǎn)換，但是需要進(jìn)行重復(fù)的步驟
 		//也就是說，1.一開始popst沒有元素為空，
 		//2.pushst有值，將pushst的元素轉(zhuǎn)移到popst中，
 		//3.在進(jìn)行popst不為空的判斷進(jìn)行pop那么
         //1.3步是相同的操作，如果將2換到最前面，后面只需要緊跟一個1步驟就能完成操作
        if(!popst.size()) 
        {
            while(pushst.size())
            {
                popst.push(pushst.top());
                pushst.pop();
            }
        }
        if(popst.size())
            res=popst.top(),popst.pop();
            return res;
    }
    
    //同上
    int peek() {
        int res;
         
        if(!popst.size()) 
        {
            while(pushst.size())
            {
                popst.push(pushst.top());
                pushst.pop();
            }
            
        }
        if(popst.size())
            res=popst.top();
            return res;
    }   
    
    //當(dāng)pushst和popst同時沒有值的時候->空
    bool empty() {
        if(pushst.size()||popst.size()) return false;
        return true;
    }
};

隊列實現(xiàn)棧

算法演示

進(jìn)棧

出棧

開始實現(xiàn)

c++中queue是雙端隊列，但是我們不適用這個特性，我們一點點的實現(xiàn)

class MyStack {
public:
	
    queue<int> q1,q2;
    MyStack() {

    }
     
    //使用假設(shè)的方式，定義空隊列，進(jìn)行判斷是否與自己的假設(shè)相反，再空的隊列中添加元素
    void push(int x) {
        queue<int>* em=&q1,*noem=&q2;
        if(!em->size()) noem=em,em=&q2;
        em->push(x);
    }
    
    //在pop的時候需要將不為空的隊列找到，然后使隊列中只剩一個元素，其余的元素全部移入另一個隊列中，最后將這個元素記錄并且刪除
    int pop() {
        queue<int>* em=&q1,*noem=&q2;
        if(!noem->size()) em=noem,noem=&q1;
        while(noem->size()>1)
        {
            em->push(noem->front());
            noem->pop();
        }
        int res=0;
        if(noem->size()==1)
        {
            res=noem->front();
            noem->pop();
        }
        return res;
    }
    
    //同上
    int top() {
        queue<int>* em=&q1,*noem=&q2;
        if(!noem->size()) em=noem,noem=&q1;
        while(noem->size()>1)
        {
            em->push(noem->front());
            noem->pop();
        }
        int res=0;
        if(noem->size()==1)
        {
            res=noem->front();
            em->push(noem->front());
            noem->pop();

        }
        return res;
    }
    
    bool empty() {
        if(q1.size()||q2.size()) return false;
        return true;
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

設(shè)計循環(huán)隊列

算法演示

文章來源地址http://www.zghlxwxcb.cn/news/detail-631022.html

開始實現(xiàn)

//使用數(shù)組進(jìn)行實現(xiàn)，結(jié)構(gòu)體需要包含數(shù)組，實際使用的空間個數(shù)，頭，尾
typedef struct {
    int* a;
    int k;
    int hh,tt;
} MyCircularQueue;

//當(dāng)頭和尾重合的時候就是空的時候
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->hh==obj->tt;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tt+1)%(obj->k+1)==obj->hh ;
}   
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* queue=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    queue->a=(int*)malloc(sizeof(int)*(k+1));
    queue->k=k;
    queue->hh=queue->tt=0;
    return queue;
}
//對特殊情況進(jìn)行判斷，當(dāng)tt位于最后一個的時候，需要將他從重新置為開頭
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj)) return false;

    obj->a[obj->tt++]=value;
    obj->tt%=(obj->k+1);
    
    return true;
}
//對特殊情況進(jìn)行判斷，當(dāng)hh位于最后一個的時候，需要將他從重新置為開頭
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) return false;
    
    obj->hh++;
    obj->hh%=(obj->k+1);
    return true;
}   
//如果為空直接返回-1，不為空返回相應(yīng)的值
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) return -1;
    
    return obj->a[obj->hh];
}
//最后一個數(shù)據(jù)是在tt的前一個位置，同時當(dāng)tt位于開頭的時候需要找到最后的位置找值
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) return -1;
    
    return obj->a[(obj->tt+obj->k)%(obj->k+1)];
}


void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之棧和隊列---c++的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！