棧和隊列的應用-創(chuàng)新互聯(lián)

目錄

• 1.括號匹配問題
• • 1.1流程圖
  • 1.2代碼
  • 1.3復雜度
• 2.用隊列實現(xiàn)棧
• • 2.1思路
  • 2.2畫圖
  • 2.3代碼
• 3.用棧實現(xiàn)隊列
• • 3.1思想
  • 3.2畫圖
  • 3.3代碼
• 4.循環(huán)隊列
• • 4.1思想
  • 4.2畫圖
  • 4.3代碼

成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設,朝陽企業(yè)網(wǎng)站建設,朝陽品牌網(wǎng)站建設,網(wǎng)站定制,朝陽網(wǎng)站建設報價,網(wǎng)絡營銷,網(wǎng)絡優(yōu)化,朝陽網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。1.括號匹配問題

??給定一個只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：(1)左括號必須用相同類型的右括號閉合。(2)左括號必須以正確的順序閉合。(3)每個右括號都有一個對應的相同類型的左括號。
來源:力扣(LeetCode)
鏈接:https://leetcode.cn/problems/valid-parentheses/

1.1流程圖

1.2代碼

//使用動態(tài)數(shù)組實現(xiàn)棧
typedef struct SeqStack
{char* arr;
    int top;
    int capacity;
}SeqStack;

//判空
bool IsEmpty(SeqStack* ps)
{if(ps->top == -1)
        return true;

    return false;
}

//初始化
void InitStack(SeqStack* ps)
{ps->arr = (char*)malloc(4*sizeof(char));
    if(ps->arr == NULL)
        return;
    ps->top = -1;
    ps->capacity = 4;
}

//進棧
void Push(SeqStack* ps,char ch)
{if(ps->top + 1 == ps->capacity)
    {char* tmp = (char*)realloc(ps->arr,ps->capacity*2*sizeof(char));
        if(tmp == NULL)
            return;

        ps->arr = tmp;
        ps->capacity *= 2;
    }
    ps->arr[++ps->top] = ch;
}

//出棧
void Pop(SeqStack* ps)
{if(ps->top == -1)
        return;

    ps->top--;
}

//取棧頂元素
char GetTopElement(SeqStack* ps)
{char ch = ps->arr[ps->top];
    return ch;
}

//棧的括號匹配
bool isValid(char * s){int len = strlen(s);

    SeqStack stack;
    InitStack(&stack);
	
	//遍歷原數(shù)組
    for(int i = 0;i< len;i++)
    {//左括號進棧
        if(s[i] == '(' || s[i] == '[' || s[i] == '{')
        {Push(&stack,s[i]);
        }
        //右括號與棧頂元素比較
        else
        {	//右括號單身
            if(IsEmpty(&stack))
                return false;
			
			//取棧頂元素
            char ret = GetTopElement(&stack);
            //三種情況左右括號不匹配
            if(s[i] == ')' && ret != '(')
                return false;
            else if(s[i] == ']' && ret != '[')
                return false;
            else if(s[i] == '}' && ret != '{')
                return false;
            Pop(&stack);
        }
    }
	
	//左括號不單身
    if(IsEmpty(&stack))
        return true;
    //左括號單身
    else
        return false;
}

1.3復雜度

時間復雜度:O(n)
空間復雜度:O(1)

2.用隊列實現(xiàn)棧

??請你僅使用兩個隊列實現(xiàn)一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。
來源:力扣(LeetCode)
鏈接:https://leetcode.cn/problems/implement-stack-using-queues/

2.1思路

1.用兩個隊列實現(xiàn)棧的各個功能
2.創(chuàng)建棧
先創(chuàng)建棧malloc 再初始化兩個隊列
3.插入(push)
將數(shù)據(jù)插入到非空隊列
4.刪除(pop)
將非空隊列(元素個數(shù)>1)倒到另外一個空隊列當中，然后非空隊列只剩一個元素，此時彈出該元素，就實現(xiàn)棧的刪除
5.取棧頂元素
取非空隊列的隊尾元素
6.判空
當兩個隊列全為空時，棧為空
7.銷毀棧(destroy)
先銷毀兩個隊列，再釋放棧

2.2畫圖

2.3代碼

//方便修改數(shù)據(jù)類型
typedef int ElemType;

//定義隊列結點
typedef struct QueueNode
{ElemType data;//數(shù)據(jù)域
	struct QueueNode* next;//指針域
}QueueNode;

//封裝隊頭指針和隊尾指針
typedef struct Queue
{QueueNode* head;
	QueueNode* tail;
	int size;
}Queue;

//初始化
void InitQueue(Queue* q)
{assert(q);

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

//判空
bool IsEmpty(Queue* q)
{assert(q);

	if (q->size == 0)
		return true;

	return false;
}

//入隊
void Push(Queue* q,ElemType x)
{assert(q);

	if (q->size == 0)
	{QueueNode* tmp = (QueueNode*)malloc(sizeof(QueueNode));
		if (tmp == NULL)
			return;

		q->head = q->tail = tmp;
		tmp->data = x;
		tmp->next = NULL;
		q->size++;
	}
	else
	{QueueNode* tmp = (QueueNode*)malloc(sizeof(QueueNode));
		if (tmp == NULL)
			return;

		tmp->data = x;
		tmp->next = NULL;
		q->tail->next = tmp;
		q->tail = q->tail->next;
		q->size++;
	}
}

//出隊
void Pop(Queue* q)
{assert(q && q->head);

	if (q->size == 0)
		return;

	if (q->head == q->tail)
	{free(q->head);
		q->head = q->tail = NULL;
		q->size--;
	}
	else
	{QueueNode* del = q->head;
		q->head = del->next;
		q->size--;
		free(del);
	}
}

//取隊首元素
ElemType GetHeadElement(Queue* q)
{assert(q);
    assert(!IsEmpty(q));

	return q->head->data;
}

//取隊尾元素
ElemType GetTailElement(Queue* q)
{assert(q && q->head);

	return q->tail->data;
}

//求隊長
int QueueSize(Queue* q)
{assert(q);

	return q->size;
}

//銷毀隊列
void DestroyQueue(Queue* q)
{assert(q);
    

	QueueNode* cur = q->head;
	while (cur)
	{QueueNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	q->head = q->tail = NULL;
	q->size = 0;
}

//封裝兩個隊列定義棧結構
typedef struct {Queue q1;
    Queue q2;
} MyStack;

//先malloc在初始化兩個隊列
MyStack* myStackCreate() {//定義棧
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    
    //初始化隊列q1和隊列q2
    InitQueue(&obj->q1);
    InitQueue(&obj->q2);
	
	//返回棧
    return obj;
}

//進棧
void myStackPush(MyStack* obj, int x) {//在非空隊列中插入數(shù)據(jù)
    if(!IsEmpty(&obj->q1))
        Push(&obj->q1,x);
    else
        Push(&obj->q2,x);
}

//出棧
int myStackPop(MyStack* obj) {//假設法找空隊列
    Queue* empty = &obj->q1;
    Queue* nonempty = &obj->q2;
    if(!IsEmpty(&obj->q1))
    {empty = &obj->q2;
        nonempty = &obj->q1;
    }

	//當非空隊列的元素個數(shù)>1,將其前面的元素插入到空隊列當中實現(xiàn)倒數(shù)據(jù)
    while(QueueSize(nonempty) >1)
    {//往空隊列中倒入一個元素,非空隊列就刪除該元素
        Push(empty,GetHeadElement(nonempty));
        Pop(nonempty);
    }
	
	//將非空隊列的最后一個元素保存下來
    int top = GetHeadElement(nonempty);
    //刪除非空隊列的最后一個元素
    Pop(nonempty);
	
	//返回棧頂元素(非空隊列的最后一個元素)
    return top;
}

//取棧頂元素
int myStackTop(MyStack* obj) {//將非空隊列的隊尾元素返回
    if(!IsEmpty(&obj->q1))
        return GetTailElement(&obj->q1);
    else
        return GetTailElement(&obj->q2);
}

//判空
bool myStackEmpty(MyStack* obj) {//當兩個隊列同時為空,棧就為空
    return IsEmpty(&obj->q1) && IsEmpty(&obj->q2);
}

//銷毀棧
void myStackFree(MyStack* obj) {//銷毀隊列q1和隊列q2
    DestroyQueue(&obj->q1);
    DestroyQueue(&obj->q2);

	//釋放棧
    free(obj);
}

3.用棧實現(xiàn)隊列

??請你僅使用兩個棧實現(xiàn)先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）
來源:力扣(LeetCode)
鏈接:https://leetcode.cn/problems/implement-queue-using-stacks/

3.1思想

1.用兩個棧實現(xiàn)隊列的各個功能
一個棧(pushStack)專門用來存數(shù)據(jù)，另外一個棧(popStack)用來刪數(shù)據(jù)
2.創(chuàng)建隊列
先創(chuàng)建隊列malloc 再初始化兩個棧
3.插入(push)
直接將元素插入到pushStack，也就是代碼里的q1
4.取隊首元素
將pushStack里的元素倒入到popStack中，然后再返回popStack的棧頂元素，并彈出該元素
5.刪除(pop)
彈出popStack的棧頂元素
6.判空
當兩個棧全為空，隊列為空
7.銷毀隊列(destroy)
先銷毀兩個棧，再釋放隊列

3.2畫圖

3.3代碼

//方便修改數(shù)據(jù)類型
typedef int ElemType;

//定義棧結構
typedef struct SeqStack
{ElemType* a;
	int top;//棧頂指針
	int capacity;//棧容量
}SeqStack;

//判空
bool IsEmpty(SeqStack* ps)
{//為什么assert,非常規(guī)思維
	assert(ps);

	if (ps->top == -1)
		return true;

	return false;
}

//初始化
void InitStack(SeqStack* ps)
{assert(ps);

	ps->a = (ElemType*)malloc(4 * sizeof(ElemType));
	if (ps->a == NULL)
	{		return;
	}
	ps->top = -1;
	ps->capacity = 4;
}

//取棧頂元素
ElemType GetTopElement(SeqStack* ps)
{assert(ps);

	ElemType x = ps->a[ps->top];

	return x;
}

//求棧長
int StackLength(SeqStack* ps)
{assert(ps);

	return ps->top + 1;
}

//進棧
void StackPush(SeqStack* ps, ElemType x)
{assert(ps);

	if (StackLength(ps) == ps->capacity)
	{ElemType* tmp = (ElemType*)realloc(ps->a, ps->capacity * 2 * sizeof(ElemType));
		if (tmp == NULL)
		{	return;
		}

		ps->a = tmp;
		ps->capacity *= 2;
	}

	ps->a[++ps->top] = x;
}

//出棧
void StackPop(SeqStack* ps)
{assert(ps);

	if (IsEmpty(ps))
		return;

	ps->top--;
}

//銷毀棧
void DestroyStack(SeqStack* ps)
{assert(ps);

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

//定義兩個棧創(chuàng)建隊列
typedef struct {SeqStack q1;
    SeqStack q2;
} MyQueue;

//創(chuàng)建隊列再初始化兩個棧
MyQueue* myQueueCreate() {//創(chuàng)建隊列
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));

	//初始化兩個棧
    InitStack(&obj->q1);
    InitStack(&obj->q2);

	//返回隊列
    return obj;
}

//入隊
void myQueuePush(MyQueue* obj, int x) {assert(obj);

    StackPush(&obj->q1,x);
}

//出隊
int myQueuePop(MyQueue* obj) {assert(obj);
    
    int peek = myQueuePeek(obj);
    StackPop(&obj->q2);

    return peek;
}

//取隊首元素
int myQueuePeek(MyQueue* obj) {assert(obj);
    
    //如果popStack為空且pushStack不為空
    //就將pushStack的元素倒入到popStack當中
    if(IsEmpty(&obj->q2))
    {while(!IsEmpty(&obj->q1))
        {	//將pushStack當中的元素倒入到popStack當中
            StackPush(&obj->q2,GetTopElement(&obj->q1));
            //彈出pushStack的棧頂元素
            StackPop(&obj->q1);
        }
    }
	
	//返回隊首元素(也就是popStack當中的棧頂元素)
    return GetTopElement(&obj->q2);
}

//判空
bool myQueueEmpty(MyQueue* obj) {assert(obj);
	
	//當兩個棧同時為空時,隊列為空
    return IsEmpty(&obj->q1) && IsEmpty(&obj->q2);
}

//銷毀隊列
void myQueueFree(MyQueue* obj) {assert(obj);

	//先銷毀兩個棧
    DestroyStack(&obj->q1);
    DestroyStack(&obj->q2);

	//釋放隊列
    free(obj);
}

4.循環(huán)隊列

??設計你的循環(huán)隊列實現(xiàn)。 循環(huán)隊列是一種線性數(shù)據(jù)結構，其操作表現(xiàn)基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環(huán)。它也被稱為“環(huán)形緩沖器”。
循環(huán)隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環(huán)隊列，我們能使用這些空間去存儲新的值。
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/design-circular-queue

4.1思想

??使用鏈表或者數(shù)組實現(xiàn)循環(huán)隊列，因為前者不能隨機訪問，所以我們選擇用數(shù)組實現(xiàn)循環(huán)隊列。循環(huán)隊列頭尾相連，大小固定。
兩大問題:
1.如何判空判滿
(1)增加加一個計數(shù)變量(size)
(2)創(chuàng)建一個空結點
2.如何用數(shù)組實現(xiàn)循環(huán)
(1)特殊處理
if(rear == Maxsize) rear = 0;
(2)循環(huán)取模
(rear + 1) % Maxsize

4.2畫圖

4.3代碼

//定義循環(huán)隊列結構
typedef struct {int* arr;//數(shù)組
    int front;//隊頭指針
    int rear;//隊尾指針
    int k;//循環(huán)隊列有效元素個數(shù)
} MyCircularQueue;

//創(chuàng)建循環(huán)隊列(隊列總大小為k+1)
MyCircularQueue* myCircularQueueCreate(int k) {//創(chuàng)建循環(huán)隊列
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

	//開辟k+1個數(shù)組元素
    obj->arr = (int*)malloc((k+1)*sizeof(int));
    //置空
    obj->front = obj->rear = 0;
    //循環(huán)隊列有效元素個數(shù)
    obj->k = k;

	//返回循環(huán)隊列
    return obj;
}

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);

    if(obj->front == obj->rear)
        return true;
    
    return false;
}

//判滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);

    if((obj->rear + 1)%(obj->k + 1) == obj->front)
        return true;
    
    return false;
}

//入隊
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);
	//判滿
    if(myCircularQueueIsFull(obj))
        return false;
	//存值
    obj->arr[obj->rear] = value;
    //循環(huán)
    obj->rear = (obj->rear + 1) % (obj->k + 1);

    return true;
}

//出隊
bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);
	//判空
    if(myCircularQueueIsEmpty(obj))
        return false;
	//循環(huán)
    obj->front = (obj->front + 1) % (obj->k + 1);

    return true;
}

//取隊首元素
int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);
	//判空
    if(myCircularQueueIsEmpty(obj))
        return -1;
	//取值
    return obj->arr[obj->front];
}

//取隊尾元素
int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);

	//判空
    if(myCircularQueueIsEmpty(obj))
        return -1;
	//找到rear的前一個結點
    int rear = (obj->rear + obj->k) % (obj->k + 1);
    return obj->arr[rear];
}

//銷毀循環(huán)隊列
void myCircularQueueFree(MyCircularQueue* obj) {assert(obj);
	//先釋放開辟的k+1個數(shù)組大小的空間
    free(obj->arr);
	//再釋放開辟的結構體變量
    free(obj);
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站標題：棧和隊列的應用-創(chuàng)新互聯(lián)
轉載注明：http://muchs.cn/article4/dcpsie.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站內鏈、建站公司、Google、定制開發(fā)、App開發(fā)、虛擬主機

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)