栈与队列
实现一个栈，先进入的数据一定是先出去的，怎么样利用队列实现这个特点呢？可以利用两个队列来进行数据顺序的调整。当需要删除数据时，可以先将数据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);
}
网友评论