[数据结构]栈和队列

第三章栈和队列

学习提要：

1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。

2.熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，应特别

注意栈满和栈空的条件以及它们的描述方法。

3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。

重难点内容：

顺序栈的相关操作、循环队列的判空判满

3.1 栈（stack）

3.1.1 栈的类型定义

栈的定义和特点

定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈。

特点：先进后出（FILO）或后进先出（LIFO）

栈的类型定义

ADT Stack {

数据对象：

D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }

数据关系：

R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }

约定an 端为栈顶，a1 端为栈底。

基本操作：

} ADT Stack

InitStack(&S)

DestroyStack(&S)

StackLength(S)

StackEmpty(s)

GetTop(S, &e)

ClearStack(&S)

Push(&S, e)

Pop(&S, &e)

StackTravers(S, visit())

3.1.2 栈的表示和实现

顺序栈

类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针

//----- 栈的顺序存储表示 -----

#define STACK_INIT_SIZE 100;

#define STACKINCREMENT 10;

typedef struct {

SElemType *base;

SElemType *top;

int stacksize;

} SqStack;

实现：一维数组s[M]

Status InitStack (SqStack &S)

{// 构造一个空栈S

S.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType));

if (!S.base) exit (OVERFLOW); //存储分配失败

S.top = S.base;

S.stacksize = STACK_INIT_SIZE;

return OK;

}

Status Push (SqStack &S, SElemType e) {

if (S.top - S.base >= S.stacksize) {//栈满，追加存储空间

S.base = (SElemType *) realloc ( S.base,

(S.stacksize + STACKINCREMENT) *

sizeof (SElemType));

if (!S.base) exit (OVERFLOW); //存储分配失败

S.top = S.base + S.stacksize;

S.stacksize += STACKINCREMENT;

}

*S.top++ = e;

return OK;

}

Status Pop (SqStack &S, SElemType &e) {

// 若栈不空，则删除S的栈顶元素，

// 用e返回其值，并返回OK；

// 否则返回ERROR

if (S.top == S.base) return ERROR;

e = *--S.top;

return OK;

}

在一个程序中同时使用两个栈

链栈

栈的链式存储结构。栈顶指针就是链表的头指针。

注意: 链栈中指针的方向

入栈操作

p->next=top ; top=p

出栈操作

q=top ; top=top->next

3.2 栈的应用

3.2.1 数制转换

十进制N和其他d进制数的转换原理:

N=( N div d )*d + N mod d

其中：div为整除运算，mod为求余运算

例如： (1348)10=(2504)8，其运算过程如下：

N N div 8 N mod 8

1348 168 4

168 21 0

21 2 5

2 0 2

void conversion( ) {

initstack(S);

scanf (“%d”,N);

while(N){

push(S，N%8);

N=N/8;

}

while(! Stackempty(s)){

pop(S,e);

printf(“%d”,e);

}

}//conversion

3.3.2 括号匹配的检验

假设在表达式中（［］（））或［（［］［］）］等为正确的格式，

［（］）或（［（））或（（）］)均为不正确的格式。

则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。

例如：考虑下列括号序列：

[ ( [ ] [ ] ) ]

1 2 3 4 5 6 7 8

分析可能出现的不匹配的情况:

到来的右括弧并非是所“期待”的；

算法的设计思想：

1）凡出现左括弧，则进栈；

2）凡出现右括弧，首先检查栈是否空，若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈” ，否则表明不匹配。

3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。

3.2.3 行编辑程序问题

设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。

假设从终端接受了这样两行字符：

whli##ilr#e（s#*s)

outcha@putchar(*s=#++);

则实际有效的是下列两行：

while (*s)

putchar(*s++);

while (ch != EOF) { //EOF为全文结束符

while (ch != EOF && ch != '\n') {

switch (ch) {

case '#' : Pop(S, c); break;

case '@': ClearStack(S); break;// 重置S为空栈

default : Push(S, ch); break;

}

ch = getchar(); // 从终端接收下一个字符

}

将从栈底到栈顶的字符传送至调用过程的

数据区；

ClearStack(S); // 重置S为空栈

if (ch != EOF) ch = getchar();

3.2.4 迷宫求解

通常用的是“穷举求解”的方法

求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;

3.2.5 表达式求值

限于二元运算符的表达式定义:

Exp = S1 OP S2

操作数 :变量、常量、表达式

运算符 :算术运算符、关系运算符、逻辑运算符

界限符：括号、结束符

例：3 * ( 7 – 2 )

OPTR栈 OPND栈输入操作

1 # 3 * ( 7 – 2 ) # PUSH( OPND, ‘3’ )

2 # 3 * ( 7 – 2 ) # PUSH( OPTR, ‘*’ )

3 # * 3 ( 7 – 2 ) # PUSH( OPTR, ‘(’ )

4 # * ( 3 7 – 2 ) # PUSH( OPND, ‘7’ )

5 # * ( 3 7 – 2 ) # PUSH( OPTR, ‘–’ )

6 # * (– 3 7 2 ) # PHSH( OPND, ‘2’ )

7 # * (– 3 7 2 ) # operate( ‘7’,’-’,’2’ )

8 # * ( 3 5 ) # POP( OPTR )

9 # * 3 5 # operate( ‘3’, ‘*’, ‘5’ )

10 # 15 # return GetTop( OPND )

OperandType EvaluateExpression() {

// 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。

InitStack (OPTR); Push (OPTR, '#');

initStack (OPND); c = getchar();

while (c!= '#' || GetTop(OPTR)!= '#') {

if (!In(c, OP)) { Push((OPND, c); c = getchar(); }

// 不是运算符则进栈

else

} // while

return GetTop(OPND);

} // EvaluateExpression

switch ( precede(GetTop(OPTR), c) {

case '<': // 栈顶元素优先权低

Push(OPTR, c); c = getchar();

break;

case '=': // 脱括号并接收下一字符

Pop(OPTR, x); c = getchar();

break;

case '> ': // 退栈并将运算结果入栈

Pop(OPTR, theta);

Pop(OPND, b); Pop(OPND, a);

Push(OPND, Operate(a, theta, b));

break;

} // switch

3.4 队列

3.4.1 队列的类型定义

队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。

队尾(rear)——允许插入的一端

队头(front)——允许删除的一端

队列特点：先进先出(FIFO)

队列的类型定义

ADT Queue {

数据对象：

D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0}

数据关系：

R1＝{ <a i-1,ai > | ai-1, ai ∈D, i=2,...,n}

约定其中a1 端为队列头， an 端为队列尾

基本操作：

} ADT Queue

队列的基本操作：

InitQueue(&Q) DestroyQueue(&Q)

QueueEmpty(Q) QueueLength(Q)

GetHead(Q, &e) ClearQueue(&Q)

EnQueue(&Q, e) DeQueue(&Q, &e)

QueueTravers(Q, visit())

3.4.2 链队列－队列的链式表示和实现

typedef struct QNode{// 结点类型

QElemType data ;

struct QNode *next ;

}QNode, *QueuePtr;

typedef struct{ //链队列类型

QueuePtr front ; //队头指针

QueuePtr rear ; //队尾指针

} LinkQueue;

Status InitQueue (LinkQueue &Q) {

// 构造一个空队列Q

Q.front = Q.rear =

(QueuePtr)malloc(sizeof(QNode));

if (!Q.front) exit (OVERFLOW);

//存储分配失败

Q.front->next = NULL;

return OK;

}

Status EnQueue (LinkQueue &Q,

QElemType e) {

// 插入元素e为Q的新的队尾元素

p = (QueuePtr) malloc (sizeof (QNode));

if (!p) exit (OVERFLOW); //存储分配失败

p->data = e; p->next = NULL;

Q.rear->next = p; Q.rear = p;

return OK;

}

Status DeQueue (LinkQueue &Q,

QElemType &e) {

// 若队列不空，则删除Q的队头元素，

//用 e 返回其值，并返回OK；否则返回ERROR

if (Q.front == Q.rear) return ERROR;

p = Q.front->next; e = p->data;

Q.front->next = p->next;

if (Q.rear == p) Q.rear = Q.front;

free (p); return OK;

}

3.4.3 循环队列－队列的顺序表示和实现

#define MAXQSIZE 100 //最大队列长度

typedef struct {

QElemType *base; // 动态分配存储空间

int front; // 头指针，若队列不空，

//指向队列头元素

int rear; // 尾指针，若队列不空，指向

// 队列尾元素的下一个位置

} SqQueue;

实现：用一维数组实现sq[M]

存在问题：

当front=0,rear=M时再有元素入队发生溢出——真溢出

当front≠0,rear=M时再有元素入队发生溢出——假溢出

解决方案

队首固定，每次出队剩余元素向下移动——浪费时间

循环队列

基本思想：把队列设想成环形，让sq[0]接在sq[M-1] 之后，若rear+1==M,则令rear=0;

实现：利用“模”运算

入队： base[rear]=x; rear=(rear+1)%M;

出队： x=base[front]; front=(front+1)%M;

队满、队空判定条件

解决方案：

1.另外设一个标志位以区别队空、队满

2.少用一个元素空间：

队空：front==rear 队满：(rear+1)%M==front

3.使用一个计数器记录队列中元素的总数

Status InitQueue (SqQueue &Q) {

// 构造一个空队列Q

Q.base = (QElemType *) malloc

(MAXQSIZE *sizeof (QElemType));

if (!Q.base) exit (OVERFLOW);

// 存储分配失败

Q.front = Q.rear = 0;

return OK;

}

Status EnQueue (SqQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素

if ((Q.rear+1) % MAXQSIZE == Q.front)

return ERROR; //队列满

Q.base[Q.rear] = e;

Q.rear = (Q.rear+1) % MAXQSIZE;

return OK;

}

Status DeQueue (SqQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素，

// 用e返回其值，并返回OK; 否则返回ERROR

if (Q.front == Q.rear) return ERROR;

e = Q.base[Q.front];

Q.front = (Q.front+1) % MAXQSIZE;

return OK;

}

秒客网

[数据结构]栈和队列

相关文章