共计 2239 个字符,预计需要花费 6 分钟才能阅读完成。
队列栈与一般线性表区别
线性表抽象是存储具有先后顺序元素数据的结构,支持任意位置的插入,删除操作。队列和栈限制插入删除操作,队列只能从尾部插入,首部取出 (删除),既先入先出; 栈限制插入和取出操作只能在尾部进行,既先入后出。
实现方式
队列和栈同一般线性表相同,可用数组和链式结构体实现。由于限制了插入和取出的位置,没有频繁的中间元素操作,数组实现比链式实现效率更高。对应缺点为初始化时要定义数组大小,无法动态分配大小。
代码实现
栈
struct stack;
typedef struct stack sStack;
typedef sStack *pStack;
#define EmptyTOS -1;
struct stack {
int capacity;
int topOfStack;
long long int *data;
};
pStack elrInitStackInt(int capaticy) {
pStack s;
s = malloc(sizeof(sStack));
if (s == NULL) {printf("out of space!");
}
s->data = malloc(sizeof(long long int) * capaticy);
if (s->data == NULL) {printf("out of space!");
}
s->capacity = capaticy;
elrMakeStackEmpty(s);
return s;
}
void elrFreeStackInt(pStack stack) {if (stack != NULL) {free(stack->data);
free(stack);
}
}
int elrIsStackEmpty(pStack stack) {return stack->topOfStack == EmptyTOS;}
int elrIsStackFull(pStack stack) {return stack->topOfStack == (stack->capacity - 1);
}
void elrMakeStackEmpty(pStack stack) {stack->topOfStack = EmptyTOS;}
void elrPushStackInt(pStack stack, long long int data) {if (elrIsStackFull(stack)) {printf("full stack");
} else {stack->data[++stack->topOfStack] = data;
}
}
long long int elrPopStackInt(pStack stack) {if (elrIsStackEmpty(stack)) {printf("empty stack");
} else {return stack->data[--stack->topOfStack];
}
}
队列
struct queue;
typedef struct queue sQueue;
typedef sQueue *pQueue;
struct queue {
int capacity;
int front;
int rear;
int size;
long long int *data;
};
pQueue elrInitQueueInt(int capaticy) {
pQueue s;
s = malloc(sizeof(sQueue));
if (s == NULL) {printf("out of space!");
}
s->data = malloc(sizeof(long long int) * capaticy);
if (s->data == NULL) {printf("out of space!");
}
s->capacity = capaticy;
elrMakeQueueEmpty(s);
return s;
}
void elrFreeQueueInt(pQueue queue) {if (queue != NULL) {free(queue->data);
free(queue);
}
}
int elrIsQueueEmpty(pQueue queue) {return queue->size == 0;}
int elrIsQueueFull(pQueue queue) {return queue->size == queue->capacity;}
void elrMakeQueueEmpty(pQueue queue) {
queue->size = 0;
queue->front = 1;
queue->rear = 0;
}
int succ(pQueue queue, int value) {if (++value == queue->capacity) {value = 0;}
return value;
}
void elrEnqueuekInt(pQueue queue, long long int data) {if (elrIsQueueFull(queue)) {printf("full queue");
} else {
queue->size++;
queue->rear = succ(queue, queue->rear);
queue->data[queue->rear] = data;
}
}
long long int elrDequeueInt(pQueue queue) {if (elrIsQueueEmpty(queue)) {printf("empty queue");
} else {
queue->size--;
int data = queue->data[queue->front];
queue->front = succ(queue, queue->front);
}
}
正文完