数据结构03-队列和栈
2018-01-22 本文已影响11人
sanpintian
3：队列（QUEUE）
3.1：队列的定义和性质
队列：只允许前端（front，队首）进行删除操作，而在后端（rear，队尾）进行插入操作的数据结构。
从队首删除队尾插入的性质，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的数据结构。
队列最典型的性质：先进先出(FIFO)。
如：操作系统的进程调度就是用的队列。
3.2：队列的结构和常见操作
3.2.1：队列结构：尾部插入，前端删除
image.png
队列底层数据结构可以使用链表或者数组。
基于数组的队列，在不断的插入元素和删除元素的时候，数组的内存空间将会不断的向上滑动（如上图中间部分所示），这在实际应用过程中肯定是不好的，因此假如数组的长度为MAX，通过用rear=(rear+1)%MAX和front=(front+1)%MAX来移动数组的前端和尾端，可以限制它们在数组的当前空间，这样就构成了一个循环队列（如上图右边部分所示）。
3.2.1：队列基本操作
队列包含创建，入队，出队，队空判断，对满判断等操作。
- 创建-int CreateQue();用于创建一个队列，一般需要初始化队列的前端和后端指针。
- 入队-int EnQueue(int e);将特定的元素e从队列的尾部插入。
- 出队-int DeQueue(int *e);获取队列头部的数据并从队列删除。
- 判断队列满-int IsQueueFull();判断队列是否已满，如果队列满了就不能再从尾部插入数据了，只对基于数组的队列有效。
- 判断队列空-int IsQueueEmpty();判断队列是否为空，如果队列为空，就不能从队首删除数据了，在构造基于链表的队列的 时候，队列为空，插入第一个元素的时候，也需要特别的处理。
3.3：基于链表的队列实现
基于链表的数组没有满的时候
如图：
image.png
链表结点的存储结构如下：
typedef struct _node {
int value;
struct _node *next;
}node, *pnode;
//其中值的部分存放的是一个整数data，这部分数据可以自己再定义，增减。
node *front = NULL; //队头指针，由于是全局变量，请注意多线程安全
node *rear = NULL; //队尾指针，由于是全局变量，请注意多线程安全
//创建
int creatQueue() {
front = rear = NULL;//将front和rear置为NULL
return 1;
}
//判断队列是否为空
int isQueueEmpty() {
if(front==NULL&&rear==NULL) {//front和rear等于NULL是队列为空的标志
return 1;
}
return 0;
}
//入队
int enQueue(int value) {
node *p = (node *)malloc(sizeof(node));
if (!p) {
return -1;
}
memset(p, 0, sizeof(node));
p->value = value;
p->next = NULL;
if(isQueueEmpty) {//队列为空，直接将rear和front指向该结点
rear = front = p;
return 1;
} else {
rear->next = p;
p->next = NULL;
rear = p;
return 1;
}
}
//出队
int deQueue(int *pValue) {//必须传指针，否则出队的值无法获取
if(pValue == NULL) {//传入空值
return -1;
}
if(isQueueEmpty) {//空链表
return -1;
}
if(rear==front && rear!=NULL && front!=NULL) {//一个节点时
*e = front->value;
free(front);
front = rear = NULL;
return 1;
}
*e = front->value;
node *pfront = front;
front = front->next;
free(pfront);
return 1;
}
//遍历队列
void traverseQueue() {
while(!isQueueEmpty()) {
int value;
deQueue(&value);
printf("%d ",value);
}
printf("\n");
}
//队列测试代码
int main(int argc, int* argv[]) {
int value;
createQueue();
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
deQueue(&value);
printf("value:%d\n", value);
enQueue(5);
enQueue(6);
deQueue(&value);
printf("value:%d\n", value);
deQueue(&value);
printf("value:%d\n", value);
traverseQueue();
return 0;
}
3.4：基于数组的队列实现
基于数组的循环队列，有3种形态：
- 队列为空:front等于rear；
- 正常形态:front指向队首元素，rear指向队尾元素的下一个位置；
- 队列满：这个时候，队尾指针指向队首指针的前一个位置（空位）。
image.png
#define MAXSIZE 100//数组的元素个数
int arrayQueue[MAXSIZE]={0};//队列的底层数据结构，数组，支持100个元素
int rear = 0;//队列后端，插入的位置
int front = 0;//队列前端，删除的位置
//创建
int creatArrayQueue() {
front = rear = 0;//将front和rear置为0
return 1;
}
//判断队列是否为空
int isArrayQueueEmpty() {//front等于rear，队列即为空
if (front == rear) {
return 1;
}
return 0;
}
//判断队列是否为满
int isArrayQueueFull() {
if (front == (rear+1)% MAXSIZE) {
return 1;
}
return 0;
}
//入队
int enArrayQueue(int value) {
if(isArrayQueueFull()) {
return -1;
}
arrayQueue[rear] = value;
rear = (rear+1)%MAXSIZE;
return 1;
}
//出队
int duArrayQueue(int *pValue) {
if(isArrayQueueEmpty()) {
return -1;
}
if(pValue == NULL) {
turn -1;
}
*pValue = arrayQueue[front];
front = (front+1)%MAXSIZE;
return 1;
}
//遍历
int traverseQueue() {
while(!isQueueEmpty()) {
int value;
if(deQueue(&value)) {
printf("%d", v);
}
}
printf("\n");
return 1;
}
4：栈(STACK)
4.1：栈的定义和性质
栈：允许在同一端进行插入和删除操作的数据结构。
- 栈顶(top)：被允许进行插入和删除操作的一端；栈顶浮动；
- 栈底(bottom)：栈底固定
- 空栈：栈中元素个数为零时为空栈
- 进栈(PUSH)：插入元素
- 出栈(POP)：删除元素
由于栈规定只能在同一端进行插入和删除，因此栈的一个典型特点就是后进先出。
栈.png
4.2：栈的结构和常见操作
4.2.1：栈的结构
栈的底层数据结构包含链表与数组。可以通过链表或者数组来构造栈。
基于链表的栈.png
基于数组的栈.png
4.3：栈的基本操作
1. 栈的创建:int createStack();负责初始化栈的基本结构，比如栈顶指针的初始化。
2.入栈:int push(int data);将数据从栈顶插入
3.出栈:int pop(int *data);获取栈顶数据，并将数据从栈顶删除
4.栈空判断:int isStackEmpty();判断栈是否为空，栈为空，就不能再pop了。
5.栈满:int isStackFull();判断栈是否为满，栈满就不能再插入数据了。只有基于数组的栈，才需要判断栈是否已满。
4.4：基于链表的栈实现
//先定义栈的结点结构：
typedef struct _node {
int value;
struct _node *next;
} node, *pnode;
//栈顶指针初始化：
node *top = NULL;
//创建栈：
int createStack() {
top = NULL;
return 1;
}
//判断栈是否为空：
int isStackEmpty() {
return top==NULL?1:0;//top为NULL的时候，栈为空
}
//入栈：
int push(int value) {
node *p = (node *)malloc(sizeof(node));
if(p==NULL) {
return -1;
}
memset(p,0,sizeof(node));
p->value = value;
p->next = NULL;
//栈为空的时候，插入的是第一个结点
if(isStackEmpty()) {
top = p;
return 1;
}
//栈非空的时候，插入一个结点
p->next = top;
top = p;
return 1;
}
//出栈
int pop(int *e) {
if (isStackEmpty()) {
return -1;
}
if(e == NULL) {
return -1;
}
//当栈只有一个结点的时候：
if(top->next == NULL) {
*e = top->value;
free(top);
top = NULL;
return 1;
}
//当栈中存放不止一个元素的时候
*e = top->value;
node *p = top;
top = top->next;
free(p);
return 1;
}
//栈的遍历：
void traverseStack() {
while(!IsStackEmpty()) {
int val;
pop(&val);
printf("%d ", val);
}
printf("\n");
}
//接口测试：
int _tmain(int argc, _TCHAR* argv[]) {
createStack();
for(int i=0; i<10; i++) {
push(i+1);
}
int val;
pop(&val);
printf("val:%d\n", val);
traverseStack();
return 0;
}
4.5：基于数组的栈实现
image.png
#define MAXSIZE 1000//栈中数组容纳的元素个数
int stackArray[MAXSIZE]={0};//栈的底层数据结构：数组stack
int top=0;//栈顶
//创建栈
int createStack() {
top = 0;//将top置零
return 1;
}
//判断栈是否满
int isStackFull() {
return top==MAXSIZE?1:0;
}
//判断栈是否空
int isStackEmpty() {
return top==0?1:0;
}
//入栈：
int push(int val) {
if(isStackFull()) {
return -1;
}
stackArray[top++]=val;
return 1;
}
//出栈：
int pop(int *e) {
if(isStackEmpty()) {
return -1;
}
if(e==NULL) {
return -1;
}
*e = stackArray[--top];
return 1;
}
//栈的遍历：
void traverseStack() {
while(!isStackEmpty()) {
int val;
pop(&val);
printf("%d ",val);
}
printf("\n");
}
//接口测试：
int _tmain(int argc, _TCHAR* argv[]) {
createStack();
for(int i=0;i<500;i++) {
push(i+1);
}
int val;
pop(&val);
printf("val:%d\n", val);
traverseStack();
return 0;
}
