【霍洛维兹数据结构】栈和队列 |
您所在的位置：网站首页 › 0x00和0x01 › 【霍洛维兹数据结构】栈和队列 |
【霍洛维兹数据结构】栈和队列
|
前言： 最近在读霍罗维兹的《数据结构基础》（Fundamentals of Data Structures in C），本篇博客为阅读笔记和知识总结。 目录 Ⅰ. 栈（STACKS） 0x00 概念 0x01 系统工作栈 0x02 栈的抽象数据类型（ADT） 0x03 栈的实现 0x04 动态栈 Ⅱ. 队列（QUEUE） 0x00 概念 0x01 队列的抽象数据类型（ADT） 0x02 队列的实现 0x03 例: 任务调度 Ⅲ. 动态循环队列 0x00 概念 0x01 实现 Ⅳ. 迷宫问题 0x00 解释 Ⅴ. 表达式（EVALUATION OF EXPRESSIONS） 0x00 表达式的概念 0x02 表达式的写法 0x03 表达式求值 0x04 中缀转后缀 Ⅵ. 多重栈与多重队列 Ⅰ. 栈（STACKS）0x00 概念栈和队列是更一般的数据类型，有序列表的特例。 栈是一个有序列表，其中插入和删除在称为顶部的一端进行。
在开始将栈的ADT之前，我们先来讨论一种特殊的栈。 为了处理函数调用，每当一个函数被调用时，程序会创建一个结构， 被称为 活动记录（activation record）或 栈帧（stack frame）。
当触发函数调用时，无论调用的是其他函数还是自身，函数的栈帧都会存放于系统工作栈中。 正因如此，递归的调用实现可以纳入同样的机制，每次递归调用也只是创建新栈帧罢了， 所以无需特殊对待，但是值得注意的是 —— 递归可能会消耗系统工作栈的大量存储空间， 极端情况下甚至可能会耗尽系统的全部内存！ 0x02 栈的抽象数据类型（ADT）
使用一维数组： Stack CreateS(maxStackSize) :: =#define MAX_STACK_SIZE 100 /* maximum stack size */typedef struct { int key; /* other fields */} element;element stack[MAX_STACK_SIZE];int top = -1;Boolean IsEmpty(stack) :: = top < 0;Boolean IsFull(stack) :: = top >= MAX_STACK_SIZE - 1;[Program 3.1] 入栈函数 void push(element item){ /* add an item to the global stack */ if (top >= MAX_STACK_SIZE - 1) stackFull(); stack[++top] = item;}[Program 3.2] 出栈函数 element pop(){ /* return the top element from the stack */ if (top == -1) return stackEmpty(); /* return an error key */ return stack[top--];}0x04 动态栈Stack CreateS() :: =typedef struct { int key; /* other fields */} element;element* stack;MALLOC(stack, sizeof(*stack));int capacity = 1;int top = -1;Boolean IsEmpty(stack) :: = top < 0;Boolean IsFull(stack) :: = top >= capacity - 1;void stackFull(){ REALLOC(stack, 2 * capacity * sizeof(*stack)); capacity *= 2;}stackFull 函数有了扩容的功能，我们一般可以选择扩二倍。 Ⅱ. 队列（QUEUE）0x00 概念队列是一个有序的列表，其插入、删除操作都限定在表的两端。 插入端称为
（对头），删除端称为
（队尾）。
最简单的方案是采用一个一维数组和两个变量，
和
.
指向第一个元素前面的位置，
指向最后一个元素的位置。这样我们就可以用一个简单的条件
来检查队列是否为空。 Queue CreateQ(maxQueueSize) :: =#define MAX_QUEUE_SIZE 100 /* maximum queue size */typedef struct { int key; /* other fields */} element;element queue[MAX_QUEUE_SIZE];int rear = -1;int front = -1;Boolean IsEmptyQ(queue) :: = front == rear;Boolean IsFullQ(queue) :: = rear == MAX_QUEUE_SIZE - 1;
[Program 3.5] 入队 void addq(element item){ /* add an item to the queue */ if (rear == MAX_QUEUE_SIZE - 1) queueFull(); queue[++rear] = item;}[Program 3.6] 出队 element deleteq(){ /* remove element at the front of the queue */ if (front == rear) return queueEmpty(); /* return an error key */ return queue[++front];}0x03 例: 任务调度操作系统中的一个工作队列， 如果操作系统不使用优先级，那么作业将按照进入系统的顺序进行处理 顺序队列的插入和删除：
对 queueFull 的处理： 随着工作进入和离开系统，队列逐渐向右移动。 最终，
下标等于 MAX_QUEUE_SIZE - 1，表明队列已满。在这种情况下，queueFull 应该把整个队列向左移动，这样第一个元素还是在queue[0]，
是 -1。
也会被重新计算。 移动一个数组是非常耗时的。 更有效地执行方式： 通过将数组queue[MAX_QUEUE_SIZE] 视为圆形， 前方索引总是指向从队列中第一个元素开始逆时针方向的一个位置，
的下标指向队列当前的尾部。
❓ 什么时候队列会满？ 为了区分空队列和满队列，我们采用这样的惯例：一个大小为 MAX_QUEUE_SIZE 的循环队列将被允许最多容纳 MAX_QUEUE_SIZE-1 个元素。
为了实现循环队列的 addq 和 deleteq，我们必须保证循环旋转的发生。 使用模运算符： rear = (rear + 1) % MAX_QUEUE_SIZE;front = (front + 1) % MAX_QUEUE_SIZE;[Program 3.7] : 循环队列入队函数 addq void addq(element item){ /* add an item to the queue */ rear = (rear + 1) % MAX_QUEUE_SIZE; if (front == rear) queueFull(); /* print error and exit */ queue[rear] = item;}[Program 3.8] : 循环队列出队函数 deleteq element deleteq(){ /* remove element at the front of the queue */ if (front == rear) return queueEmpty(); /* return an error key */ front = (front + 1) % MAX_QUEUE_SIZE; return queue[front];}Ⅲ. 动态循环队列（CIRCULAR QUEUES USING DYNAMICALLY ALLOCATED ARRAYS） 0x00 概念要向一个完整的队列添加一个元素，我们须先使用 realloc 等函数增加这个数组的大小。 与动态分配的堆栈一样，我们采用数组扩容的手段去实现。 0x01 实现队列扩容 让
为数组
中的位置数。(1) 申请新数组 newQueue，在现有容量
上扩2倍。 (2)把数组中的第二段数据（从 queue[front + 1] 到 queue[capacity - 1] ）赋值道 newQueue 的起始位置（0）之后。 (3) 把数组中的第一段数据（从 queue[0] 到 queue[rear] ）复制到 newQueue 的位置之后（即 capacity - front -1 之后）。
[Program 3.9] : 循环队列的插入 void addq(element item){ /* add an item to the queue */ rear = (rear + 1) % capacity; if (front == rear) queueFull(); /* double capacity */ queue[rear] = item;}[Program 3.10] : 队列扩容 void queueFull(){ /* allcoate an array with twice the capacity */ element* newQueue; MALLOC(newQueue, 2 * capacity * sizeof(*queue)); /* copy from queue to newQueue */ int start = (front + 1) % capacity; if (start < 2) /* no wrap around */ else { /* queue wraps around */ copy(queue + start, queue + capacity, newQueue); copy(queue, queue + rear + 1, newQueue + capacity - start); } /* switch to newQueue */ front = 2 * capacity - 1; rear = capacity – 2; capacity *= 2; free(queue) queue = newQueue;}Ⅳ. 迷宫问题0x00 解释我们拿二维数组表示，其中 0 代表开放路径，1 代表障碍：
为了防止检查边界条件，我们用一个 1 的边界来包围迷宫。 因此，一个 m×p 的迷宫将需要一个 (m+2) × (p+2) 大小的数组。 入口设置在位置 [1][1]，出口设置在 [m][p] 。 💬 预先定义一个数组中可能的移动方向，
（8个邻域） 在迷宫中搜索，某一时刻也许会有多种选择，我们并不确定究竟哪个方向好， 因此我们只能先把当前位置保存起来，这有点类似于游戏里的存档功能，然后任选一个方向去走， 发现是死路，我们就回到 "存档点" ，继续试另外的路，我们可以顺时针一个个试探其他方向。 为了避免再次回到我们已经走过的死路，我们可以用数组 mark 来标记一下， 我们先将 mark 初始化为全0的数组，然后访问 maze[row][col] 之后，mark[row][cow] 置为1。 typedef struct { short int vert; short int horiz;} offsets;offsets move[8]; /*array of moves for each direction*/
用一个栈存储从入口到当前位置的路径上的位置。 [Program 3.11] : 第一个迷宫程序 initialize a stack to the maze's entrance coordinates and direction to north;while (stack is not empty) { /* move to position at the top of stack */ = delete from top of stack; while (there are more moves from current position) { = coordinates of next move; dir = direction of move; if ((nextRow == EXIT_ROW) && (nextCol == EXIT_COL)) success; if ((maze[nextRow][nextCol] == 0) && (mark[nextRow][nextCol] == 0)) { /* legal move and haven't been there */ mark[nextRow][nextCol] = 1; /* save current position and direction */ add to the top of the stack; row = nextRow; col = nextCol; dir = north; } }}printf("No path found");定义一个栈： #define MAX_STACK_SIZE 100typedef struct { short int row; short int col; short int dir;} element;element stack[MAX_STACK_SIZE];我们需要为堆栈大小敲定一个合理的边界。
（路径很长的小迷宫） [Program 3.12] : 迷宫搜索函数 我们设定数组，maze，mark，move，stack，以及常量 EXIT_ROW，EXIT_COL，TRUE，FALSE，以及变量 top 都是全局变量。 #define _CRT_SECURE_NO_WARNINGS 1void path(void){ /* output a path through the maze if such a path exists */ int i, row, col, nextRow, nextCol, dir, found = FALSE; element position; mark[1][1] = 1; top = 0; stack[0].row = 1; stack[0].col = 1; stack[0].dir = 1; while (top > -1 && !found) { position = pop(); row = position.row; col = position.col, dir = position.dir; while (dir < 8 && !found) { /* move in direction dir */ nextRow = row + move[dir].vert; nextCol = col + move[dir].horiz; if (nextRow == EXIT_ROW && nextCol == EXIT_COL) found = TRUE; else if (!maze[nextRow][nextCol] && !mark[nextRow][nextCol]) { mark[nextRow][nextCol] = 1; position.row = row; position.col = col; position.dir = ++dir; push(position); row = nextRow; col = nextCol; dir = 0; } else ++dir; } } if (found) { printf("The path is : \n"); printf("row col \n"); for (i = 0; i = icp of the new operator. precedence stack[MAX_STACK_SIZE];/* isp and icp arrays -- index is value of precedencelparen, rparen, plus, minus, times, divide, mod, eos */static int isp[] = {0, 19, 12, 12, 13, 13, 13, 0};static int icp[] = {20, 19, 12, 12, 13, 13, 13, 0};[program 3.15] : 中缀表达式转后缀表达式 void postfix(void){ /* output the postfix of the expression. The expression string, stack, and the top are global */ char symbol; int n = 0; int top = 0; /* place eos on stack */ stack[0] = eos; for (token = getToken(&symbol, &n); token != eos; token = getToken(&symbol, &n)) { if (token == operand) printf(“ % c”, symbol); else (token == rparan) { /* unstack tokens until left paranthesis */ while (stack[top] != lparen) printToken(pop(&top)); pop(); /* discard the left paranthesis */ } else { /* remove and print symbols whose isp is greater than or equal to the current token’s icp */ while (isp[stack[top]] >= icp[token]) printToken(pop()); push(token); } } while ((token = pop()) != eos) printToken(token); printf(“\n”);}分析 postfix： 令 n 是表达式中 token 的个数， 取得 token 与输出 token 的时间都是
两条 while 语句的总时间都是
入栈和出栈的次数关于
都是线性的，因此，函数 postfix 的复杂度为
。 Ⅵ. 多重栈与多重队列实现多个堆栈（队列），将这些栈按顺序映射到一个数组中。 即用数值 memory [MEMORY_SIZE] 存储数据元素。 如果我们只有两个栈需要表示：
两个栈以上： 假设有n个堆栈，最初我们将可用的内存分为n个段。让 stack_no 指 n个堆栈中的一个堆栈编号。 底层元素，boundary[stack_no]，0≤stack_no |
【本文地址】