双队列实现栈

栈与队列

实现一个栈，先进入的数据一定是先出去的，怎么样利用队列实现这个特点呢？可以利用两个队列来进行数据顺序的调整。当需要删除数据时，可以先将数据push到一个队列当中，pop时，因为队列是先进先出的，所以可以将队尾的元素保留下来，其余元素按照出队的顺序入队到另外一个队列当中，然后pop第一个队列的最后一个元素，这样就实现了栈的删除操作


双队列实现栈

先定义队列，这里用循环队列，用于实现栈的队列数据结构 SQueue

#ifndef StackQueue_h
#define StackQueue_h
#include <stdio.h>
#include <stdbool.h>

#define max_size 100 // 假设队列环最大空间100

typedef char QData.  // 队列数据类型

// 队列数据结构
typedef struct SQueue {
    QData *data;    // 用数组存储队列元素
    int head;
    int tail;
    int size;       // 循环队列环长度
}SQueue;

双队列实现栈的数据结构 QStack

// 用双队列实现的栈
Typedef struct QStack {
    SQueue queue1;
    SQueue queue2;
    int size;       // 栈中有效元素长度
}QStack;

// 栈初始化
void q_stack_init(QStack *stack);

// 入栈
void q_stack_push(QStack *stack, QData element);

// 出栈
void q_stack_pop(QStack *stack, QData *value);

// 栈顶
QData* q_stack_peek(QStack *stack, QData *element);

bool q_stack_empty(QStack *stack);

size_t q_stack_length(QStack *stack);


#endif /* StackQueue_h */

循环队列SQueue实现

#include <stdlib.h>

// 队列初始化函数
void queue_init(Queue *queue) {
    if (queue == NULL） return;

    queue->data = (QData *)malloc(sizeof(QData)*max_size);
    queue->head = 0;
    queue->tail = 0;
    queue->size = max_size;  // 这里size记录的是环队列最大空间
}

// 队列是否为空
bool queue_empty(SQueue *queue) {
    return queue->tail == queue->head;
}    

// 循环队列是否已满
bool queue_full(SQueue *queue) {
    return (queue->tail+1)%queue->size = queue->head;
}

// 入队列
void queue_en(SQueue *queue, QData element) {
    if (queue == NULL) return;
    if (queue_full(queue)) {
        printf("队列已满了");
        return;
    }

    queue->data[queue->tail] = element;
    // 尾指针偏移，重新回到数组的初始地址，继续入队，于是这就形成了循环队列。
    queue->tail = (queue->tail+1)%queue->size;
}

// 出队列
void queue_de(SQueue *queue, QData *data) {
    if (queue_empty(queue)) {
        printf("队列是空的");
        return;
    }

    *data = queue->data[queue->head];
    // 头指针偏移
    queue->head = (queue->head+1)%queue->size; 
}

// 取队列头元素
QData* queue_peek(SQueue *queue) {
    if (queue_empty(queue)) {
        printf("队列是空的");
        return NULL;
    }
    // 只获取队列头，指针无需偏移
    return &queue->data[queue->head];
}

// 循环队列长度
int queue_length(SQueue *queue) {
    return (queue->tail - queue->head + queue->size)%queue->size;
}

// 销毁队列
void queue_destory(SQueue *queue) {
    if (!queue) return;

    free(queue->data);
    queue->data = NULL;
    queue->head = queue->tail = queue->size = 0;
}

栈 StackQueue.c具体实现

栈初始化

#include <stdlib.h>

/**
* ----------- 双队列实现栈操作 ------------
*/

/**
 * 栈初始化
 */
void q_stack_init(QStack *stack) {
    if (stack == NULL) return;
    
    queue_init(&stack->queue1);
    queue_init(&stack->queue2);
    stack->size = 0;
}

入栈

// 入栈
void q_stack_push(QStack *stack, QData element) {
    if (stack == NULL) return;
    
    // 入栈找到不为空的那个队列
    SQueue *push = NULL;
    // 队列1不为空，push
    if (!queue_empty(&stack->queue1)) {
        push = &stack->queue1;
    } else {
        // 否则队列2不为空，或者两个队列都为空, 随便en那个队列都可以
        push = &stack->queue2;
    }
    queue_en(push, element);
    stack->size++;  // 每次入栈，栈有效元素个数+1
}

出栈

// 出栈
void q_stack_pop(QStack *stack, QData *value) {
    if (stack == NULL || stack->size ==0) return;
    
    SQueue *de_queue = NULL;
    SQueue *en_queue = NULL;
    // 将不为空的队列元素转移到空队列，queue1和queue2至少有个队列不为空，另一个为空
    if (!queue_empty(&stack->queue1)) {
        de_queue = &stack->queue1;
        en_queue = &stack->queue2;
    } else {
        de_queue = &stack->queue2;
        en_queue = &stack->queue1;
    }
    // 首先确保en_queue为空，将de_queue中元素转移到en_queue，但是保留队列尾最后一个元素
    if (queue_empty(en_queue)) {
        while (queue_length(de_queue) > 1) {
            QData de_data;
            // 不为空队列出队列
            queue_de(de_queue, &de_data);
            
            // de_queue出队列元素进入en_queue队列
            queue_en(en_queue, de_data);
        }
    }
    
    // 循环结束，de_queue队列尾最后一个元素
    queue_de(de_queue, value);
    // 栈总有效元素个数-1
    stack->size--;
}

取栈顶

/** 取栈顶元素：与出栈操作类似，唯一不同的就是，将元素移动到剩下最后一个元素时不要出队列，而是返回该元素，这个元素依然存在该栈中，为确保至少一个队列为空， 读取完成后也要转移到en_queue队列中去
 **/
QData* q_stack_peek(QStack *stack, QData *element) {
    if (stack == NULL || stack->size ==0) return NULL;
    
    // queue1&queue2至少有个队列不为空
    if (!queue_empty(&stack->queue1)) {
        return queue_peek(&stack->queue1);
    } else {
        return queue_peek(&stack->queue2);
    }
    return NULL;
}

栈式队列是否空

/**
 * 双队列实现栈是否空
 */
bool q_stack_empty(QStack *stack) {
    if (stack == NULL || stack->size ==0) return true;
    if (queue_empty(&stack->queue1) && queue_empty(&stack->queue2)) {
        return true;
    } else {
        return false;
    }
}

栈长度

/**
 * 栈长度
 */
size_t q_stack_length(QStack *stack) {
    if (stack == NULL || stack->size ==0) return 0;
    
    if (queue_empty(&stack->queue1) && queue_empty(&stack->queue2)) {
        return 0;
    } else if (!queue_empty(&stack->queue1)) {
        return queue_length(&stack->queue1);
    } else {
        return queue_length(&stack->queue2);
    }
}

栈销毁

// 销毁
void q_stack_destory(QStack *stack) {
    if (stack == NULL) return;
    
    queue_destory(&stack->queue1);
    queue_destory(&stack->queue2);
}

测试双队列栈

void stack_queue_main() {
    QStack qstack;
    q_stack_init(&qstack);
    q_stack_push(&qstack, 'm');
    q_stack_push(&qstack, '8');
    q_stack_push(&qstack, 'b');
    q_stack_push(&qstack, 'u');
    q_stack_push(&qstack, 'a');
    q_stack_push(&qstack, '5');
    
    char pop;
    q_stack_pop(&qstack, &pop);
    q_stack_push(&qstack, 't');
    q_stack_push(&qstack, 'e');
    char data;
    q_stack_pop(&qstack, &data);
    printf("two queue stack pop: %c\n",data);
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
禁止转载，如需转载请通过简信或评论联系作者。
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,088评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,715评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,361评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,099评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 60,987评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,063评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,486评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,175评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,440评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,518评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,305评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,190评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,550评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,880评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,152评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,451评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,637评论 2赞 335