数据结构：栈、队列（顺序存储结构）-C&Java实现

• 栈（顺序存储结构）
• • Stack.c
  • DataStruct/Stack.java
• 队列（顺序存储结构）
• • Queue.c
  • DataStruct/Queue.java

#include 
#include 

#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 100
#define INCREMENT_SIZE 10

typedef unsigned short Bool;
typedef int Elemtype;


typedef struct
{
    Elemtype *base;
    int top;
    int stackSize;
} Stack;


Bool push(Stack stack, Elemtype elem)
{
    // 如果栈顶指针大于栈大小，先将栈扩容
    if (stack.top > stack.stackSize)
    {
        Elemtype *newbase = (Elemtype *)realloc(stack.base, sizeof(Elemtype) * (stack.stackSize + INCREMENT_SIZE));
        if (!newbase)
        {
            printf("重新分配内存失败！n");
            return FALSE;
        }
        stack.base = newbase;
    }
    // 推入元素
    stack.base[stack.top] = elem;
    stack.top += 1;
    return TRUE;
}


Bool pop(Stack stack, Elemtype *elem)
{
    // 如果栈为空
    if (stack.top == 0)
    {
        printf("栈为空！");
        return FALSE;
    }
    stack.top -= 1;
    // 指针有效才赋值
    if (elem)
    {
        *elem = stack.base[stack.top]
    }
    return TRUE;
}


Stack *createStack()
{
    Stack *stack = (Stack *)calloc(1, sizeof(Stack));
    if (!stack)
    {
        printf("内存分配失败！");
        return NULL;
    }
    Elemtype *newbase = (Elemtype *)malloc(sizeof(Elemtype) * STACK_INIT_SIZE);
    if (!newbase)
    {
        printf("内存分配失败！");
        free(stack);
        return NULL;
    }
    stack->base = newbase;
    stack->stackSize = STACK_INIT_SIZE;
    return stack;
}

package DataStruct;

import java.lang.reflect.Array;
import java.util.Arrays;


public class Stack {
    private static final int STACK_INIT_SIZE = 100;
    private static final int INCREMENT_SIZE = 10;

    private T[] base;
    private int top;
    private int size;

    
    @SuppressWarnings("unchecked")
    public Stack(Class type) {
        base = (T[]) Array.newInstance(type, STACK_INIT_SIZE);
        top = 0;
        size = STACK_INIT_SIZE;
    }

    
    public void push(T elem) {
        // 如果栈满则扩容
        if (top > size) {
            base = Arrays.copyOf(base, size + INCREMENT_SIZE);
        }
        // 推入元素
        base[top] = elem;
        top += 1;
    }

    
    public T pop() {
        // 如果栈空
        if (top <= 0) {
            throw new IllegalStateException("栈为空！");
        }
        top -= 1;
        return base[top];
    }
}

#include 
#include 

#define TRUE 1
#define FALSE 0
#define MAX_SIZE 100

typedef unsigned short Bool;
typedef int Elemtype;


typedef struct
{
    Elemtype *data;
    int front;
    int rear;
    int queueSize;
} Queue;


Bool addFirst(Queue *queue, Elemtype elem)
{
    if ((queue->rear + 1) % queue->queueSize == queue->queueSize)
    {
        printf("队列已满！");
        return FALSE;
    }
    int idx = queue->front - 1;
    queue->front = idx < 0 ? queue->queueSize - 1 : idx;
    queue->data[queue->front] = elem;
    return TRUE;
}


Bool addLast(Queue *queue, Elemtype elem)
{
    if ((queue->rear + 1) % queue->queueSize == queue->queueSize)
    {
        printf("队列已满！");
        return FALSE;
    }
    int idx = (queue->rear + 1) % queue->queueSize;
    queue->rear = idx;
    queue->data[idx] = elem;
    return TRUE;
}


Bool removeFirst(Queue *queue, Elemtype *elem)
{
    if (queue->front == queue->rear)
    {
        printf("队列为空！");
        return FALSE;
    }
    if (elem)
    {
        *elem = queue->data[queue->front];
    }
    queue->front = (queue->front + 1) % queue->queueSize;
    return TRUE;
}


Bool removeLast(Queue *queue, Elemtype *elem)
{
    if (queue->front == queue->rear)
    {
        printf("队列为空！");
        return FALSE;
    }
    if (elem)
    {
        *elem = queue->data[queue->rear];
    }
    int idx = queue->rear - 1;
    queue->rear = idx < 0 ? queue->queueSize - 1 : idx;
    return TRUE;
}


int getLength(Queue *queue)
{
    if (queue->front <= queue->rear)
    {
        return queue->rear - queue->front;
    }
    else
    {
        return queue->rear + queue->queueSize - queue->front - 1;
    }
}


Queue *createQueue()
{
    Queue *queue = (Queue *)calloc(1, sizeof(Queue));
    if (!queue)
    {
        printf("内存分配失败！");
        return NULL;
    }
    Elemtype *newData = (Elemtype *)malloc(sizeof(Elemtype) * MAX_SIZE);
    if (!newData)
    {
        printf("内存分配失败！");
        free(queue);
        return NULL;
    }
    queue->data = newData;
    queue->queueSize = MAX_SIZE;
    return queue;
}

package DataStruct;

import java.lang.reflect.Array;


public class Queue {
    private static final int QUEUE_INIT_SIZE = 100;
    // private static final int INCREMENT_SIZE = 10;

    private T[] data;
    private int front;
    private int rear;
    private int queueSize;

    
    @SuppressWarnings("unchecked")
    public Queue(Class type) {
        data = (T[]) Array.newInstance(type, QUEUE_INIT_SIZE);
        front = 0;
        rear = 0;
        queueSize = QUEUE_INIT_SIZE;
    }

    
    public boolean addFirst(T elem) {
        if ((rear + 1) % queueSize == queueSize) {
            System.out.println("队列已满！");
            return false;
        }
        int idx = front - 1;
        front = idx < 0 ? queueSize - 1 : idx;
        data[front] = elem;
        return true;
    }

    
    public boolean addLast(T elem) {
        if ((rear + 1) % queueSize == queueSize) {
            System.out.println("队列已满！");
            return false;
        }
        int idx = (rear + 1) % queueSize;
        rear = idx;
        data[idx] = elem;
        return true;
    }

    
    public T removeFirst() {
        if (front == rear) {
            throw new IllegalStateException("队列为空！");
        }

        T elem = data[front];

        front = (front + 1) % queueSize;
        return elem;
    }

    
    public T removeLast() {
        if (front == rear) {
            throw new IllegalStateException("队列为空！");
        }

        T elem = data[rear];

        int idx = rear - 1;
        rear = idx < 0 ? queueSize - 1 : idx;
        return elem;
    }

    
    int getLength() {
        if (front <= rear) {
            return rear - front;
        } else {
            return rear + queueSize - front - 1;
        }
    }
}