国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【數(shù)據(jù)結(jié)構(gòu)與算法】用隊(duì)列實(shí)現(xiàn)棧&&用棧實(shí)現(xiàn)隊(duì)列&&設(shè)計(jì)循環(huán)隊(duì)列

2年前作者：阿亮joy.分類：Toy博客閱讀(26)違法舉報(bào)

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

??作者：@阿亮joy.
??專欄：《數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué)》
??座右銘：每個(gè)優(yōu)秀的人都有一段沉默的時(shí)光，那段時(shí)光是付出了很多努力卻得不到結(jié)果的日子，我們把它叫做扎根
用棧實(shí)現(xiàn)循環(huán)隊(duì)列,數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué),算法,leetcode,數(shù)據(jù)結(jié)構(gòu),C語言,棧和隊(duì)列


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

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

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

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

注意：

  • 你只能使用隊(duì)列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty
    這些操作。
  • 你所使用的語言也許不支持隊(duì)列。 你可以使用 list （列表）或者 deque（雙端隊(duì)列）來模擬一個(gè)隊(duì)列 ,只要是標(biāo)準(zhǔn)的隊(duì)列操作即可。

示例：

輸入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2],[], [], []]
輸出：
[null, null, null, 2, 2, false]

解釋：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回False

提示：

  • 1 <= x <= 9
  • 最多調(diào)用100 次 push、pop、top 和 empty
  • 每次調(diào)用 pop 和 top 都保證棧不為空

進(jìn)階：你能否僅用一個(gè)隊(duì)列來實(shí)現(xiàn)棧。

用兩個(gè)隊(duì)列實(shí)現(xiàn)棧

因?yàn)殛?duì)列是先進(jìn)先出的結(jié)構(gòu)，而棧是后進(jìn)先出的結(jié)構(gòu)，那我們用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧呢？其實(shí)可以這樣子實(shí)現(xiàn)：當(dāng)入數(shù)據(jù)的時(shí)候，往不為空的隊(duì)列入，保持另一個(gè)隊(duì)列為空；當(dāng)出數(shù)據(jù)的時(shí)候，依次出隊(duì)頭的數(shù)據(jù)，轉(zhuǎn)移到另一個(gè)隊(duì)列中保存，只剩一個(gè)數(shù)據(jù)的時(shí)候，pop 掉。如下圖所示：
用棧實(shí)現(xiàn)循環(huán)隊(duì)列,數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué),算法,leetcode,數(shù)據(jù)結(jié)構(gòu),C語言,棧和隊(duì)列

將這篇博客實(shí)現(xiàn)的隊(duì)列拷貝過來，然后將要求的函數(shù)接口就行了。具體代碼見下方：

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head; // 頭指針
	QNode* tail; // 尾指針
	int size;    // 節(jié)點(diǎn)的個(gè)數(shù)
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

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

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

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

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}

	// 隊(duì)列中沒有節(jié)點(diǎn)
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

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

	// 隊(duì)列中只有一個(gè)節(jié)點(diǎn)
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		//del = NULL;
	}

	pq->size--;
}

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;
}

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

	return pq->size == 0;
	//return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

//核心思路：
//1.入數(shù)據(jù)，往不為空的隊(duì)列入，保持另一個(gè)隊(duì)列為空
//2.出數(shù)據(jù)的時(shí)候，依次出隊(duì)頭的數(shù)據(jù)，轉(zhuǎn)移到另一個(gè)隊(duì)列中保存
//只剩一個(gè)數(shù)據(jù)時(shí)，pop掉
//不能改變隊(duì)列的結(jié)構(gòu)，只能調(diào)用提供的函數(shù)接口
typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;

MyStack* myStackCreate() 
{
    // 注意局部變量，出了作用域會(huì)銷毀
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    //初始化隊(duì)列
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

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) 
{
    // 找出誰是空隊(duì)列
    Queue* empty = &obj->q1;
    Queue* nonEmpty = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        nonEmpty = &obj->q1;
    }

    // 非空隊(duì)列前N-1個(gè)數(shù)據(jù)導(dǎo)入空隊(duì)列，剩下的一個(gè)數(shù)據(jù)就是棧頂元素
    while(QueueSize(nonEmpty) > 1)
    {
        QueuePush(empty, QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }

    int top = QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    return top;
}

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) 
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

用棧實(shí)現(xiàn)循環(huán)隊(duì)列,數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué),算法,leetcode,數(shù)據(jù)結(jié)構(gòu),C語言,棧和隊(duì)列

用一個(gè)棧實(shí)現(xiàn)隊(duì)列

用一個(gè)棧如何實(shí)現(xiàn)隊(duì)列呢？其實(shí)也很簡單，當(dāng)一個(gè)數(shù)據(jù)入隊(duì)時(shí)，先將該數(shù)據(jù)入隊(duì)，然后再將在該數(shù)據(jù)前面的數(shù)據(jù)依次 pop 掉，然后又依次入隊(duì)，就能實(shí)現(xiàn)后進(jìn)先出的棧結(jié)構(gòu)了。如下圖所示：
用棧實(shí)現(xiàn)循環(huán)隊(duì)列,數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué),算法,leetcode,數(shù)據(jù)結(jié)構(gòu),C語言,棧和隊(duì)列

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head; // 頭指針
	QNode* tail; // 尾指針
	int size;    // 節(jié)點(diǎn)的個(gè)數(shù)
}Queue;

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

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

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

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

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}

	// 隊(duì)列中沒有節(jié)點(diǎn)
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

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

	// 隊(duì)列中只有一個(gè)節(jié)點(diǎn)
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		//del = NULL;
	}

	pq->size--;
}

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;
}

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

	return pq->size == 0;
	//return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

typedef struct 
{
    Queue q;
} MyStack;

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

void myStackPush(MyStack* obj, int x) 
{
    // 數(shù)據(jù)先入隊(duì)
    QueuePush(&obj->q, x);
    // 前面的數(shù)據(jù)依次出隊(duì)，再依次入隊(duì)
    int i = 0;
    while(i < QueueSize(&obj->q) - 1)
    {
        int front = QueueFront(&obj->q);
        QueuePop(&obj->q);
        QueuePush(&obj->q, front);
        i++;
    }
}

int myStackPop(MyStack* obj) 
{
    int top = QueueFront(&obj->q);
    QueuePop(&obj->q);
    return top;
}

int myStackTop(MyStack* obj) 
{
    int top = QueueFront(&obj->q);
    return top;
}

bool myStackEmpty(MyStack* obj) 
{
    return QueueEmpty(&obj->q);
}

void myStackFree(MyStack* obj) 
{
    QueueDestroy(&obj->q);
    free(obj);
}

用棧實(shí)現(xiàn)循環(huán)隊(duì)列,數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué),算法,leetcode,數(shù)據(jù)結(jié)構(gòu),C語言,棧和隊(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 類：

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

說明：

你只能使用標(biāo)準(zhǔn)的棧操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)棧，只要是標(biāo)準(zhǔn)的棧操作即可。

示例 1：

輸入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2],[], [], []]
輸出：
[null, null, null, 1, 1, false]

解釋：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false


提示：

  • 1 <= x <= 9
  • 最多調(diào)用 100 次 push、pop、peek 和 empty
  • 假設(shè)所有操作都是有效的（例如，一個(gè)空的隊(duì)列不會(huì)調(diào)用 pop 或者 peek 操作）

用兩個(gè)棧實(shí)現(xiàn)隊(duì)列的這道題和用兩個(gè)隊(duì)列實(shí)現(xiàn)棧的思路差不多。先在隊(duì)列中定義兩個(gè)棧，分別是入數(shù)據(jù)的棧pushST和出數(shù)據(jù)的棧popST。當(dāng)入數(shù)據(jù)的時(shí)候，直接向棧pushST入數(shù)據(jù)。當(dāng)出數(shù)據(jù)時(shí)，需要考慮兩種情況：如果棧popST中沒有數(shù)據(jù)，就將pushST中的數(shù)據(jù)導(dǎo)過去，再將棧pushST棧頂?shù)臄?shù)據(jù) pop 掉；如果popST中有數(shù)據(jù)，直接 pop 掉棧頂?shù)臄?shù)據(jù)就行了。
用棧實(shí)現(xiàn)循環(huán)隊(duì)列,數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué),算法,leetcode,數(shù)據(jù)結(jié)構(gòu),C語言,棧和隊(duì)列

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

void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);

STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

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

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

//匿名結(jié)構(gòu)體
typedef struct 
{
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushST);
    StackInit(&q->popST);
    return q;
}

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

int myQueuePop(MyQueue* obj) 
{
    //如果popST中沒有數(shù)據(jù)，將pushST中的數(shù)據(jù)導(dǎo)過去
    //popST中的數(shù)據(jù)就符號(hào)先進(jìn)先出的順序了
    //如果popST中有數(shù)據(jù)，那么就直接pop popST中的數(shù)據(jù)
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }

    int front = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return front;
}

int myQueuePeek(MyQueue* obj) 
{
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            int top = StackTop(&obj->pushST);
            StackPop(&obj->pushST);
            StackPush(&obj->popST, top);
        }
    }
    return StackTop(&obj->popST);
}

bool myQueueEmpty(MyQueue* obj) 
{
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}

用棧實(shí)現(xiàn)循環(huán)隊(duì)列,數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué),算法,leetcode,數(shù)據(jù)結(jié)構(gòu),C語言,棧和隊(duì)列

??設(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ì)列，我們能使用這些空間去存儲(chǔ)新的值。

你的實(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ì)列是否已滿。

示例：

MyCircularQueue circularQueue = newMyCircularQueue(3); // 設(shè)置長度為 3
circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false，隊(duì)列已滿
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); //返回 4

提示：

  • 所有的值都在 0 至 1000 的范圍內(nèi)；
  • 操作數(shù)將在 1 至 1000 的范圍內(nèi)；
  • 請(qǐng)不要使用內(nèi)置的隊(duì)列庫。

本道題需要實(shí)現(xiàn)的函數(shù)接口有：創(chuàng)建循環(huán)鏈表、判斷循環(huán)鏈表是否為空、判斷循環(huán)鏈表是否為滿、數(shù)據(jù)入隊(duì)、數(shù)據(jù)出隊(duì)、返回隊(duì)頭數(shù)據(jù)、返回隊(duì)尾數(shù)據(jù)以及銷毀循環(huán)隊(duì)列。循環(huán)隊(duì)列可以采用數(shù)組或者鏈表的形式實(shí)現(xiàn)，但不管使用數(shù)組還是鏈表來實(shí)現(xiàn)循環(huán)隊(duì)列，需要多開一個(gè)空間或者加個(gè)size記錄循環(huán)隊(duì)列中數(shù)據(jù)的個(gè)數(shù)，否則無法將隊(duì)列為空和隊(duì)列為滿兩種情況區(qū)分開。

//重點(diǎn)：循環(huán)隊(duì)列，無論使用數(shù)組實(shí)現(xiàn)還是鏈表實(shí)現(xiàn)，都要
//多開一個(gè)空間，也就意味著，要是一個(gè)存k個(gè)數(shù)據(jù)的循環(huán)隊(duì)列
//要開k+1個(gè)空間，否則無法實(shí)現(xiàn)判空和判滿。

//數(shù)組實(shí)現(xiàn)：空：front == tail  滿：(tail+1)%(k+1) == front
//鏈表實(shí)現(xiàn)：空：tail == tail 滿：tail->next == front

typedef struct 
{
    int* a;
    int front;
    int back;
    int N;
} MyCircularQueue;


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

    return obj;
}

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

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

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if(myCircularQueueIsFull(obj))
        return false;
    
    obj->a[obj->back] = value;
    obj->back++;
    // 當(dāng)back在最后一個(gè)位置時(shí)，讓back回到下標(biāo)為0的位置
    obj->back %= obj->N;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
        return false;
    
    obj->front++;
    // 當(dāng)front在最后一個(gè)位置時(shí)，讓front回到下標(biāo)為0的位置
    obj->front %= obj->N;

    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 if(obj->back == 0)
    //     return obj->a[obj->N -1];
    // else    
    //     return obj->a[obj->back - 1];

    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[(obj->back - 1 + obj->N) % obj->N];
}

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

用棧實(shí)現(xiàn)循環(huán)隊(duì)列,數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué),算法,leetcode,數(shù)據(jù)結(jié)構(gòu),C語言,棧和隊(duì)列

自定義循環(huán)隊(duì)列

a：整型指針，指向申請(qǐng)的空間
front：隊(duì)頭的位置
back：隊(duì)尾位置的下一個(gè)位置
N：數(shù)組的長度 = k + 1

typedef struct 
{
    int* a;
    int front;
    int back;
    int N;
} MyCircularQueue;

創(chuàng)建循環(huán)鏈表

需要注意的是，要給隊(duì)列循環(huán)申請(qǐng) k + 1個(gè)空間，來區(qū)分隊(duì)列是空還是滿

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

    return obj;
}

判斷循環(huán)隊(duì)列是否為空

當(dāng)obj->front == obj->back時(shí)，循環(huán)隊(duì)列為空

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

判斷循環(huán)隊(duì)列是否為滿

當(dāng)(obj->back + 1) % obj->N == obj->front時(shí)，循環(huán)隊(duì)列為滿

用棧實(shí)現(xiàn)循環(huán)隊(duì)列,數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué),算法,leetcode,數(shù)據(jù)結(jié)構(gòu),C語言,棧和隊(duì)列

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

數(shù)據(jù)入隊(duì)

1.當(dāng)循環(huán)隊(duì)列為滿時(shí)，返回 false
2.當(dāng)循環(huán)隊(duì)列不為滿時(shí)，數(shù)據(jù)入隊(duì)obj->a[obj->back] = value, obj->back++
3.當(dāng)back在最后一個(gè)位置時(shí)，讓back回到下標(biāo)為 0 的位置obj->back %= obj->N

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if(myCircularQueueIsFull(obj))
        return false;
    
    obj->a[obj->back] = value;
    obj->back++;
    // 當(dāng)back在最后一個(gè)位置時(shí)，讓back回到下標(biāo)為0的位置
    obj->back %= obj->N;
    return true;
}

數(shù)據(jù)出隊(duì)

1.當(dāng)循環(huán)隊(duì)列為空時(shí)，返回 false
2.當(dāng)循環(huán)隊(duì)列不為空時(shí)，數(shù)據(jù)出隊(duì)obj->front++
3.當(dāng)front在最后一個(gè)位置時(shí)，讓front回到下標(biāo)為 0的位置obj->front %= obj->N

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
        return false;
    
    obj->front++;
    // 當(dāng)front在最后一個(gè)位置時(shí)，讓front回到下標(biāo)為0的位置
    obj->front %= obj->N;

    return true;
}

返回隊(duì)頭數(shù)據(jù)

1.當(dāng)循環(huán)隊(duì)列為空時(shí)，返回 false
2.當(dāng)循環(huán)隊(duì)列不為空時(shí)，返回隊(duì)頭數(shù)據(jù)return obj->a[obj->front]

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}

返回隊(duì)尾數(shù)據(jù)

1.當(dāng)循環(huán)隊(duì)列為空時(shí)，返回 false
2.當(dāng)循環(huán)隊(duì)列不為空時(shí)，返回隊(duì)尾數(shù)據(jù)return obj->a[(obj->back - 1 + obj->N) % obj->N]

用棧實(shí)現(xiàn)循環(huán)隊(duì)列,數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué),算法,leetcode,數(shù)據(jù)結(jié)構(gòu),C語言,棧和隊(duì)列

int myCircularQueueRear(MyCircularQueue* obj) 
{
    // if(myCircularQueueIsEmpty(obj))
    //     return -1;
    // else if(obj->back == 0)
    //     return obj->a[obj->N -1];
    // else    
    //     return obj->a[obj->back - 1];

    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[(obj->back - 1 + obj->N) % obj->N];
}

銷毀循環(huán)隊(duì)列

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

??一道小小的選擇題??

現(xiàn)有一循環(huán)隊(duì)列，其隊(duì)頭為front，隊(duì)尾為rear，循環(huán)隊(duì)列長度為N,最多存儲(chǔ)N-1個(gè)數(shù)據(jù)。其隊(duì)內(nèi)有效長度為（ ）
A.(rear - front + N) % N + 1
B.(rear - front + N) % N
C.(rear - front) % (N + 1)
D.(rear - front + N) % (N - 1)

答案：B
解析：有效長度一般是rear-front，但是循環(huán)隊(duì)列中rear有可能小于front，減完之后可能是負(fù)數(shù)，所以需要+N，此時(shí)結(jié)果剛好是隊(duì)列中有效元素個(gè)數(shù)，但如果rear大于front，減完之后就是有效元素個(gè)數(shù)了，再加N后有效長度會(huì)超過N，故需要%N。

??總結(jié)??

本篇博客主要講解三道 OJ 題，主要考察的是大家對(duì)棧和隊(duì)列性質(zhì)的理解。以上就是本篇博客的全部內(nèi)容了，如果大家覺得有收獲的話，可以點(diǎn)個(gè)三連支持一下！謝謝大家啦！??????文章來源地址http://www.zghlxwxcb.cn/news/detail-807958.html

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

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包