隊列的實現(xiàn)
這里的隊列我們使用鏈?zhǔn)疥犃?，好處就是可以很方便的取出隊頭的元素。
使用順序隊列取出隊頭元素所花費的時間復(fù)雜度為O（N），把后面的元素向前移動一個下標(biāo)所花費的時間。
鏈?zhǔn)疥犃械拇鎯Y(jié)構(gòu)：
typedef int QueueDataType;
//節(jié)點類型
typedef struct QueueNode
{
QueueDataType data;
struct QueueNode* next;
}QNode;
//隊列類型
typedef struct Queue
{
QNode* phead; //頭指針
QNode* ptail; //尾指針 使用頭指針和尾指針來實現(xiàn)隊列的刪除和插入操作。
int size;
}Que;
接口函數(shù)的實現(xiàn)
`
void QueueInit(Que* pq);
void QueueDestory(Que* pq);
void QueuePush(Que* pq, QueueDataType x);
void QueuePop(Que* pq);
QueueDataType QueueFront(Que* pq);
QueueDataType QueueBack(Que* pq);
int QueueSize(Que* pq);
bool QueueEmpty(Que* pq);
//實現(xiàn)
//初始化隊列
void QueueInit(Que* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//銷毀隊列，這里相當(dāng)于單鏈表的銷毀，一個節(jié)點一個節(jié)點銷毀
void QueueDestory(Que* pq)
{
assert(pq);
//刪除鏈?zhǔn)疥犃?/span>
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
}
//相當(dāng)于單鏈表的尾插，先新建一個節(jié)點，初始化這個節(jié)點，尾插到隊列中，這里考慮兩種情況，隊列為空和不為空的情況
void QueuePush(Que* pq, QueueDataType x)
{
assert(pq);
//新建節(jié)點
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc failed!\n");
return;
}
newnode->data = x;
newnode->next = NULL;
//考慮此時的隊列為空
if (pq->ptail == NULL)
{
assert(pq->phead == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
//不為空時，把newnode賦值給phead->next,然后ptail = newnode
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
//相當(dāng)于單鏈表的頭刪。需要考慮兩種情況，隊列為空就不可以刪除，隊列不為空只有一個節(jié)點phead和ptail都要賦值成NULL，否則會出現(xiàn)ptail為野指針的情況，多個節(jié)點時，相當(dāng)于單鏈表的頭刪，
void QueuePop(Que* pq)
{
//相當(dāng)于單鏈表的頭刪
assert(pq);
//處理隊列為空的情況
assert(!QueueEmpty(pq));
//處理只有一個節(jié)點的情況
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else //考慮多個節(jié)點的情況
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
QueueDataType QueueFront(Que* pq)
{
assert(pq);
//處理隊列為空的情況
assert(!QueueEmpty(pq));
return pq->phead->data;
}
//返回隊列的尾部元素，這里會在用隊列實現(xiàn)棧的時候用到
QueueDataType QueueBack(Que* pq)
{
assert(pq);
//處理隊列為空的情況
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
int QueueSize(Que* pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Que* pq)
{
assert(pq);
return pq->phead == NULL && pq->ptail == NULL;
//return pq->size == 0;
}
用隊列實現(xiàn)棧
leetcode做題鏈接
主要思想：用兩個隊列來實現(xiàn)一個棧的功能，先進(jìn)后出，后進(jìn)先出的功能，我們可以這樣，在不為空的隊列里入數(shù)據(jù)，然后再把數(shù)據(jù)前n-1個數(shù)數(shù)據(jù)倒入另一個隊列中，具體的過程用圖展示：
第一步：準(zhǔn)備兩個隊列，開始入數(shù)據(jù)
第二步：往不為空的隊列里入數(shù)據(jù)，如果兩個都為空，任選一個入數(shù)據(jù)
push 四次。可得隊列中的數(shù)據(jù)如下圖所示：
第三步：出數(shù)據(jù)，需要先把q1中的數(shù)據(jù)1、2、3倒入q2中，然后使用QueueBack()接口獲取隊尾數(shù)據(jù)4。
以上就是出數(shù)據(jù)和入數(shù)據(jù)的過程。
具體代碼如下：
typedef struct {
Que q1;
Que q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
if(obj == NULL)
{
perror("malloc failed!\n");
return NULL;
}
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x); //入數(shù)據(jù)，往不為空的隊列里如數(shù)據(jù)
}
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
//假設(shè)為空
Que* pEmptyQ = &obj->q1;
Que* pNonEmptyQ = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
pEmptyQ = &obj->q2;
pNonEmptyQ = &obj->q1;
}
//倒數(shù)據(jù),把非空隊列的數(shù)據(jù)導(dǎo)入空隊列，剩余一個就是棧頂元素
while(QueueSize(pNonEmptyQ)>1)
{
QueuePush(pEmptyQ, QueueFront(pNonEmptyQ));
QueuePop(pNonEmptyQ);
}
int top = QueueFront(pNonEmptyQ);
QueuePop(pNonEmptyQ);
return top;
}
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
用棧實現(xiàn)隊列
leetcode 做題鏈接
基本思想
使用兩個棧，一個為入數(shù)據(jù)的棧，一個為出數(shù)據(jù)的棧，把數(shù)據(jù)入到入數(shù)據(jù)的棧，然后出數(shù)據(jù)到出數(shù)據(jù)的棧，基本方法如下：入隊列1 2 3 4。
第一步：初始化兩個棧。
第二步：入數(shù)據(jù)push 1 2 3 4
第三步：導(dǎo)數(shù)據(jù)到popst中
第四步：從popst中出數(shù)據(jù)
實現(xiàn)代碼如下：
typedef struct {
ST pushst;
ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
if(obj==NULL)
{
perror("malloc failed!\n");
return NULL;
}
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj) {
int front = myQueuePeek(obj);
STPop(&obj->popst);
return front;
}
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&obj->popst))
{
while(!STEmpty(&obj->pushst))
{
STPush(&obj->popst,STTop(&obj->pushst));
STPop(&obj->pushst);
}
}
return STTop(&obj->popst);
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj) {
STDestory(&obj->pushst);
STDestory(&obj->popst);
free(obj);
}
設(shè)計循環(huán)隊列
leetcode做題鏈接
循環(huán)隊列的要點：如何用一個順序表實現(xiàn)一個循環(huán)隊列，front為隊頭，rear為隊尾，判滿：rear + 1 == front為滿，判空：rear == front 為空。
第一步，初始化一個隊列，k為5，n為6
第二步：出隊列 front++；再入數(shù)據(jù) 6、7。
此時的rear，跑到了front的前面，我們可以 讓rear % （k+1）保持rear永遠(yuǎn)不會越界front也可以使用這個公式保證front永遠(yuǎn)不會越界
獲取隊尾元素的兩種方法：
求元素的個數(shù)的方法： （rear - front + k+1）% （k+1）
具體的實現(xiàn)代碼如下：文章來源：http://www.zghlxwxcb.cn/news/detail-512164.html
typedef struct {
int front;
int rear;
int k;
int* a;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear+1)%(obj->k+1) == obj->front;
}
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if(obj == NULL)
{
perror("malloc failed!\n");
return NULL;
}
obj->a = (int*)malloc(sizeof(int)*(k+1));
if(obj->a == NULL)
{
perror("malloc failed!\n");
return NULL;
}
obj->front = obj->rear = 0;
obj->k = k;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->rear] = value;
obj->rear++;
obj->rear %= (obj->k+1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->front++;
obj->front%=(obj->k+1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
//return obj->a[(obj->rear+obj->k)%(obj->k+1)];
if(obj->rear==0)
{
return obj->a[obj->k];
}
else
{
return obj->a[obj->rear-1];
}
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
好的我們下一篇再見。文章來源地址http://www.zghlxwxcb.cn/news/detail-512164.html
到了這里，關(guān)于棧和隊列（二） 隊列的實現(xiàn)，用棧實現(xiàn)隊列，用隊列實現(xiàn)棧，設(shè)計循環(huán)隊列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
