【霍洛维兹数据结构】栈和队列 | 动态循环队列 | 迷宫问题 | 表达式 | 多重栈&多重队列

简介: 【霍洛维兹数据结构】栈和队列 | 动态循环队列 | 迷宫问题 | 表达式 | 多重栈&多重队列

前言:

最近在读霍罗维兹的《数据结构基础》(Fundamentals of Data Structures in C),本篇博客为阅读笔记和知识总结。


Ⅰ. 栈(STACKS)

0x00 概念

栈和队列是更一般的数据类型,有序列表的特例。

栈是一个有序列表,其中插入和删除在称为顶部的一端进行。

0x01  系统工作栈

在开始将栈的ADT之前,我们先来讨论一种特殊的栈。

为了处理函数调用,每当一个函数被调用时,程序会创建一个结构,

被称为 活动记录(activation record)栈帧(stack frame)

当触发函数调用时,无论调用的是其他函数还是自身,函数的栈帧都会存放于系统工作栈中。

正因如此,递归的调用实现可以纳入同样的机制,每次递归调用也只是创建新栈帧罢了,

所以无需特殊对待,但是值得注意的是 —— 递归可能会消耗系统工作栈的大量存储空间,

极端情况下甚至可能会耗尽系统的全部内存!

0x02  栈的抽象数据类型(ADT)

0x03 栈的实现

使用一维数组:

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  概念

队列是一个有序的列表,其插入、删除操作都限定在表的两端。

插入端称为 (对头),删除端称为 (队尾)。

0x01  队列的抽象数据类型(ADT)

0x02  队列的实现

最简单的方案是采用一个一维数组和两个变量,.

指向第一个元素前面的位置, 指向最后一个元素的位置。

这样我们就可以用一个简单的条件 来检查队列是否为空。

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] 视为圆形,

前方索引总是指向从队列中第一个元素开始逆时针方向的一个位置,

的下标指向队列当前的尾部。

The queue is empty iff front == rear

❓ 什么时候队列会满?

为了区分空队列和满队列,我们采用这样的惯例:一个大小为 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 */
  <row, col, dir> = delete from top of stack;
  while (there are more moves from current position) {
    <nextRow, nextCol> = 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 <row, col, dir> to the top of the stack;
      row = nextRow; col = nextCol; dir = north;
    }
  }
}
printf("No path found");

定义一个栈:

#define MAX_STACK_SIZE 100
typedef 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 1
void 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 <= top; i++)
      printf(“ % 2d % 5d”, stack[i].row, stack[i].col);
    printf(" % 2d % 5d\n", row, col);
    printf(" % 2d % 5d\n", EXIT_ROW, EXIT_COL);
  }
  else printf("The maze does not have a path \n");
}

对 path 的分析:

迷宫的大小决定了 path 的计算时间。

由于迷宫中的每个位置被访问的次数不超过一次,算法的最坏情况下的时间复杂度是 ,其中 是迷宫的行数, 是迷宫的列数。

Ⅴ.  表达式(EVALUATION OF EXPRESSIONS)

0x00  表达式的概念

概念:表达式的表示和评估对计算机科学来说是非常有意义的。

((rear+1 == front) || ((rear == MAX_QUEUE_SIZE-1) && ! front))
x = a/b-c+d*e-a*c

表达式中的标记:运算符、操作数和括号。    a + b - c

求x的值:

x = a / b - c + d * e - a * c, 
当 a = 4, b = c = 2, d = e = 3,求x的值

答案是 1 还是 -2.666... 呢?大多数人会认为第一个答案正确,因为遵循先乘除后加减的规则。

但是如果我们就是想要第二个答案的效果,我们该如何修改原式呢?

x = (a / (b - c + d)) * (e - a) * c

在任何编程语言中,都有一个优先级层次,它决定了我们评估运算符的顺序。

括号被用来改变优先级,表达式总是从最内层的括号表达式开始执行。

参见图3.12,关于C语言的优先级层次,参见关联性。

0x02 表达式的写法

尽管 infix (中缀)符号是最常见的表达式书写形式,但它并不是编译器用来评估表达式的方式。

编译器通常使用一种无括号的符号,称为 postfix (后缀)。

0x03 表达式求值

为了求一个后缀表达式,我们对它进行一次从左到右的扫描。

① 将操作数放在堆栈中,直到找到一个运算符。

② 从栈中取出该运算符的正确数目。

③ 执行操作。

④ 将结果放回栈上。

为了方便测试,我们假设表达式只包含二元运算符

并且表达式中的操作数是个位数的整数。

完整的声明:

#define MAX_STACK_SIZE 100 /*maximum stack size*/
#define MAX_EXPR_SIZE 100 /*max size of expression*/
typedef enum {lparen, rparen, plus, minus, times, divide, mod, eos, operand} precedence;
int stack[MAX_STACK_SIZE]; /* global stack */
char expr[MAX_EXPR_SIZE]; /* input string */

[Program 3.13] : 后缀表达式求值函数

int eval(void)
{
  /* evaluate a postfix expression, expr, maintained as a global variable. ‘\0’ is the end of the
  expression. The stack and top of the stack are global variables. getToken is used to
  return the tokentype and the character symbol. Operands are assumed to be single
  character digits */
  precedence token;
  char symbol;
  int op1, op2;
  int n = 0; /* counter for the expression string */
  int top = -1;
  token = getToken(&symbol, &n);
  while (token != eos) {
    if (token == operand)
      push(symbol - ’0’); /* stack insert */
    else {
      /* remove two operands, perform operation, and return result to the stack */
      op2 = pop(); /* stack delete */
      op1 = pop();
      switch (token) {
      case plus: push(op1 + op2); break;
      case minus: push(op1 - op2); break;
      case times: push(op1 * op2); break;
      case divide: push(op1 / op2); break;
      case mod: push(op1 % op2);
      }
    }
    token = getToken(&symbol, &n);
  }
  return pop(&top); /* return result */
}

[Program 3.14] : 从输入串中取token的函数

precedence getToken(char* symbol, int* n)
{
  /* get the next token, symbol is the character representation, which is returned, the
  token is represented by its enumerated value, which is returned in the function name */
  *symbol = expr[(*n)++];
  switch (*symbol) {
  case '(': return lparen;
  case ')': return rparen;
  case '+': return plus;
  case '-': return minus;
  case '/': return divide;
  case '*': return times;
  case '%': return mod;
  case ' ' : return eos;
  default: return operand; /* no error checking, default is operand */
  }
}

0x04 中缀转后缀

以下是中缀表达式转换为后缀表达式的一种算法:

① 为表达式加入所有必须要加的括号。

② 把所有的双目操作符移到对应括号右边。

③ 删除所有括号。

举个例子:

对表达式 进行中缀转后缀。

第一步:加括号,

第二步&第三步:将双目操作符移动到括号右边,然后删除所有括号,

虽然这种算法很适合手算,但在计算机上实现效率不高,因为需要两次扫描操作。第一次扫描插入括号,第二次扫描移动操作符。

请注意,操作量的出现顺序在 infix 和 postfix 中是一样的,因此可以从左向右扫描一遍。

但是,操作数的输出顺序取决于它们的优先级。 由于我们必须先输出优先级较高的运算符,所以我们要保存运算符,直到我们知道它们的正确位置。

我们可以想到用栈存放,但如何按正确的顺序出栈,还有待思考。

方法:

优先级高的运算符必须在优先级低的运算符之前输出。

因此,只要堆栈顶部的运算符的优先级小于传入运算符的优先级,就行。

带括号的表达:

堆叠 "(" 运算符,直到我们碰到 ")" 。

碰到后,我们 "解开" 堆栈,直到我们碰到相应的 "(" ,然后删除 ")"  。

上述分析提示我们,操作符的入栈、出栈顺序取决于优先于优先级。

因此,左括号又两个优先级,分别是 栈内优先级(isp)和 栈外优先级(icp)。

Remove an operator from the stack only if its isp >= icp of the new operator.

precedence stack[MAX_STACK_SIZE];
/* isp and icp arrays -- index is value of precedence
lparen, 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<MAX_STACKS,总是指向紧靠底层元素左边的位置,而top[stack_no],0≤stack_no<MAX_STACKS,总是指向顶部元素。

#define MEMORY_SIZE 100 /* size of memory */
#define MAX_STACKS 10 /* max number of stacks plus 1 */
/* global memory declaration */
element memory[MEMORY_SIZE];
int top[MAX_STACKS];
int boundary[MAX_STACKS];
int n; /* number of stacks entered by the user */
top[0] = boundary[0] = -1;
for (i = 1; i < n; i++)
  top[i] = boundary[i] = (MEMORY_SIZE / n) * i;
boundary[n] = MEMORY_SIZE - 1;


参考资料:

Fundamentals of Data Structures in C

本章完。

相关文章
|
6月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
166 1
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
52 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
8月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
169 11
|
11月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
883 9
|
11月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
224 59
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
335 77
|
8月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
9月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
245 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
141 9