題目一：括號匹配問題

?給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字串 s ，判斷字串是否有效，
有效字串需滿足：
?1.左括號必須用相同型別的右括號閉合，
?2.左括號必須以正確的順序閉合，

要求：
?時間復雜度：O(n)

思路：
?該題是堆疊的典型應用，滿足后進先出的規則（后入堆疊的前括號將優先與先出現的后括號相匹配），
?遍歷字串，遇到前括號直接入堆疊，遇到后括號，判斷該后括號與堆疊頂的前括號是否匹配（若此時堆疊為空，則字串無效），若不匹配則字串無效；若匹配則洗掉堆疊頂元素，繼續遍歷字串，直到字串遍歷完畢，當字串遍歷完后，檢測堆疊是否為空，若為空，則字串有效，若不為空，說明有前括號未匹配，字串無效，

代碼：

typedef char STDataType;//堆疊中存盤的元素型別

typedef struct Stack
{
	STDataType* a;//堆疊
	int top;//堆疊頂
	int capacity;//容量，方便增容
}Stack;

//初始化堆疊
void StackInit(Stack* pst)
{
	assert(pst);

	pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);//初始化堆疊可存盤4個元素
	pst->top = 0;//初始時堆疊中無元素，堆疊頂為0
	pst->capacity = 4;//容量為4
}

//銷毀堆疊
void StackDestroy(Stack* pst)
{
	assert(pst);

	free(pst->a);//釋放堆疊
	pst->a = NULL;//及時置空
	pst->top = 0;//堆疊頂置0
	pst->capacity = 0;//容量置0
}

//入堆疊
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);

	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);
		}
		pst->a = tmp;
		pst->capacity *= 2;//堆疊容量擴大為原來的兩倍
	}
	pst->a[pst->top] = x;//堆疊頂位置存放元素x
	pst->top++;//堆疊頂上移
}

//檢測堆疊是否為空
bool StackEmpty(Stack* pst)
{
	assert(pst);

	return pst->top == 0;
}

//出堆疊
void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));//檢測堆疊是否為空

	pst->top--;//堆疊頂下移
}

//獲取堆疊頂元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));//檢測堆疊是否為空

	return pst->a[pst->top - 1];//回傳堆疊頂元素
}

//獲取堆疊中有效元素個數
int StackSize(Stack* pst)
{
	assert(pst);

	return pst->top;//top的值便是堆疊中有效元素的個數
}
/*---以上代碼是堆疊的基本功能實作，以下代碼是題解主體部分---*/
bool isValid(char * s){
    Stack st;//創建一個堆疊
    StackInit(&st);//初始化堆疊
    char* cur = s;//cur用于遍歷字串
    while(*cur)
    {
        if(*cur == '('||*cur == '{'||*cur == '[')//前括號統一入堆疊
        {
            StackPush(&st, *cur);
            cur++;
        }
        else
        {
            if(StackEmpty(&st))//若遇到后括號，且堆疊為空，則字串無效
            {
                StackDestroy(&st);
                return false;
            }
            char top = StackTop(&st);//獲取堆疊頂元素
            if((top == '('&&*cur != ')')
            ||(top == '{'&&*cur != '}')
            ||(top == '['&&*cur != ']'))//后括號與堆疊頂的前括號不匹配
            {
                StackDestroy(&st);
                return false;
            }
            else//匹配
            {
                StackPop(&st);
                cur++;
            }
        }
    }
    bool ret = StackEmpty(&st);//檢測堆疊是否為空
    StackDestroy(&st);
    return ret;//堆疊為慷訓傳true，堆疊不為慷訓傳false
}

題目二：用佇列實作堆疊

?請你僅使用兩個佇列實作一個后入先出（LIFO）的堆疊，并支持普通佇列的全部四種操作（push、top、pop 和 empty），

實作 MyStack 類：
?void push(int x) 將元素 x 壓入堆疊頂，
?int pop() 移除并回傳堆疊頂元素，
?int top() 回傳堆疊頂元素，
?boolean empty() 如果堆疊是空的，回傳 true ；否則，回傳 false ，

思路：
?佇列的機制是先入先出，而堆疊的機制是先入后出，我們僅用一個佇列是不可能實作堆疊的，
?使用兩個佇列，始終保持一個佇列為空，當我們需要進行壓堆疊操作時，將資料壓入不為空的佇列中（若兩個都為空，則隨便壓入一個佇列），當需要進行出堆疊操作時，將不為空的佇列中的資料匯入空佇列，僅留下一個資料，這時將這個資料回傳并且洗掉即可，判斷堆疊是否為空，即判斷兩個佇列是否同時為空，
在這里插入圖片描述
代碼：

typedef int QDataType;//佇列中存盤的元素型別

typedef struct QListNode
{
	struct QListNode* next;//指標域
	QDataType data;//資料域
}QListNode;

typedef struct Queue
{
	QListNode* head;//隊頭
	QListNode* tail;//隊尾
}Queue;
//初始化佇列
void QueueInit(Queue* pq)
{
	assert(pq);
	//起始時佇列為空
	pq->head = NULL;
	pq->tail = NULL;
}

//銷毀佇列
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QListNode* cur = pq->head;//接收隊頭
	//遍歷鏈表，逐個釋放結點
	while (cur)
	{
		QListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;//隊頭置空
	pq->tail = NULL;//隊尾置空
}

//隊尾入佇列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));//申請新結點
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;//新結點賦值
	newnode->next = NULL;//新結點指標域置空
	if (pq->head == NULL)//佇列中原本無結點
	{
		pq->head = pq->tail = newnode;//隊頭、隊尾直接指向新結點
	}
	else//佇列中原本有結點
	{
		pq->tail->next = newnode;//最后一個結點指向新結點
		pq->tail = newnode;//改變隊尾指標指向
	}
}

//檢測佇列是否為空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

//隊頭出佇列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//檢測佇列是否為空

	if (pq->head->next == NULL)//佇列中只有一個結點
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;
	}
	else//佇列中有多個結點
	{
		QListNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;//改變隊頭指標指向
	}
}

//獲取佇列頭部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//檢測佇列是否為空

	return pq->head->data;//回傳隊頭指標指向的資料
}

//獲取佇列尾部元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//檢測佇列是否為空

	return pq->tail->data;//回傳隊尾指標指向的資料
}

//獲取佇列中有效元素個數
int QueueSize(Queue* pq)
{
	assert(pq);

	QListNode* cur = pq->head;//接收隊頭
	int count = 0;//記錄結點個數
	while (cur)//遍歷佇列
	{
		count++;
		cur = cur->next;
	}
	return count;//回傳佇列中的結點數
}
/*---以上代碼是佇列的基本功能實作，以下代碼是題解主體部分---*/
typedef struct {
	Queue q1;//第一個佇列
	Queue q2;//第二個佇列
} MyStack;

/** Initialize your data structure here. */
MyStack* myStackCreate() {
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));//申請一個MyStack型別的堆疊
	QueueInit(&pst->q1);//初始化第一個佇列
	QueueInit(&pst->q2);//初始化第二個佇列

	return pst;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
	//資料壓入非空的那個佇列
	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
	Queue* pEmpty = &obj->q1;//記錄空佇列
	Queue* pNoEmpty = &obj->q2;//記錄非空佇列
	if (!QueueEmpty(&obj->q1))
	{
		pEmpty = &obj->q2;
		pNoEmpty = &obj->q1;
	}
	while (QueueSize(pNoEmpty) > 1)
	{
		QueuePush(pEmpty, QueueFront(pNoEmpty));
		QueuePop(pNoEmpty);
	}//將非空佇列中的資料放入空佇列中，只留下一個資料
	int front = QueueFront(pNoEmpty);//獲取目標資料
	QueuePop(pNoEmpty);//洗掉目標資料
	return front;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
	//獲取非空佇列的隊尾資料
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
	//兩個佇列均為空，則MyStack為空
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
	QueueDestroy(&obj->q1);//釋放第一個佇列
	QueueDestroy(&obj->q2);//釋放第二個佇列
	free(obj);//釋放MyStack
}

題目三：用堆疊實作佇列

?請你僅使用兩個堆疊實作先入先出佇列，佇列應當支持一般佇列支持的所有操作（push、pop、peek、empty），

實作 MyQueue 類：
?void push(int x) 將元素 x 推到佇列的末尾，
?int pop() 從佇列的開頭移除并回傳元素，
?int peek() 回傳佇列開頭的元素，
?boolean empty() 如果佇列為空，回傳 true ；否則，回傳 false，

思路：
?使用兩個堆疊，第一個堆疊只用于資料的輸入，第二個堆疊只用于資料的輸出，當需要輸出資料，但第二個堆疊為空時，先將第一個堆疊中的資料一個一個匯入到第二個堆疊，然后第二個堆疊再輸出資料即可，
在這里插入圖片描述
這樣就能夠模擬實作一個佇列了，即先輸入的資料先輸出，

代碼：

typedef int STDataType;//堆疊中存盤的元素型別

typedef struct Stack
{
	STDataType* a;//堆疊
	int top;//堆疊頂
	int capacity;//容量，方便增容
}Stack;

//初始化堆疊
void StackInit(Stack* pst)
{
	assert(pst);

	pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);//初始化堆疊可存盤4個元素
	pst->top = 0;//初始時堆疊中無元素，堆疊頂為0
	pst->capacity = 4;//容量為4
}

//銷毀堆疊
void StackDestroy(Stack* pst)
{
	assert(pst);

	free(pst->a);//釋放堆疊
	pst->a = NULL;//及時置空
	pst->top = 0;//堆疊頂置0
	pst->capacity = 0;//容量置0
}

//入堆疊
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);

	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);
		}
		pst->a = tmp;
		pst->capacity *= 2;//堆疊容量擴大為原來的兩倍
	}
	pst->a[pst->top] = x;//堆疊頂位置存放元素x
	pst->top++;//堆疊頂上移
}

//檢測堆疊是否為空
bool StackEmpty(Stack* pst)
{
	assert(pst);

	return pst->top == 0;
}

//出堆疊
void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));//檢測堆疊是否為空

	pst->top--;//堆疊頂下移
}

//獲取堆疊頂元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));//檢測堆疊是否為空

	return pst->a[pst->top - 1];//回傳堆疊頂元素
}

//獲取堆疊中有效元素個數
int StackSize(Stack* pst)
{
	assert(pst);

	return pst->top;//top的值便是堆疊中有效元素的個數
}
/*---以上代碼是堆疊的基本功能實作，以下代碼是題解主體部分---*/
typedef struct {
    Stack pushST;//插入資料時用的堆疊
    Stack popST;//洗掉資料時用的堆疊
} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));//申請一個佇列型別
    StackInit(&obj->pushST);//初始化pushST
    StackInit(&obj->popST);//初始化popST

    return obj;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST, x);//插入資料，向pushST插入
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popST))//popST為空時，需先將pushST中資料匯入popST
    {
        while(!StackEmpty(&obj->pushST))//將pushST資料全部匯入popST
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);//回傳popST堆疊頂的元素
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    int top = myQueuePeek(obj);
    StackPop(&obj->popST);//洗掉資料，洗掉popST中堆疊頂的元素
    return top;
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);//兩個堆疊均為空，則“佇列”為空
}

void myQueueFree(MyQueue* obj) {
    //先釋放兩個堆疊，再釋放佇列的結構體型別
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}

題目四：設計回圈佇列

?設計你的回圈佇列實作，回圈佇列是一種線性資料結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個回圈，它也被稱為“環形緩沖器”，
?回圈佇列的一個好處是我們可以利用這個佇列之前用過的空間，在一個普通佇列里，一旦一個佇列滿了，我們就不能插入下一個元素，即使在佇列前面仍有空間，但是使用回圈佇列，我們能使用這些空間去存盤新的值，

實作 MyCircularQueue 類：
?MyCircularQueue(k): 構造器，設定佇列長度為 k ，
?Front: 從隊首獲取元素，如果佇列為空，回傳 -1 ，
?Rear: 獲取隊尾元素，如果佇列為空，回傳 -1 ，
?enQueue(value): 向回圈佇列插入一個元素，如果成功插入則回傳真，
?deQueue(): 從回圈佇列中洗掉一個元素，如果成功洗掉則回傳真，
?isEmpty(): 檢查回圈佇列是否為空，
?isFull(): 檢查回圈佇列是否已滿，

思路：
?在環形佇列中，佇列為空時，隊頭隊尾指向同一個位置，當佇列不為空時，隊頭指向插入的第一個資料，隊尾指向最后一個資料的下一個位置，當tail+1等于front時，說明環形佇列已滿，
?注意：環形佇列的隊尾不能像常規佇列中隊尾一樣指向最后一個資料，如果這樣的話，我們將不能區別環形佇列的狀態是慷訓是滿，因為此時隊頭和隊尾都指向同一個位置，這就意味著，我們必須留出一個空間，這個空間不能存放資料，這樣我們才能很好的區別環形佇列的狀態是慷訓是滿，
在這里插入圖片描述
?我們如果用一個陣列來實作這個環形佇列的話，上面這三種狀態就對應于以下三種狀態：

?可以看出，此時這個陣列和環形完全扯不上關系，這其實很簡單，我們只需注意判斷兩個地方：
?1.當指標指向整個陣列的后方的時候，讓該指標重新指向陣列的第一個元素，
?2.當指標指向整個陣列的前方的時候，讓該指標直接指向陣列最后一個有效元素的后面，

這樣就使得該陣列在邏輯上是“環形”的了，
在這里插入圖片描述
代碼：

typedef struct {
    int* a;//陣列模擬環形佇列
    int k;//佇列可存盤的有效資料總數
    int front;//隊頭
    int tail;//隊尾的后一個位置
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申請一個環形佇列
    obj->a = (int*)malloc(sizeof(int)*(k+1));//開辟佇列空間
    //初始時，隊頭和隊尾均為0
    obj->front = 0;
    obj->tail = 0;
    obj->k = k;//設定佇列可存盤的有效資料個數
    
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->tail;//當front和tail指向同一位置時，佇列為空
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int tailNext = obj->tail+1;
    if(tailNext == obj->k+1)//當指標指到佇列末尾時，指標回傳佇列開頭，使佇列回圈
    {
        tailNext = 0;
    }
    return tailNext == obj->front;//當tail+1指向的位置與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;

        return true;
    }
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))//當佇列為空時，無法再洗掉資料
    {
        return false;
    }
    else//洗掉資料
    {
        obj->front++;

        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-1指向位置的資料
    {
        int tailPrev = obj->tail-1;

        if(tailPrev == -1)//使佇列回圈
            tailPrev = obj->k;
        
        return obj->a[tailPrev];
    }
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);//先釋放動態開辟的陣列
    free(obj);//再釋放動態開辟的結構體
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/279295.html

標籤：其他

上一篇：Hadoop Rpc簡單實作

下一篇：安全開發Java：日志注入，并沒那么簡單

堆疊和佇列高頻面試題

題目一：括號匹配問題

題目二：用佇列實作堆疊

題目三：用堆疊實作佇列

題目四：設計回圈佇列