在這里插入圖片描述

堆疊的概念
堆疊的實作
- 堆疊的宣告
- 堆疊的實作
- 壓堆疊
- 出堆疊
佇列
- 佇列宣告
- 佇列實作
- 銷毀
- 隊尾入隊
- 隊頭出隊
- 判空
- 獲取隊頭資料
- 獲取隊尾資料
- 求元素個數
力扣題
- 20. 有效的括號
- 225. 用佇列實作堆疊
- 232. 用堆疊實作佇列
- 設計回圈佇列

堆疊的概念

1.堆疊
1.1堆疊的概念及結構
堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端
稱為堆疊頂，另一端稱為堆疊底，堆疊中的資料元素遵守后進先出LIFO（Last In First Out）的原則，

壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂，
出堆疊：堆疊的洗掉操作叫做出堆疊，出資料也在堆疊頂

在這里插入圖片描述

堆疊的實作

堆疊的宣告

typedef int STData;
typedef struct Stack 
{
	STData *a;
	int capacity;
	int top;
}Stack;

//初始化
void StackInit(Stack *ST);
//堆疊銷毀
void StackDestroy(Stack *ST);
//入堆疊
void StackPush(Stack *ST, int x);
//彈堆疊
void StackPop(Stack *ST);
//獲取堆疊頂元素
int StackTop(Stack *ST);
//判斷堆疊是否空
bool StackEmpty(Stack *ST);
//獲取堆疊頂元素個數
int StackSize(Stack *ST);

堆疊的實作

#include"Stack.h"
//初始化
void StackInit(Stack *ST) 
{
	assert(ST);
	ST->a = (STData *)malloc(sizeof(int) * 4);
	ST->capacity = 4;
	ST->top = 0;
}

//堆疊銷毀
void StackDestroy(Stack *ST)
{
	assert(ST);
	free(ST->a);
	ST->a = NULL;
	ST->capacity = ST->top = 0;
}
//入堆疊
void StackPush(Stack *ST, int x) 
{
	assert(ST);
	if (ST->capacity == ST->top) 
	{
		STData *tmp = realloc(ST->a,sizeof(STData) * ST->capacity * 2);
		if (tmp == NULL) 
		{
			perror("relloc:");
			exit(-1);
		}
		ST->a = tmp;
		ST->capacity = ST->capacity * 2;
	}
	ST->a[ST->top++] = x;
}
//彈堆疊
void StackPop(Stack *ST) 
{
	assert(ST);
	if(!StackEmpty(ST))
	ST->top--;
}
//獲取堆疊頂元素
int StackTop(Stack *ST) 
{
	assert(ST);
	return ST->a[ST->top - 1];
}
//判斷堆疊是否空
bool StackEmpty(Stack *ST) 
{
	assert(ST);
	return ST->top == 0 ? true : false;
}
//獲取堆疊頂元素個數
int StackSize(Stack *ST) 
{
	assert(ST);
	return ST->top;
}

壓堆疊

在這里插入圖片描述

//入堆疊
void StackPush(Stack *ST, int x) 
{
	assert(ST);
	if (ST->capacity == ST->top) 
	{
		STData *tmp = realloc(ST->a,sizeof(STData) * ST->capacity * 2);
		if (tmp == NULL) 
		{
			perror("relloc:");
			exit(-1);
		}
		ST->a = tmp;
		ST->capacity = ST->capacity * 2;
	}
	ST->a[ST->top++] = x;
}

出堆疊

在這里插入圖片描述

//彈堆疊
void StackPop(Stack *ST) 
{
	assert(ST);
	if(!StackEmpty(ST))
	ST->top--;
}

佇列

佇列宣告


typedef int QueDataTypef;

typedef struct QueueNode
{
	struct Queue *next;
	QueDataTypef data;
}QueueNode;

typedef struct Queue 
{
	QueueNode *head;
	QueueNode *tail;
}Queue;


//初始化
void QueueInit(Queue *q);
//銷毀
void QueueDestroy(Queue *q);
//隊尾入隊
void QueuePush(Queue *q, int x);
//隊頭出隊
void QueuePop(Queue *q);
//判斷空
bool QueueEmpty(Queue *q);
//獲取隊頭資料
QueDataTypef QueueFront(Queue *q);
//獲取隊尾資料
QueDataTypef QueueBack(Queue *q);
//求佇列的元素個數
int QueueSize(Queue *q);

佇列實作

#include"Queue.h"

//初始化
void QueueInit(Queue *q) 
{
	assert(q);
	q->head = q->tail = NULL;
}
//銷毀
void QueueDestroy(Queue *q) 
{
	QueueNode* cur = q->head;
	
	while (cur) 
	{
		QueueNode *next = (QueueNode *)cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}

//隊尾入隊
void QueuePush(Queue *q, int x) 
{
	assert(q);
	QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		exit(-1);
		perror("QueuePush::malloc");
	}
	newNode->data = x;
	newNode->next = NULL;
	
	if (q->tail == NULL) 
	{
		q->head = q->tail = newNode;
	}
	else 
	{
		q->tail->next = (Queue *)newNode;
		q->tail = newNode;
	}
}
//隊頭出隊
void QueuePop(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head->next == NULL) 
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else 
	{
		QueueNode *next = (QueueNode *)q->head->next;
		free(q->head);
		q->head = next;
	}
}

//判斷空
bool QueueEmpty(Queue *q) 
{
	assert(q);
	return q->head ==  NULL ? true : false;
}
//獲取隊頭資料
QueDataTypef QueueFront(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}
//獲取隊尾資料
QueDataTypef QueueBack(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

//求佇列的元素個數
int QueueSize(Queue *q) 
{
	assert(q);
	int size = 0;
	QueueNode *cur = q->head;
	while (cur) 
	{
		cur = (QueueNode *)cur->next;
		size++;
	}
	return size;
}

銷毀

佇列在銷毀時，除了釋放結點的記憶體，還要將頭結點和尾結點置空

//銷毀
void QueueDestroy(Queue *q) 
{
	QueueNode* cur = q->head;
	
	while (cur) 
	{
		QueueNode *next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}

隊尾入隊

在這里插入圖片描述

如果隊頭和隊尾都是NULL的話，將新結點取下來做隊頭和隊尾，如果隊頭不是空，就將新的結點尾插到tail的后面，讓新結點做新的尾

//隊尾入隊
void QueuePush(Queue *q, int x) 
{
	assert(q);
	QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		exit(-1);
		perror("QueuePush::malloc");
	}
	newNode->data = x;
	newNode->next = NULL;
	//隊頭隊尾都是NULL
	if (q->tail == NULL) 
	{
		q->head = q->tail = newNode;
	}
	//取結點尾插入隊，新結點成為新的尾
	else 
	{
		q->tail->next = newNode;
		q->tail = newNode;
	}
}

隊頭出隊

在這里插入圖片描述

出隊的時候考慮一種情況如果當只剩下一個結點了，不單獨處理的話會讓q->tail成為野指標

//隊頭出資料
void QueuePop(Queue *q) 
{
	//出隊只剩一個結點時，防止tail成為野指標
	if (q->head->next == NULL) 
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else 
	{
		QueueNode *next = q->head->next;
		free(q->head);
		q->head = next;
	}
}

判空

//判斷空
bool QueueEmpty(Queue *q) 
{
	assert(q);
	return q->head ==  NULL ? true : false;
}

獲取隊頭資料

//獲取隊頭資料
QueDataTypef QueueFront(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}

獲取隊尾資料

//獲取隊尾資料
QueDataTypef QueueBack(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

求元素個數

//求佇列的元素個數
int QueueSize(Queue *q) 
{
	assert(q);
	int size = 0;
	QueueNode *cur = q->head;
	while (cur) 
	{
		cur = (QueueNode *)cur->next;
		size++;
	}
	return size;
}

力扣題

20. 有效的括號

鏈接: link.

原題描述：
給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字串 s ，判斷字串是否有效，

有效字串需滿足：

左括號必須用相同型別的右括號閉合，
左括號必須以正確的順序閉合，

解題思路：
遍歷字串遇到左括號就入堆疊，遇到右括號就取出堆疊中的元素來匹配，如果匹配不上，就回傳false，如果匹配上了，就將堆疊頂元素彈出，直到字串遍歷完了，最后判斷堆疊是否為空

typedef char STData;
typedef struct Stack 
{
	STData *a;
	int capacity;
	int top;
}Stack;
//堆疊銷毀
void StackDestroy(Stack *ST)
{
	assert(ST);
	free(ST->a);
	ST->a = NULL;
	ST->capacity = ST->top = 0;
}
//判斷堆疊是否空
bool StackEmpty(Stack *ST) 
{
	assert(ST);
	return ST->top == 0 ? true : false;
}
//初始化
void StackInit(Stack *ST) 
{
	assert(ST);
	ST->a = (STData *)malloc(sizeof(int) * 4);
	ST->capacity = 4;
	ST->top = 0;
    return;
}
//入堆疊
void StackPush(Stack *ST, int x) 
{
	assert(ST);
	if (ST->capacity == ST->top) 
	{
		STData *tmp = realloc(ST->a,sizeof(STData) * ST->capacity * 2);
		if (tmp == NULL) 
		{
			perror("relloc:");
			exit(-1);
		}
		ST->a = tmp;
		ST->capacity = ST->capacity * 2;
	}
	ST->a[ST->top++] = x;
}
//彈堆疊
void StackPop(Stack *ST) 
{
	assert(ST);
	if(!StackEmpty(ST))
	ST->top--;
}
//獲取堆疊頂元素
int StackTop(Stack *ST) 
{
	assert(ST);
	return ST->a[ST->top - 1];
}
bool isValid(char * s){
    if(s == NULL)
    return false;
    Stack ST;
    StackInit(&ST);
    while(*s)
    {
        //左括號入堆疊
        if(*s == '(' 
        || *s == '{'
        || *s == '[')
        {
            StackPush(&ST,*s);
        }
        else //右括號出堆疊
        {
            //防止越界，如果上來就是右括號
            if(StackEmpty(&ST))
            {
                StackDestroy(&ST);
                return false;
            }
            char ch = StackTop(&ST);
            if(ch == '(' && *s != ')'
            || ch == '{' && *s != '}'
            || ch == '[' && *s != ']')
            {
                StackDestroy(&ST);
                return false;
            }
            else
            {
                StackPop(&ST);
            }
        }
        s++;
    }
    bool ret = StackEmpty(&ST);
    StackDestroy(&ST);
    return ret;
}

225. 用佇列實作堆疊

鏈接: link.
原題描述：

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

實作 MyStack 類：

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

實作思路：
用兩個佇列互相倒入資料，入資料，往不為空的那個佇列入，保持另一個佇列為空，出資料，不為空的佇列前size-1個倒出佇列存放到另一個空佇列中，佇列元素的交換，再輸出隊尾的資料，這樣就實作了后進先出的原則


typedef int QueDataTypef;

typedef struct QueueNode
{
	struct Queue *next;
	QueDataTypef data;
}QueueNode;

typedef struct Queue 
{
	QueueNode *head;
	QueueNode *tail;
}Queue;
//初始化
void QueueInit(Queue *q);
//銷毀
void QueueDestroy(Queue *q);
//隊尾入隊
void QueuePush(Queue *q, int x);
//隊頭出隊
void QueuePop(Queue *q);
//判斷空
bool QueueEmpty(Queue *q);
//獲取隊頭資料
QueDataTypef QueueFront(Queue *q);
//獲取隊尾資料
QueDataTypef QueueBack(Queue *q);
//求佇列的元素個數
int QueueSize(Queue *q);
//初始化
void QueueInit(Queue *q) 
{
	assert(q);
	q->head = q->tail = NULL;
}
//銷毀
void QueueDestroy(Queue *q) 
{
	QueueNode* cur = q->head;
	
	while (cur) 
	{
		QueueNode *next = (QueueNode *)cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}

//隊尾入隊
void QueuePush(Queue *q, int x) 
{
	assert(q);
	QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		exit(-1);
		perror("QueuePush::malloc");
	}
	newNode->data = x;
	newNode->next = NULL;
	
	if (q->tail == NULL) 
	{
		q->head = q->tail = newNode;
	}
	else 
	{
		q->tail->next = (Queue *)newNode;
		q->tail = newNode;
	}
}
//隊頭出隊
void QueuePop(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head->next == NULL) 
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else 
	{
		QueueNode *next = (QueueNode *)q->head->next;
		free(q->head);
		q->head = next;
	}
}

//判斷空
bool QueueEmpty(Queue *q) 
{
	assert(q);
	return q->head ==  NULL ? true : false;
}
//獲取隊頭資料
QueDataTypef QueueFront(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}
//獲取隊尾資料
QueDataTypef QueueBack(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

//求佇列的元素個數
int QueueSize(Queue *q) 
{
	assert(q);
	int size = 0;
	QueueNode *cur = q->head;
	while (cur) 
	{
		cur = (QueueNode *)cur->next;
		size++;
	}
	return size;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
   MyStack* obj = (MyStack *)malloc(sizeof(MyStack));
   QueueInit(&obj->q1);
   QueueInit(&obj->q2);
   return obj;
}

void myStackPush(MyStack* obj, int x) {
    //往不為空的佇列里面倒資料,保證一個佇列是空的
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    //非空佇列往空佇列里面倒資料，只剩一個資料的時候就將他釋放并回傳
    Queue *pnoEmpty = &obj->q1;
    Queue *pEmpty = &obj->q2;
    if(QueueEmpty(pnoEmpty))
    {
        pEmpty = &obj->q1;
        pnoEmpty = &obj->q2;
    }
    while(QueueSize(pnoEmpty) > 1)
    {
        QueuePush(pEmpty,QueueFront(pnoEmpty));
        QueuePop(pnoEmpty);
    }
    int ret = QueueBack(pnoEmpty);
    QueuePop(pnoEmpty);
    return ret;
}

int myStackTop(MyStack* obj) {
    //佇列的尾部元素，等于堆疊頂的元素，取非空佇列的尾部元素
    int ret = 0;
    if(!QueueEmpty(&obj->q1))
    {
       ret = QueueBack(&obj->q1);
    }
    else
    {
       ret = QueueBack(&obj->q2);
    }
    return ret;
}

bool myStackEmpty(MyStack* obj) {
    //兩個佇列都不為空堆疊就不為空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); 
}

void myStackFree(MyStack* obj) {
    //兩個佇列都釋放，最后釋放obj
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

232. 用堆疊實作佇列

鏈接: link.

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

實作 MyQueue 類：

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

實作思路：
只需要在一個結構里面定義出來兩個堆疊，一個堆疊用于存取資料push，一個堆疊用來出資料pop，既然要實作先進先出的原則，不妨push堆疊中的元素，依次取出來后倒入到用于出資料的堆疊中pop，最后再將資料從pop中倒出

typedef int STData;
typedef struct Stack 
{
	STData *a;
	int capacity;
	int top;
}Stack;

//初始化
void StackInit(Stack *ST);
//堆疊銷毀
void StackDestroy(Stack *ST);
//入堆疊
void StackPush(Stack *ST, int x);
//彈堆疊
void StackPop(Stack *ST);
//獲取堆疊頂元素
int StackTop(Stack *ST);
//判斷堆疊是否空
bool StackEmpty(Stack *ST);
//獲取堆疊頂元素個數
int StackSize(Stack *ST);


//初始化
void StackInit(Stack *ST) 
{
	assert(ST);
	ST->a = (STData *)malloc(sizeof(int) * 4);
	ST->capacity = 4;
	ST->top = 0;
}

//堆疊銷毀
void StackDestroy(Stack *ST)
{
	assert(ST);
	free(ST->a);
	ST->a = NULL;
	ST->capacity = ST->top = 0;
}
//入堆疊
void StackPush(Stack *ST, int x) 
{
	assert(ST);
	if (ST->capacity == ST->top) 
	{
		STData *tmp = realloc(ST->a,sizeof(STData) * ST->capacity * 2);
		if (tmp == NULL) 
		{
			perror("relloc:");
			exit(-1);
		}
		ST->a = tmp;
		ST->capacity = ST->capacity * 2;
	}
	ST->a[ST->top++] = x;
}
//彈堆疊
void StackPop(Stack *ST) 
{
	assert(ST);
	if(!StackEmpty(ST))
	ST->top--;
}
//獲取堆疊頂元素
int StackTop(Stack *ST) 
{
	assert(ST);
	return ST->a[ST->top - 1];
}
//判斷堆疊是否空
bool StackEmpty(Stack *ST) 
{
	assert(ST);
	return ST->top == 0 ? true : false;
}
//獲取堆疊頂元素個數
int StackSize(Stack *ST) 
{
	assert(ST);
	return ST->top;
}

typedef struct {
    Stack push;
    Stack pop;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue *obj = (MyQueue *)malloc(sizeof(MyQueue));
    StackInit(&obj->pop);
    StackInit(&obj->push);
    return obj;
}

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

int myQueuePop(MyQueue* obj) {
    int ret = myQueuePeek(obj);
    StackPop(&obj->pop);
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    return StackTop(&obj->pop);
}   

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pop);
    StackDestroy(&obj->push);
    free(obj);
}

設計回圈佇列

鏈接: link.

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

你的實作應該支持如下操作：

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

實作思路：
為了方便標記回圈佇列的滿和空的狀態，多開辟出一個位置用于判斷佇列是滿的情況，而如果頭跟尾都是在一個位置的情況就是空隊，而入資料考慮從隊尾入，出資料從隊頭出，從隊尾入資料的話有tail記錄佇列的尾位置，直接可以將資料插入進去

在這里插入圖片描述

typedef struct {
    int *a;//陣列
    int front;//回圈佇列的頭
    int tail;//回圈佇列的尾
    int k;//存放多少個元素
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    obj->a = (int *)malloc(sizeof(int) * (k + 1));
    obj->front = obj->tail = 0;
    obj->k = k;
    return obj;
}
//入資料，既然要設計成回圈佇列，那么他就可以無限制的入資料，只不過超出了一定長度，會覆寫掉原先資料
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //如果佇列已經是滿的了，就不需要入資料
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //佇列不滿的情況，接著入資料，入進一次資料就表示成功
    else
    {
        obj->a[obj->tail++] = value;
       
        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;
    return obj->a[obj->front];
}
//取隊尾,取隊尾的資料要取這個下標的前一個位置的值，如果隊尾的位置是0呢，前一個位置就是-1，那不切實際，需要修正一下
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    int prevtail = obj->tail - 1;
    if(prevtail == -1)
    {
        prevtail = obj->k;
    }
    return obj->a[prevtail];
}
//剛初始化時，頭跟尾都是相同的，那時候還沒入資料，就以頭跟尾是相等的來判斷
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->tail ? true : false;
}
//判斷滿，多開辟一個位置（原先是k,多開是k+1），最后一個位置用來記錄滿不滿，如果tail等于k + 1，就表示已經滿了
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int tailnext = obj->tail + 1;
    if(tailnext == obj->k + 1)
    {
        tailnext = 0;
    }
    return tailnext == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->tail = obj->front = 0;
    free(obj);
}

在這里插入圖片描述

//入資料，既然要設計成回圈佇列，那么他就可以無限制的入資料，只不過超出了一定長度，會覆寫掉原先資料
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //如果佇列已經是滿的了，就不需要入資料
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //佇列不滿的情況，接著入資料，入進一次資料就表示成功
    else
    {
        obj->a[obj->tail++] = value;
       
        if(obj->tail == obj->k + 1)
        {
            obj->tail = 0;
        }
        return true;
    }
}

在這里插入圖片描述

實作功能：將資料依次出隊，先進先出的原則，當obj->front走到了k+1的位置，就表示資料已經出完了，front又可以回到原來的位置，此時的佇列是空的

//出隊,出一個資料，頭來到下一個位置，當頭到最后了整個資料都出完了，佇列又為空，所以需要置零
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->front++;
        if(obj->front == obj->k + 1)
        {
            obj->front = 0;
        }
        return true;
    }
}

在這里插入圖片描述

//判斷滿，多開辟一個位置（原先是k,多開是k+1），最后一個位置用來記錄滿不滿，如果tail等于k + 1，就表示已經滿了
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int tailnext = obj->tail + 1;
    if(tailnext == obj->k + 1)
    {
        tailnext = 0;
    }
    return tailnext == obj->front;
}

在這里插入圖片描述

//取隊尾,取隊尾的資料要取這個下標的前一個位置的值，如果隊尾的位置是0呢，前一個位置就是-1，那不切實際，需要修正一下
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    int prevtail = obj->tail - 1;
    if(prevtail == -1)
    {
        prevtail = obj->k;
    }
    return obj->a[prevtail];
}

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

標籤：其他

上一篇：保姆級教程CSS兩萬字筆記大總結【建議收藏】（上篇）

下一篇：[娛樂數學建模]如何優雅的吃掉肉夾饃并且不讓肉從旁邊溢位來

堆疊和佇列C語言實作附加力扣題

目錄

堆疊的概念

堆疊的實作

堆疊的宣告

堆疊的實作

壓堆疊

出堆疊

佇列

佇列宣告

佇列實作

銷毀

隊尾入隊

隊頭出隊

判空

獲取隊頭資料

獲取隊尾資料

求元素個數

力扣題

20. 有效的括號

225. 用佇列實作堆疊

232. 用堆疊實作佇列

設計回圈佇列