C语言实现栈

发布于 2020-04-12  294 次阅读


#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include <windows.h>
#define MAX_SIZE 10000
#define MAX_INT 2147483647

//定义栈的结构体,top为栈顶指针
typedef struct{
    int top;
    int arr[MAX_SIZE];
}Stack;

//创建一个栈
Stack * createStack(){
    Stack * stack = (Stack*)malloc(sizeof(Stack));
    if(stack == NULL)//stack 等于 NULL代表分配空间失败
        return NULL;

    stack->top = -1;
    memset(stack->arr,0,sizeof(int) * MAX_SIZE);
    return stack;
}
//判断栈是否为空
//分配空间失败或者栈顶等于-1
int isempty(Stack * stack){
    if(stack == NULL || stack->top == -1)
        return 1;
    return 0;
}
//弹出栈顶元素
int pop(Stack *stack){
    if(isempty(stack))
        return -1;
    return stack->arr[stack->top--];
}
//入栈
//不管是入栈还是出栈都要判断栈是否为NULL
void push(Stack *stack,int value){
    if(stack == NULL || stack->top >= MAX_SIZE){
        return;
    }
    stack->arr[++stack->top] = value;
    return;
}
int main(){
    int i=0;
    Stack *stack = createStack();
    for(i = 0; i < 10;i++){
        push(stack,i);
    }
    for(i = 0;i < 10;i++){
        printf("%d ",pop(stack));
        Sleep(500);
    }
    free(stack);
}

双栈实现队列

入队操作:直接入栈一
出队操作:

  1. 如果栈一为空,栈二为空,提示空队列
  2. 如果栈一不空,栈二为空,把栈一全部出栈入栈二,弹出栈二顶
  3. 如果栈二不空,弹出栈二顶

和Stack.c放在同一个目录下,并注释掉其main函数

#include<stdio.h>
#include<malloc.h>
#include "Stack.c"

typedef struct queue{
    Stack * stack1;
    Stack * stack2;
}Queue;

Queue* create_queue(){
    Queue * queue = (Queue*)malloc(sizeof(Queue));

    if(queue == NULL){
        printf("Memory is not enough!!!");
        return NULL;
    }

    queue->stack1 = createStack();
    queue->stack2 = createStack();

    return queue;
}

void enterQueueTail(Queue * queue,int value){
    if(queue == NULL)
        return;

    push(queue->stack1, value);
    return;
}

int deleteQueueHead(Queue *queue){
    if(queue == NULL)
        return -1;

    int tmp;

    if(isempty(queue->stack2) && isempty(queue->stack1))
        return -1;

    if(isempty(queue->stack2)){
        while(!isempty(queue->stack1)){
            tmp = pop(queue->stack1);
            push(queue->stack2, tmp);
        }
    }
    return pop(queue->stack2);
}

void freeQueue(Queue *queue){
    if(queue == NULL)
        return;

    if(queue->stack1 != NULL)
        free(queue->stack1);

    if(queue->stack2 != NULL)
        free(queue->stack2);

    free(queue);
    return;
}

main(){
    Queue * queue = create_queue();
    enterQueueTail(queue,1);
    enterQueueTail(queue,2);
    enterQueueTail(queue,3);

    int n = 3;
    while(n--){
        printf("%d ",deleteQueueHead(queue));
    }

    freeQueue(queue);
}

天空没有鸟的痕迹,但我已飞过。