C++數(shù)據(jù)結(jié)構(gòu)深入探究棧與隊(duì)列

更新時(shí)間：2022年05月11日 16:39:28 作者：舟葉

棧和隊(duì)列，嚴(yán)格意義上來說，也屬于線性表，因?yàn)樗鼈円捕加糜诖鎯壿嬯P(guān)系為 "一對一" 的數(shù)據(jù)，但由于它們比較特殊，本章講解分別用隊(duì)列實(shí)現(xiàn)棧與用棧實(shí)現(xiàn)隊(duì)列

1. 棧

1.1 棧的概念

棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。

壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。

出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

1.2 棧的實(shí)現(xiàn)

棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的代價(jià)比較小。

Stack.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int bool;
#define TRUE 1;
#define FALSE 0;
typedef int STDataType;
struct Stack
{
	STDataType* a;
	int top;       //棧頂
	int capacity;  //容量，方便增容
};
//typedef struct Stack ST;
typedef struct Stack Stack;
//初始化
void StackInit(Stack* pst);
//銷毀
void StackDestroy(Stack* pst);
//入棧
void StackPush(Stack* pst, STDataType x);
//出棧
void StackPop(Stack* pst);
//返回棧頂數(shù)據(jù)
STDataType StackTop(Stack* pst);
//判斷棧是否為空,空返回1非空返回0
//int StackEmpty(Stack* pst);
bool StackEmpty(Stack* pst);
//棧中數(shù)據(jù)個(gè)數(shù)
int StackSize(Stack* pst);

Stack.c
#include "Stack.h"
//初始化
void StackInit(Stack* pst)
{
	assert(pst);
	/*pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;*/
	//開始就申請空間，好處在于空間不夠時(shí)直接容量*2即可(如果剛開始是0就要單獨(dú)處理)
	pst->a = malloc(sizeof(STDataType) * 4);
	pst->top = 0;
	pst->capacity = 4;
}
//銷毀
void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
//入棧
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	//從top為0的位置開始放
	//如果滿了就增容
	if (pst->top == pst->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
		if (tmp == NULL)
		{
			//如果開辟空間失敗
			printf("realloc fail\n");
			exit(-1);//結(jié)束整個(gè)程序(-1表示異常退出)
		}
		pst->a = tmp;
		pst->capacity *= 2;
	}
	//入數(shù)據(jù)
	pst->a[pst->top] = x;
	pst->top++;
}
//出棧
void StackPop(Stack* pst)
{
	assert(pst);//不能是空指針
	assert(!StackEmpty(pst)); //棧內(nèi)還有元素才能出戰(zhàn)
	pst->top--;
}
//返回棧頂數(shù)據(jù)
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];
}
//判斷棧是否為空,空返回1非空返回0
bool StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->top == 0;
}
int StackSize(Stack* pst)
{
	assert(pst);
	return pst->top;
}

test.c
#include "Stack.h"
//對棧操作的測試
void TestStack()
{
	Stack st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	//棧遍歷數(shù)據(jù)
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	//4 3 2 1
	StackDestroy(&st);
}
int main()
{
	TestStack();
	return 0;
}

2. 隊(duì)列

2.1 隊(duì)列的概念

隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出 FIFO(First In First Out)

入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾

出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭

2.2 隊(duì)列的實(shí)現(xiàn)

Queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int QDataType;
//隊(duì)列中的一個(gè)結(jié)點(diǎn)
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;
//隊(duì)列(由于需要兩個(gè)指針，所以用結(jié)構(gòu)體定義)
typedef struct Queue
{
	QueueNode* head; //頭指針
	QueueNode* tail; //尾指針
}Queue;
//初始化
void QueueInit(Queue* pq);
//銷毀
void QueueDestroy(Queue* pq);
//入隊(duì)
void QueuePush(Queue* pq, QDataType x);
//出隊(duì)
void QueuePop(Queue* pq);
//取隊(duì)頭數(shù)據(jù)
QDataType QueueFront(Queue* pq);
//取隊(duì)尾數(shù)據(jù)
QDataType QueueBack(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//計(jì)算隊(duì)列元素個(gè)數(shù)
int QueueSize(Queue* pq);

Queue.c
#include "Queue.h"
//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	//不帶哨兵位
	pq->head = pq->tail = NULL;
}
//銷毀
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL; //等于空就為真, 不為空就是假
}
//入隊(duì)
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)//申請空間失敗
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
//出隊(duì)
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//空隊(duì)列也不能調(diào)用出隊(duì)操作
	if (pq->head->next == NULL)//只有一個(gè)結(jié)點(diǎn)的情況(如果不單獨(dú)考慮，那當(dāng)只有一個(gè)結(jié)點(diǎn)時(shí)，tail會仍然指向曾經(jīng)的隊(duì)尾)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
//取隊(duì)頭數(shù)據(jù)
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
//取隊(duì)尾數(shù)據(jù)
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
int QueueSize(Queue* pq)
{
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

test.c
#include "Queue.h"
//對隊(duì)列操作的測試
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	printf("%d\n", QueueSize(&q)); //4
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	//1 2 3 4
	QueueDestroy(&q);
}
int main()
{
	TestQueue();
	return 0;
}

3. 棧和隊(duì)列面試題

3.1 括號匹配問題

bool isValid(char * s)
{
    Stack st;
    StackInit(&st);
    while(*s)
    {
        //左括號入棧，右括號找最近的左括號匹配
        if(*s == '[' || *s == '(' || *s == '{')
        {
            StackPush(&st, *s);
            s++;
        }
        else
        {
            if(StackEmpty(&st))//只有后括號的情況
            {
                StackDestroy(&st);
                return false;
            }
            char top = StackTop(&st);
            //不匹配的情況
            if ( (top == '[' && *s != ']') 
            || (top == '(' && *s != ')')
            || (top == '{' && *s != '}') ) 
            {
                StackDestroy(&st);
                return false;
            }
            else //匹配的情況
            {
                StackPop(&st);
                s++;
            }
        }
    }
    //如果最后棧內(nèi)為空才說明是匹配的(防止最后棧內(nèi)還剩下前括號的情況)
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
    //特別注意:在return之前需要先把棧銷毀掉
}

3.2用隊(duì)列實(shí)現(xiàn)棧

//思路:
//入棧: 向不為空的隊(duì)列入數(shù)據(jù),始終保持另一個(gè)隊(duì)列為空
//出棧: 前size-1個(gè)數(shù)據(jù)導(dǎo)入空隊(duì)列，刪除最后一個(gè)
typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;
//*為什么下面代碼傳參都要傳&obj->q1/q2？
//因?yàn)閼?yīng)該傳入函數(shù)中的是隊(duì)列的指針
MyStack* myStackCreate() 
{
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}
void myStackPush(MyStack* obj, int x)
{
    //往不為空的隊(duì)列里入數(shù)據(jù)
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}
int myStackPop(MyStack* obj) 
{
    //假設(shè)q1為空q2不為空
    Queue* pEmpty = &obj->q1;
    Queue* pNonEmpty = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        pEmpty = &obj->q2;
        pNonEmpty = &obj->q1;
    }
    //取出前size-1個(gè)插入空隊(duì)列
    while(QueueSize(pNonEmpty) > 1)
    {
        QueuePush(pEmpty, QueueFront(pNonEmpty));
        QueuePop(pNonEmpty);
    }
    //"干掉"最后一個(gè)
    int front = QueueBack(pNonEmpty);
    QueuePop(pNonEmpty);
    return front;
}
int myStackTop(MyStack* obj) 
{
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}
bool myStackEmpty(MyStack* obj) 
{
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) 
{
    //先釋放兩個(gè)隊(duì)列，再釋放malloc出來的結(jié)構(gòu)體
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

3.3 用棧實(shí)現(xiàn)隊(duì)列

typedef struct 
{
    Stack pushST;
    Stack popST;
} MyQueue;
MyQueue* myQueueCreate() 
{
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushST);
    StackInit(&q->popST);
    return q;
}
void myQueuePush(MyQueue* obj, int x)
{
    //不管棧內(nèi)有沒有數(shù)據(jù)，只要是入隊(duì)操作就向Push棧入數(shù)據(jù)即可
    StackPush(&obj->pushST, x);
}
//獲取隊(duì)頭數(shù)據(jù)
int myQueuePeek(MyQueue* obj) 
{
    //如果pop棧為空,先把push棧數(shù)據(jù)導(dǎo)入pop棧
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}
//出隊(duì)
int myQueuePop(MyQueue* obj) 
{
    //如果pop棧為空,先把push棧數(shù)據(jù)導(dǎo)入pop棧
    /*if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    */
    //復(fù)用
    int top = myQueuePeek(obj);//易錯(cuò)點(diǎn):不能寫&obj->popST,因?yàn)樵搨魅腙?duì)列的指針
    StackPop(&obj->popST);
    return top;
}
bool myQueueEmpty(MyQueue* obj) 
{
    //push棧和pop棧同時(shí)為空,隊(duì)列才為空
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj)
{
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}

3.4 設(shè)計(jì)循環(huán)隊(duì)列

題目描述：

設(shè)計(jì)你的循環(huán)隊(duì)列實(shí)現(xiàn)。循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。它也被稱為“環(huán)形緩沖器”。

循環(huán)隊(duì)列的一個(gè)好處是我們可以利用這個(gè)隊(duì)列之前用過的空間。在一個(gè)普通隊(duì)列里，一旦一個(gè)隊(duì)列滿了，我們就不能插入下一個(gè)元素，即使在隊(duì)列前面仍有空間。但是使用循環(huán)隊(duì)列，我們能使用這些空間去存儲新的值。

你的實(shí)現(xiàn)應(yīng)該支持如下操作：

MyCircularQueue(k): 構(gòu)造器，設(shè)置隊(duì)列長度為 k 。

Front: 從隊(duì)首獲取元素。如果隊(duì)列為空，返回 -1 。

Rear: 獲取隊(duì)尾元素。如果隊(duì)列為空，返回 -1 。

enQueue(value): 向循環(huán)隊(duì)列插入一個(gè)元素。如果成功插入則返回真。

deQueue(): 從循環(huán)隊(duì)列中刪除一個(gè)元素。如果成功刪除則返回真。

isEmpty(): 檢查循環(huán)隊(duì)列是否為空。

isFull(): 檢查循環(huán)隊(duì)列是否已滿。

//循環(huán)隊(duì)列是邏輯上的循環(huán)(數(shù)組、鏈表都可以實(shí)現(xiàn),本題使用數(shù)組)
//永遠(yuǎn)空出一個(gè)位置不存儲數(shù)據(jù)(目的是區(qū)分空和滿)
//當(dāng)front = tail說明循環(huán)隊(duì)列空
//當(dāng)tail+1 = front說明循環(huán)隊(duì)列滿
typedef struct 
{
    int* a;     //數(shù)組
    int k;      //循環(huán)隊(duì)列最多能存多少個(gè)數(shù)據(jù)
    int front;  //頭指針
    int tail;   //尾指針(隊(duì)尾數(shù)據(jù)的下一個(gè)位置)
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int)*(k+1)); //需要多開一個(gè)空間
    obj->front = 0;
    obj->tail = 0;
    obj->k = k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->front == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    int tailNext = obj->tail + 1;
    if(tailNext == obj->k+1)
    {
        //如果tail已經(jīng)走到尾(不存放數(shù)據(jù)的位置),此時(shí)認(rèn)為tailNext回到了數(shù)組首元素位置
        tailNext = 0;
    }
 
    return tailNext == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        obj->a[obj->tail] = value;
        obj->tail++;
 
        if(obj->tail == obj->k+1) //也可以取模  
        {
            obj->tail = 0;
        }
        /* //取模
        obj->tail %= (obj->k+1);
        */
 
        return true;
    }
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))//如果obj為空了就不能出數(shù)據(jù)
    {
        return false;
    }
    else
    {
        obj->front++;
        //極端情況:front加到尾后重新回到數(shù)組首元素
        if(obj->front == obj->k+1)
        {
            obj->front = 0;
        }
        return true;
    }
}
int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->a[obj->front];
    }
}
int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        //由于取尾需要去tail的前一個(gè),那么當(dāng)tail就在首元素的時(shí)候,要把它挪到最后一個(gè)元素的位置去
        int tailPrev = obj->tail - 1;
        if(tailPrev == -1)
        {
            tailPrev = obj->k;
        }
        return obj->a[tailPrev];
    }
}
void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->a);
    free(obj);
}

到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)深入探究棧與隊(duì)列的文章就介紹到這了,更多相關(guān)C++棧與隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: