队列的特别实现（两个栈模拟队列）
组合使用两个栈的后进先出可以实现队列的先进先出，简单高效，入队和出队的时间复杂度可以到 O(1)
SQueue.h
#ifndef _SQUEUE_H_#define _SQUEUE_H_typedef void SQueue;SQueue* SQueue_Create();void SQueue_Destroy(SQueue* queue);void SQueue_Clear(SQueue* queue);int SQueue_Append(SQueue* queue, void* item);void* SQueue_Retrieve(SQueue* queue);void* SQueue_Header(SQueue* queue);int SQueue_Length(SQueue* queue);#endif
SQueue.c
#include#include #include "LinkStack.h"#include "SQueue.h"typedef struct _tag_SQueue{ LinkStack* inStack; LinkStack* outStack;} TSQueue;SQueue* SQueue_Create() // O(1){ TSQueue* ret = (TSQueue*)malloc(sizeof(TSQueue)); if( ret != NULL ) { ret->inStack = LinkStack_Create(); ret->outStack = LinkStack_Create(); if( (ret->inStack == NULL) || (ret->outStack == NULL) ) { LinkStack_Destroy(ret->inStack); LinkStack_Destroy(ret->outStack); free(ret); ret = NULL; } } return ret;}void SQueue_Destroy(SQueue* queue) // O(n){ SQueue_Clear(queue); free(queue);}void SQueue_Clear(SQueue* queue) // O(n){ TSQueue* sQueue = (TSQueue*)queue; if( sQueue != NULL ) { LinkStack_Clear(sQueue->inStack); LinkStack_Clear(sQueue->outStack); }}int SQueue_Append(SQueue* queue, void* item) // O(1){ TSQueue* sQueue = (TSQueue*)queue; if( sQueue != NULL ) { LinkStack_Push(sQueue->inStack, item); }}void* SQueue_Retrieve(SQueue* queue) // O(1){ TSQueue* sQueue = (TSQueue*)queue; void* ret = NULL; if( sQueue != NULL ) { if( LinkStack_Size(sQueue->outStack) == 0 ) { while( LinkStack_Size(sQueue->inStack) > 0 ) { LinkStack_Push(sQueue->outStack, LinkStack_Pop(sQueue->inStack)); } } ret = LinkStack_Pop(sQueue->outStack); } return ret;}void* SQueue_Header(SQueue* queue) // O(1){ TSQueue* sQueue = (TSQueue*)queue; void* ret = NULL; if( sQueue != NULL ) { if( LinkStack_Size(sQueue->outStack) == 0 ) { while( LinkStack_Size(sQueue->inStack) > 0 ) { LinkStack_Push(sQueue->outStack, LinkStack_Pop(sQueue->inStack)); } } ret = LinkStack_Top(sQueue->outStack); } return ret;}int SQueue_Length(SQueue* queue) // O(1){ TSQueue* sQueue = (TSQueue*)queue; int ret = -1; if( sQueue != NULL ) { ret = LinkStack_Size(sQueue->inStack) + LinkStack_Size(sQueue->outStack); } return ret;}
main.c
#include#include #include "SQueue.h"/* run this program using the console pauser or add your own getch, system("pause") or input loop */int main(int argc, char *argv[]) { SQueue* queue = SQueue_Create(); int a[10] = { 0}; int i = 0; for(i=0; i<10; i++) { a[i] = i + 1; SQueue_Append(queue, a + i); } printf("Header: %d\n", *(int*)SQueue_Header(queue)); printf("Length: %d\n", SQueue_Length(queue)); for(i=0; i<5; i++) { printf("Retrieve: %d\n", *(int*)SQueue_Retrieve(queue)); } printf("Header: %d\n", *(int*)SQueue_Header(queue)); printf("Length: %d\n", SQueue_Length(queue)); for(i=0; i<10; i++) { a[i] = i + 1; SQueue_Append(queue, a + i); } while( SQueue_Length(queue) > 0 ) { printf("Retrieve: %d\n", *(int*)SQueue_Retrieve(queue)); } SQueue_Destroy(queue); return 0;}
假定有这样一个拥有3个操作的队列：
1. EnQueue(v): 将v加入队列中2. DeQueue(): 使队列中的队首元素删除并返回此元素3. MaxElement(): 返回队列中的最大值请设计一种数据结构和算法，让MaxElement()操作的时间复杂度尽可能的低。