栈与队列
实现思路
（1） 使用两个栈A,B，其中假定A负责push操作，B负责pop操作。使用一个变量back_elem来存储最后添加的元素。
（2） 实现队列的push操作， 每次进行添加操作，都会相应得对栈A进行添加元素。并对back_elem赋值
（3） 实现队列的pop操作，每次进行删除操作，因为栈B负责pop操作，
两个关键点：
- 入栈为push栈，出栈是pop栈
- 只有pop为空时才能将元素从push栈转移到pop栈
-
而且一次性push完成，这个过程可以是队列en()方法或者是de()方法执行
队列
先定义栈：数组结构，新建StackTable.h
#ifndef StackTable_h
#define StackTable_h
#include <stdio.h>
#define MAXSTACK 100
typedef int SElemType;
typedef struct Stack {
SElemType *data // 栈数据
int stackTop; // 栈顶标记
int size;
} Stack;
#include "StackTable.h"
#include <stdlib.h>
#include <stdbool.h>
// 创建栈数据结构
Stack* createStack() {
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->data = (SELEMType *)malloc(sizeof(SELEType)*MAXSTACK);
stack->stackTop = -1;
stack->size = MAXSTACK;
return stack;
}
// 栈是否空
bool stack_empty(Stack *stack) {
return stack->stackTop == -1;
}
入栈：
int stack_push(Stack *stack, SELEMType data) {
If (stack == NULL || stack->data == NULL) return 0;
// 判断栈顶溢出，top栈顶自增后设置
if (stack->stackTop+1 >= stack->size) {
printf("栈满.");
return 0;
} else {
// 栈顶赋值自增
stack->data[++(stack->stackTop)] = data;
return 1;
}
}
出栈：
int stack_pop(Stack *stack, SElemType *data) {
if (stack_empty(stack)) {
printf("栈为空.");
return 0;
}
*data = stack->data[(stack->stackTop)--];
return 1;
}
栈顶：
int stack_peep(Stack *stack, SElemType *data) {
if (stack_empty(stack)) {
printf("栈为空.");
return 0;
}
*data = stack->data[(stack->stackTop)];
return 1;
}
栈长
int stack_length(Stack *stack) {
if (stack == NULL) return 0;
return stack->stackTop;
}
遍历：
void stack_iterator(Stack *stack) {
if (stack_empty(stack)) return;
int I, length = stack->stackTop;
for (I=0;i<length;i++) {
SELemType item = stack-data[i];
printf("%d ", item);
}
printf("\n");
}
入队列
入队列
出队列
出队列
定义栈式队列 StackQueue
#include "StackQueue.h"
#include "StackTable.h"
#include <stdlib.h>
Define max_stack = 100;
/**
* 双栈队列
*/
Typedef struct StackQueue {
Stack *push_stack;
Stack *pop_stack;
}StackQueue，*PSQueue;
创建栈式队列
PSQueue create_stack_queue() {
PSQueue queue = (PSQueue)malloc(sizeof(StackQueue));
queue->push_stack = createStack(max_stack);
queue->pop_stack = createStack(max_stack);
return queue;
}
加入队列： 如果stack_push往stack_pop中倒入数据， 必须stack_push中所有数据一次性倒完
void s_queue_en(PSQueue queue, SElemType element) {
if (NULL == queue) {
printf("NULL queue.\n");
exit(1);
}
stack_push(queue->push_stack, element);
}
出队列
SElemType s_queue_de(PSQueue queue) {
if (NULL == queue) {
printf("NULL queue.\n");
exit(1);
}
if (stack_empty(queue->push_stack) && stack_empty(queue->pop_stack) {
printf("no element.\n");
exit(1);
} else if (stack_empty(queue->pop_stack)) {
// 首先要确保pop_stack是空，随后一次性将stack_push注入到stack_pop
while (!stack_empty(queue->push_stack)) {
SElemType data;
stack_pop(queue->stack_push, &data);
stack_push(queue->stack_pop, data);
}
}
SElemType value;
stack_pop(queue->stack_pop, &value); // 始终从stack_pop栈出队列
return value;
}
单向队列队顶: 如s_queue_de出队列类似，但是不要出队列，只返回队列顶部元素
SElemType s_queue_peek(PSQueue queue) {
if (stack_empty(queue->stack_push) && stack_empty(queue->stack_pop)) {
printf("no element.\n”);
exit(1);
} else if (stack_empty(queue->pop_stack)) {
while (!stack_empty(queue->push_stack)) {
SElemType data;
stack_pop(queue->stack_push, &data);
stack_push(queue->stack_pop, data);
}
}
SElemType peek;
stack_pop(queue->stack_pop, &peek);
return peek;
}
队列长度: 由入栈stack_push与出栈stack_pop长度之和
int length_queue(PSQueue queue) {
if (queue == NULL) return 0;
int queue_length = 0;
if (!stack_empty(queue->push_stack)) {
queue_length += queue->push_stack->stackTop;
}
if (!stack_empty(queue->pop_stack)) {
queue_length += queue->pop_stack->stackTop;
}
return queue_length;
}
