前言

1.用佇列實作堆疊

2.用堆疊實作佇列

3.回圈佇列

前言

前面在學習了堆疊和佇列的實作之后，相信大家對堆疊和佇列的結構和使用方式都有了一些理解，

下面我們就來進行一些練習，這這章的練習相對于原來在難度上有了一些提升，

原來的題只需要實作一個介面，而今天的練習題需要實作多個介面，

1.用佇列實作堆疊

225. 用佇列實作堆疊 - 力扣（LeetCode） (leetcode-cn.com)

堆疊：后進先出；佇列：先進先出

方法：

創建兩個佇列，用來來回導資料，

入堆疊：將資料放入不為空的佇列，

出堆疊：將不為空的佇列中的資料以出隊入堆疊的方式放入空佇列，直到該佇列中只剩一個資料，

這個資料就是要出堆疊的資料，直接將他pop掉即可，

堆疊頂：回傳隊尾，

檢測堆疊是否為空：兩個佇列都為空，則堆疊為空，

口說無憑，請看圖：

如圖：

佇列1中有4個數，以1，2，3，4順序入隊，所以1為隊頭，4為隊尾，

根據佇列先進先出規則，1應該先出隊，而這里我們要實作堆疊，即后進先出，即應該先出隊尾資料，

所以我們將除隊尾資料全部先匯入佇列2中，這樣佇列1中就只剩下隊尾資料，

注意：佇列1中的資料匯入佇列2中后，資料的相對位置是不變的，

即：

最后出堆疊，就可得到堆疊頂資料，

代碼如下：

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

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}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;
}

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

//入隊
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc");
		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;
	}
}

//出隊
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* next = pq->head->next;
	free(pq->head);
	
	pq->head = next;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
	
}


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->head == NULL;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	int size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
//因為C語言中沒有直接可以呼叫的堆疊和佇列，所以需要將自己實作的佇列拷貝到前面


typedef struct {//在堆疊中創建兩個佇列
    Queue q1;
    Queue q2;
} MyStack;

bool myStackEmpty(MyStack* obj);
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))//入堆疊時向不為空的佇列插入資料，都為空這里默認向佇列2中插入
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
    
}

int myStackPop(MyStack* obj) {
    Queue*empty = &obj->q1;//出堆疊時需在不為空的佇列里出，所以先找不為空的佇列
    Queue*noempty = &obj->q2;//默認佇列1不為空
    if(!QueueEmpty(&obj->q1))//如果佇列1不為空，則交換兩佇列
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }
    while(QueueSize(noempty)>1)//將不為空佇列中除隊尾資料全部放入空佇列中
    {
        QueuePush(empty,QueueFront(noempty));
        QueuePop(noempty);
    }
    int pop = QueueFront(noempty);//剩下的最后一個資料
    QueuePop(noempty);//將資料Pop掉
    return pop;
}

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

2.用堆疊實作佇列

232. 用堆疊實作佇列 - 力扣（LeetCode） (leetcode-cn.com)

方法：

與上題類似，創建兩個堆疊，將資料入堆疊與入隊相同，堆疊1用來入資料，堆疊2用來出資料，

不過出隊時，隊頭的資料位于堆疊底，所以還是要將除堆疊底的資料全部匯入另一個堆疊中，

但不同的是，佇列實作堆疊時，導過去后資料的順序不變，所以需要來回導；而這里倒過去后資料順序會顛倒，所以不需要再導回去，可以直接出隊，直到該堆疊中沒有資料，

口說無憑，請看圖：

這樣下一次再需要出隊時，只需將堆疊2的堆疊頂Pop即可，直到堆疊2中沒有資料，然后再從堆疊1中導資料，

代碼如下：

typedef int STDataType;

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

//初始化
void StackInit(Stack*ps);

//銷毀
void StackDestroy(Stack* ps);

//壓堆疊
void StackPush(Stack* ps, STDataType x);

//出堆疊
void StackPop(Stack* ps);

//堆疊頂
STDataType StackTop(Stack* ps);

//判斷堆疊是否為空
bool StackEmpty(Stack* ps);

//堆疊中元素個數
int StackSize(Stack* ps);


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

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

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


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

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

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


int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
//同樣需拷貝自己實作的堆疊



typedef struct {//創建兩個堆疊，s1用來入資料，s2用來出資料
    Stack s1;
    Stack s2;
} MyQueue;


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

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->s1,x);//直接將資料Push到s1中
}

int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->s2))//pop資料之前先檢查s2中是否有資料，沒有資料需從s1中匯入
    {
        while(!StackEmpty(&obj->s1))
        {
            StackPush(&obj->s2,StackTop(&obj->s1));
            StackPop(&obj->s1);
        }
    }
    int pop = StackTop(&obj->s2);//直接pop堆疊頂資料即可
    StackPop(&obj->s2);
    return pop;
}

int myQueuePeek(MyQueue* obj) {//回傳隊尾資料(即s2堆疊頂資料)
    if(StackEmpty(&obj->s2))//回傳資料之前先檢查s2中是否有資料，沒有資料需從s1中匯入
    {
        while(!StackEmpty(&obj->s1))
        {
            StackPush(&obj->s2,StackTop(&obj->s1));
            StackPop(&obj->s1);
        }
    }
    return StackTop(&obj->s2);
}

bool myQueueEmpty(MyQueue* obj) {//兩個堆疊都為空，佇列才為空
    return StackEmpty(&obj->s1)&&StackEmpty(&obj->s2);
}

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

3.回圈佇列

622. 設計回圈佇列 - 力扣（LeetCode） (leetcode-cn.com)

這道題的意思是：

設計一個佇列，這個佇列的大小是固定的，且佇列頭尾相連，然后該佇列能夠實作題目中的操作，

那么是使用陣列實作，還是用鏈表實作呢？我們接著往下看，

例如：用k表示陣列大小

圖中我們用陣列實作，用head和tail表示隊頭隊尾下標，每插入一個資料，在陣列tail位置插入，然后再將tail++，

但是有個問題如果將head==tail認為是佇列為空的條件，那么怎么判斷佇列滿了呢？

面對這個問題我們這樣解決：將陣列的空間大小增加1，即陣列比佇列大1個空間，

這樣：當 head = tail 時佇列為空，(tail+1)%(k+1) = head 時佇列滿了，

且以鏈表實作時也會多申請一個空間，

代碼如下：陣列實作，

typedef struct {
    int*arr;
    int head;//隊頭
    int tail;//隊尾
    int capacity;//佇列容量
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr = (int*)malloc(sizeof(int)*(k+1));//申請陣列空間
    obj->head = 0;
    obj->tail = 0;
    obj->capacity = k;//佇列大小
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

//插入資料
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))//檢查容量
    {
        return false;
    }
    else
    {
        obj->arr[obj->tail] = value;//在隊尾位置插入
        obj->tail++;//隊尾向后移動
        obj->tail %= obj->capacity+1;//當隊尾移動到陣列最后一個元素后面的下標時，隊尾回到陣列下標為0的位置 
        return true;
    }
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))//檢測佇列是否為空
    {
        return false;
    }
    else
    {
        obj->head++;
        obj->head %= obj->capacity+1; 當隊頭移動到陣列最后一個元素后面的下標時，隊尾回到陣列下標為0的位置 

        return true;

    }

}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;//佇列為慷訓傳-1
    }
    else
    {
        return obj->arr[obj->head];//回傳隊頭資料
    }
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;//佇列為慷訓傳-1
    }
    else
    {
        return obj->arr[(obj->tail+obj->capacity)%(obj->capacity+1)];//回傳下標為tail位置前面一個位置資料
    }
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;//head==tail佇列為空
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->capacity+1) == obj->head;//為防止陣列越界，不能直接將tail+1與head比較
}

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

鏈表實作與陣列實作類似，只是判斷佇列滿的條件的不一樣，

鏈表判滿的條件時tail->next = head;

代碼如下：

typedef struct ListNode1 ListNode1;
struct ListNode1{
    int data;
    ListNode1* next;
};


typedef struct {
    ListNode1* front;//創建頭尾指標指向佇列頭和尾
    ListNode1* tail;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->front = NULL;
    ListNode1* cur = NULL;
    while (k > -1)//創建k+1個結點
    {
        if (obj->front == NULL)
        {
            obj->front = (ListNode1*)malloc(sizeof(ListNode1));
            obj->front->next = NULL;
            cur = obj->front;
        }
        else
        {
            ListNode1* next = (ListNode1*)malloc(sizeof(ListNode1));
            cur->next = next;
            cur = next;
        }
        k--;
    }
    cur->next = obj->front;//將鏈表成環
    obj->tail = obj->front;//頭尾指標復位
    return obj;
}


bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        obj->tail->data = value;//插入資料將資料放入tail結點
        obj->tail = obj->tail->next;//tail結點向后移動
        return true;
    }
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->front = obj->front->next;//洗掉資料時直接將頭指標向后移動，不用將該位置的資料洗掉
        return true;
    }
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->front->data;//回傳頭指標結點處的資料
    }
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        ListNode1* cur = obj->front;//因為不知到隊尾位置，只知道隊尾的下一個位置，所以需要遍歷鏈表尋找隊尾，
        while (cur->next != obj->tail)
        {
            cur = cur->next;
        }
        return cur->data;
    }
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->tail;//head==tail佇列為空
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->tail->next == obj->front;//tail->next == head 佇列滿了
}

void myCircularQueueFree(MyCircularQueue* obj) {
    ListNode1* cur = obj->front->next;
    while (cur != obj->front)//釋放鏈表結點
    {
        ListNode1* next = cur->next;
        free(cur);
        cur = next;
    }
    free(cur);
    free(obj);
}

如有錯誤，或更好的方法，可以在評論區一起交流喲~

你的點贊支持就是我創作的動力！

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

標籤：其他

上一篇：＜LeetCode天梯＞Day016 整數反轉（暴力求解+直接反轉） | 初級演算法 | Python

下一篇：百度后端C++，一面、二面 + 主管面面經（已拿offer）

【資料結構】堆疊和佇列OJ練習(堆疊和佇列相互實作+回圈佇列實作)

前言

1.用佇列實作堆疊

2.用堆疊實作佇列

3.回圈佇列