数据结构（功能受限的表-栈队列）

功能受限的表结构

一、栈和队列介绍

• 栈和队列是两种重要的线性结构，从数据结构角度，他们都是线性表，特殊点在于它们的操作被限制，也就是所谓的功能受限，统称功能受限的线性表

• 从数据类型角度，它们也可以是看成处理、管理数据的一种规则

二、栈结构

• 栈（stack）是限定在表尾进行数据的插入、删除等操作的线性表(只允许操作一个端口的数据)

• 表尾称为栈顶，表头称为栈底 ，当没有元素的空表称为空栈，当元素的数量到达栈的容量时称为满栈 ，添加数据到栈顶中的动作称为入栈、压栈，把数据从栈顶中拿出的动作称为出栈、弹栈，正因为这个数据的添加、删除的规则，所以栈中元素满足先进后出，简称FILO表、LIFO

• 栈结构可以具备的功能

  • 创建

  • 销毁

  • 是否满栈

  • 是否空栈

  • 入栈

  • 出栈

  • 查看栈顶元素

  • 查看元素数量

    注意：只有顺序栈才有需要判断栈是否满

1、栈结构的顺序实现

//  设计顺序栈结构
typedef struct ArrayStack
{TYPE* ptr;      //  存储栈元素的内存首地址size_t cap;     //  栈的容量size_t top;     //  栈顶的位置 
}ArrayStack;
​

2、栈结构常考笔试题

• 对一个栈的入栈、出栈序列进行正确性判断

  • 入栈顺序： 1 2 3 4 5

  • 出栈顺序：1 2 3 4 5 正确 1 2 4 3 5 正确 2 1 5 3 4错误 5 4 3 2 1

• 编程题：实现一个函数，判断序列B是否是序列A的出栈顺序

  //  判断出栈顺序是否正确
  bool is_pop(int* a,int* b,size_t len)
  {//  创建一个栈ArrayStack* stack = create_array_stack(len);//  按照a顺序入栈for(int i=0,j=0; i<len; i++){   push_array_stack(stack,a[i]);//  按照b的顺序出栈，一直出到无法出栈为止int val = 0;//  栈非空，且栈顶值等于b中要出栈的值 则出栈while(top_array_stack(stack,&val) && val == b[j]){   pop_array_stack(stack);j++;}}//  判断栈是否空，如果空，则是正确顺序bool flag = false;if(empty_array_stack(stack))flag = true;//  销毁栈destroy_array_stack(stack);return flag;
  }

• 如何让两个长度相同的顺序栈，实现空间利用率最大化？

  • 两个栈顶的增长方向设置成相对的

3、栈结构的链式实现

#define TYPE int
​
typedef struct ListNode
{TYPE data;struct ListNode* next;
}ListNode;
​
ListNode* create_list_node(TYPE data)
{ListNode* node = malloc(sizeof(ListNode));node->data = data;node->next = NULL;return node;
}
​
//  链式栈结构
typedef struct ListStack
{ListNode* top;      // 栈顶指针 指向栈顶节点size_t size;        // 节点数量
}ListStack;
​
//  创建栈
ListStack* create_list_stack(void)
{ListStack* stack = malloc(sizeof(ListStack));//  因为栈不允许随意操作插入、删除操作，因此不需要头节点stack->top = NULL;stack->size = 0;return stack;
}
​
//  栈空
bool empty_list_stack(ListStack* stack)
{}
//  入栈
void push_list_stack(ListStack* stack,TYPE data)
{}
//  出栈
bool pop_list_stack(ListStack* stack)
{}
//  栈顶
TYPE top_list_stack(ListStack* stack)
{}
//  节点数
size_t size_list_stack(ListStack* stack)
{}
//  销毁
void destroy_list_stack(ListStack* stack)
{}
​

4、栈的应用

• 内存管理，例如栈内存，之所以叫栈内存因为它遵循栈的先进后出原则，函数调用、函数参数的传参、定义，先把数据入栈，等结束时，逆序出栈，函数的调用、结束跳转也是遵循栈结构原则

• 特殊的算法：算术表达式的转换(中缀表达式转后缀表达) 、进制转换、迷宫算法

三、队列结构

1、队列介绍

• 与栈结构相似的是，也只允许在端口处进行添加、删除操作，但是有两个端口，一个负责添加数据，称为入队 ，该端口称为队尾，另一个端口只负责删除数据，称为出队，该端口称为队头，属于一种先进先出结构，称为FIFO

2、队列所具备的功能

• 创建队列

• 销毁队列

• 判断队空

• 判断队满 （只有顺序存储时才有）

• 入队

• 出队

• 查看队头元素

• 查看队尾元素

• 队列元素数量

3、队列的链式实现

#define TYPE int
​
typedef struct ListNode
{TYPE data;struct ListNode* next;
}ListNode;
​
ListNode* create_list_node(TYPE data)
{ListNode* node = malloc(sizeof(ListNode));node->data = data;node->next = NULL;return node;
}
​
//  设计链式队列结构
typedef struct ListQueue
{ListNode* front;    //  队头ListNode* rear;     //  队尾size_t size;        //  节点数量
}ListQueue;
​
//  创建
ListQueue* create_list_queue(void)
{ListQueue* queue = malloc(sizeof(ListQueue));queue->front = NULL;queue->rear = NULL;queue->size = 0;return queue;
}
//  队空
bool empty_list_queue(ListQueue* queue)
{return 0 == queue->size;
}
//  入队
void push_list_queue(ListQueue* queue,TYPE data)
{ListNode* node = create_list_node(data);if(empty_list_queue(queue)){queue->front = node;}else{   queue->rear->next = node;queue->rear = node;}queue->size++;
}
​
//  出队
bool pop_list_queue(ListQueue* queue)
{if(empty_list_queue(queue)) return false;ListNode* node = queue->front;queue->front = node->next;free(node);queue->size--;if(0 == queue->size) queue->rear = NULL;return true;
}
​
//  队头
TYPE front_list_queue(ListQueue* queue)
{return queue->front->data;
}
​
//  队尾
TYPE rear_list_queue(ListQueue* queue)
{return queue->rear->data;
}
​
​
//  数量
size_t size_list_queue(ListQueue* queue)
{return queue->size;
}
​
//  销毁
void destroy_list_queue(ListQueue* queue)
{while(pop_list_queue(queue));free(queue);
}
​
​

4、队列的顺序实现

• 顺序队列的队尾下标rear会随着入队而增大rear+1，队头下标front会随着出队增大front+1，因为是顺序结构，就有随着入队和出队的进行，可能超出有效的下标范围，如果不进行处理，那么队列无法重复使用。

• 为了避免这种情况，当队尾、队头下标达到存储空间的末尾时，要想办法让它们回到内存的开头位置，相当于把内存想象成一个环形，从而可以循环使用队列，这样的队列称为循环队列

  • 因此当队尾、队头下标增加时，都要对队列的容量求余

  • rear = (rear+1)%cap

  • front = (front+1)%cap

带计数器版本的循环队列

• 很直接地解决了元素数量的问题

• 可以直接解决队空、队满的判断矛盾问题

• 但是在队列结构中会多增加一个数据项，并且每次入队、出队操作都要对其进行修改

typedef struct ArrayQueue
{TYPE* ptr;      //  存储元素的内存首地址size_t cap;     //  容量size_t cnt;     //  元素个数  计数器int front;      //  队头下标int rear;       //  队尾下标
}ArrayQueue;
​
//  创建
ArrayQueue* create_array_queue(size_t cap)
{ArrayQueue* queue = malloc(sizeof(ArrayQueue));queue->ptr = malloc(sizeof(TYPE)*cap);queue->cap = cap;queue->cnt = 0;queue->front = 0;qeueu->rear = -1;   //  rear指向队尾元素return queue;
}
​
//  销毁
void destroy_array_queue(ArrayQueue* queue){}
​
//  队满
bool full_array_queue(ArrayQueue* queue){}
​
//  队空
bool empty_array_queue(ArrayQueue* queue){}
​
//  入队
bool push_array_queue(ArrayQueue* queue,TYPE data){}
​
//  出队
bool pop_array_queue(ArrayQueue* queue){}
​
//  队头
TYPE front_array_queue(ArrayQueue* queue){}
//  队尾
TYPE rear_array_queue(ArrayQueue* queue){}
//  数量
size_t size_array_queue(ArrayQueue* queue){}   

不带计数器的版本