【LeetCode】【數(shù)據(jù)結(jié)構(gòu)】棧與隊(duì)列必刷OJ題

這篇具有很好參考價(jià)值的文章主要介紹了【LeetCode】【數(shù)據(jù)結(jié)構(gòu)】棧與隊(duì)列必刷OJ題。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

【LeetCode】【數(shù)據(jù)結(jié)構(gòu)】棧與隊(duì)列必刷OJ題,LeetCode刷題筆記,數(shù)據(jù)結(jié)構(gòu),leetcode,數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言,c++

??樊梓慕：個(gè)人主頁(yè)

???個(gè)人專(zhuān)欄：《C語(yǔ)言》《數(shù)據(jù)結(jié)構(gòu)》《藍(lán)橋杯試題》《LeetCode刷題筆記》

??每一個(gè)不曾起舞的日子，都是對(duì)生命的辜負(fù)

前言：

【LeetCode】20.有效的括號(hào)（棧的括號(hào)匹配問(wèn)題）

【LeetCode】225.用隊(duì)列實(shí)現(xiàn)棧

【LeetCode】232.用棧實(shí)現(xiàn)隊(duì)列

【LeetCode】622.設(shè)計(jì)循環(huán)隊(duì)列

前言：

本篇文章博主會(huì)給大家推薦幾道棧與隊(duì)列的必刷OJ題，并提供思路分析及原碼（包含棧與隊(duì)列的實(shí)現(xiàn)）。

歡迎大家??收藏??以便未來(lái)做題時(shí)可以快速找到思路，巧妙的方法可以事半功倍。

=========================================================================

GITEE相關(guān)代碼：??fanfei_c的倉(cāng)庫(kù)??

=========================================================================

【LeetCode】20.有效的括號(hào)（棧的括號(hào)匹配問(wèn)題）

原題鏈接：??有效的括號(hào)??

題目：給定一個(gè)只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。

有效字符串需滿(mǎn)足：

左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。

左括號(hào)必須以正確的順序閉合。

每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相同類(lèi)型的左括號(hào)。

根據(jù)棧“先入后出”的特性，我們可以利用棧的數(shù)據(jù)結(jié)構(gòu)進(jìn)行檢驗(yàn)。

當(dāng)遇到左括號(hào)時(shí)，入棧，遇到右括號(hào)出棧。

最后檢查棧中是否還堆積有元素，如果有證明匹配失敗，如果棧空，證明匹配成功。

代碼實(shí)現(xiàn)：

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

// 初始化
void STInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

// 銷(xiāo)毀
void STDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

// 入棧
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->a,newcapacity * sizeof(STDataType));
		if (tmp==NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top]=x;
	ps->top++;
}

// 出棧
void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	ps->top--;
}

// 取棧頂元素
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top-1];
}

// 判空
bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

// 檢驗(yàn)是否匹配
bool isValid(char * s)
{
    ST st;
    STInit(&st);
    char val;
    while(*s)
    {
        if(*s=='('||*s=='{'||*s=='[')
        {
            STPush(&st,*s);// 是左括號(hào) 入棧
        }
        else
        {
            if(STEmpty(&st))// 排除 首個(gè)字符為右括號(hào)的情況
            {
                STDestroy(&st);
                return false;
            }
            val=STTop(&st);// 取棧頂字符判斷
            STPop(&st);
            if((*s==')'&& val!='(')
            ||(*s==']' && val!='[')
            ||(*s=='}' && val!='{'))// 左右括號(hào)不匹配
            {
                STDestroy(&st);
                return false;
            }
        }
        s++;
    }
    bool ret=STEmpty(&st);// 判斷數(shù)量是否匹配
    STDestroy(&st);
    return ret;
}

【LeetCode】225.用隊(duì)列實(shí)現(xiàn)棧

原題鏈接：??用隊(duì)列實(shí)現(xiàn)棧??

題目：請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。

實(shí)現(xiàn) MyStack 類(lèi)：

void push(int x) 將元素 x 壓入棧頂。

int pop() 移除并返回棧頂元素。

int top() 返回棧頂元素。

boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。

首先我們知道隊(duì)列的特性是先入先出，棧的特性是先入后出，題目既然給了我們兩個(gè)隊(duì)列，那么一定是利用這兩個(gè)隊(duì)列進(jìn)行捯數(shù)據(jù)，從而實(shí)現(xiàn)棧先入后出的特性。

思路：

每次入棧，利用不空的隊(duì)列入數(shù)據(jù)；
當(dāng)需要出棧時(shí)，將非空隊(duì)列“出隊(duì)”到空的隊(duì)列上，直到剩余最后一個(gè)元素，取該元素，然后出隊(duì)，即完成出棧動(dòng)作。
當(dāng)需要取棧頂元素時(shí)，只需要取非空隊(duì)列的隊(duì)尾，此時(shí)該隊(duì)尾即為棧頂元素。
當(dāng)需要判空時(shí)，只需要判斷兩個(gè)隊(duì)列是否都為空即可。

注意：該題主要考察的其實(shí)是大家對(duì)于結(jié)構(gòu)的理解，如形參MyStack* obj，實(shí)參對(duì)應(yīng)為&obj->q1或&obj->q2，&操作符的優(yōu)先級(jí)低于->，obj是該棧指針，obj->q1為隊(duì)列結(jié)構(gòu)體，但由于參數(shù)為指針類(lèi)型，所以需要&。

代碼實(shí)現(xiàn)：

// 隊(duì)列的基本函數(shù)
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;

void QueueInit(Que* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

bool QueueEmpty(Que* pq)
{
	assert(pq);

	return pq->head == NULL;
}

void QueueDestroy(Que* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Que* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->tail = pq->head = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

void QueuePop(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

QDataType QueueFront(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

QDataType QueueBack(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

int QueueSize(Que* pq)
{
	assert(pq);

	return pq->size;
}

// 以上為隊(duì)列的基本函數(shù)
// 以下為用隊(duì)列實(shí)現(xiàn)棧

// 定義棧
typedef struct
{
	Que q1;
	Que q2;
} MyStack;

// 創(chuàng)建棧
MyStack* myStackCreate()
{
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&pst->q1);
	QueueInit(&pst->q2);

	return pst;
}

// 入棧
void myStackPush(MyStack* obj, int x)
{
	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}
 
// 出棧
int myStackPop(MyStack* obj)
{
    // 假設(shè)法，假設(shè)q1為空，q2不空
	Que* EmpQue = &obj->q1;
	Que* noEmpQue = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		noEmpQue = &obj->q1;
		EmpQue = &obj->q2;
	}
    // 此時(shí)EmpQue一定為空的隊(duì)列，noEmpQue 一定不為空的隊(duì)列
    
    // 將size-1個(gè)數(shù)據(jù)移動(dòng)到空隊(duì)列中
	while (QueueSize(noEmpQue) > 1)
	{
		QueuePush(EmpQue, QueueFront(noEmpQue));
		QueuePop(noEmpQue);
	}
    //保存返回值
	int ret = QueueFront(noEmpQue);
	QueuePop(noEmpQue);

	return ret;
}

// 取棧頂元素
int myStackTop(MyStack* obj)
{
    // 不空的隊(duì)列的隊(duì)尾即為棧頂
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

// 判空
bool myStackEmpty(MyStack* obj)
{
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

// 銷(xiāo)毀棧
void myStackFree(MyStack* obj)
{
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);

    // free棧之前一定要先銷(xiāo)毀隊(duì)列，否則會(huì)導(dǎo)致內(nèi)存泄露
	free(obj);
}

【LeetCode】232.用棧實(shí)現(xiàn)隊(duì)列

原題鏈接：??用棧實(shí)現(xiàn)隊(duì)列??

題目：請(qǐng)你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列。隊(duì)列應(yīng)當(dāng)支持一般隊(duì)列支持的所有操作（push、pop、peek、empty）：

實(shí)現(xiàn)?MyQueue?類(lèi)：

void push(int x)?將元素 x 推到隊(duì)列的末尾

int pop()?從隊(duì)列的開(kāi)頭移除并返回元素

int peek()?返回隊(duì)列開(kāi)頭的元素

boolean empty()?如果隊(duì)列為空，返回?true?；否則，返回?false

與上面用隊(duì)列實(shí)現(xiàn)棧的思路相似，需要兩個(gè)棧用來(lái)捯數(shù)據(jù)，不同的是，分析過(guò)后你會(huì)發(fā)現(xiàn)這里的兩個(gè)棧，一個(gè)可以固定用來(lái)做入隊(duì)棧（下面統(tǒng)稱(chēng)為pushst），而另外一個(gè)固定用來(lái)做出隊(duì)棧（下面統(tǒng)稱(chēng)為popst）。

思路：

入隊(duì)時(shí)，直接push到pushst即可；
出隊(duì)時(shí)，需要進(jìn)行判斷，當(dāng)popst不為空時(shí)，直接出棧popst，注意保存棧頂元素以便返回；當(dāng)popst為空時(shí)，需要將pushst的數(shù)據(jù)依次捯到popst中，然后出棧popst，同樣注意保存棧頂元素以便返回；
返回隊(duì)頭元素時(shí)，我們可以寫(xiě)一個(gè)返回棧底元素的函數(shù)，然后同樣進(jìn)行判斷，如果popst為空，我們就返回pushst的棧底；如果popst不為空，我們就返回popst的棧頂即可；
判空時(shí)，思路與用隊(duì)列實(shí)現(xiàn)棧相同。

代碼實(shí)現(xiàn)：

typedef struct 
{
    ST s1;//入隊(duì)棧pushst
    ST s2;//出隊(duì)棧popst
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pst->s1);
    STInit(&pst->s2);
    return pst;
}

void myQueuePush(MyQueue* obj, int x) 
{
    STPush(&obj->s1,x);
}

int myQueuePop(MyQueue* obj) 
{
    if(!STEmpty(&obj->s2))
    {
				int x=STTop(&obj->s2);
        STPop(&obj->s2);
        return x;
    }
    else
    {
        while(!STEmpty(&obj->s1))
        {
						int x=STTop(&obj->s1);
            STPop(&obj->s1);
            STPush(&obj->s2,x);
        }
        int y=STTop(&obj->s2);
				STPop(&obj->s2);
        return y;
    }
}

int myQueuePeek(MyQueue* obj) 
{
    if(STEmpty(&obj->s2))
    {
        return STbase(&obj->s1);
    }
    else
    {
        return STTop(&obj->s2);
    }
}

bool myQueueEmpty(MyQueue* obj) 
{
    return STEmpty(&obj->s1)&&STEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) 
{
    STDestroy(&obj->s1);
    STDestroy(&obj->s2);
    free(obj);
}

【LeetCode】622.設(shè)計(jì)循環(huán)隊(duì)列

原題鏈接：??設(shè)計(jì)循環(huán)隊(duì)列??

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

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

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

MyCircularQueue(k): 構(gòu)造器，設(shè)置隊(duì)列長(zhǎng)度為 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ì)列是否已滿(mǎn)。

?由于題目中已經(jīng)明確隊(duì)列長(zhǎng)度，所以定長(zhǎng)數(shù)組是一個(gè)較優(yōu)的解決方案。

該題目最要首先理解的兩個(gè)函數(shù)為判空和判滿(mǎn)。

判空：我們首先肯定會(huì)想到當(dāng)front和rear相等時(shí)，即為空。

?那么問(wèn)題來(lái)了，如何判滿(mǎn)呢？

貌似判空和判滿(mǎn)都可以利用front和rear是否相等來(lái)判斷，如何區(qū)分呢？

判滿(mǎn)：普遍的解決方案為犧牲一個(gè)空間，讓該數(shù)組始終留有一個(gè)空間，用作區(qū)分，那么就有以下幾種情況，請(qǐng)?jiān)囍罁?jù)下圖總結(jié)規(guī)律，得到判滿(mǎn)通用公式。

判滿(mǎn)公式：(rear+1)%(k+1)==front

只要了解了這個(gè)思想，剩下的就簡(jiǎn)單很多了。

代碼實(shí)現(xiàn)：

typedef struct 
{
    int* a;
    int front;
    int rear;
    int k;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->rear=0;
    obj->k=k;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->front==obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->rear+1)%(obj->k+1)==obj->front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->rear]=value;
    obj->rear++;
    obj->rear%=obj->k+1;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front++;
    obj->front%=(obj->k+1);
    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
        return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}

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

=========================================================================

如果你對(duì)該系列文章有興趣的話(huà)，歡迎持續(xù)關(guān)注博主動(dòng)態(tài)，博主會(huì)持續(xù)輸出優(yōu)質(zhì)內(nèi)容

??博主很需要大家的支持，你的支持是我創(chuàng)作的不竭動(dòng)力??

??~ 點(diǎn)贊收藏＋關(guān)注 ~??

=========================================================================?
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-648850.html

到了這里，關(guān)于【LeetCode】【數(shù)據(jù)結(jié)構(gòu)】棧與隊(duì)列必刷OJ題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！