栈

2022.09.06

栈的基本概念

栈顶（进行插入删除的一端），栈底，空栈
特性：先进后出，FILO
$\frac{1}{n+1}C_{2n}^{n}$ （卡特兰数）

栈的顺序存储结构

https://github.com/CharlesShan-hub/DataStructureNotes/blob/master/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97/%E9%A1%BA%E5%BA%8F%E6%A0%88.cpp


// 顺序栈 - 两种top
/** 基本操作如下
 * 定义
 * 初始化
 * 判空
*/
#include <stdio.h>
#include <stdbool.h>

// 定义
#define MaxSize 10
typedef struct
{
  int data[MaxSize];
  int top;
}SqStack;// 顺序栈

/*
// 初始化 - 方案一:top指向最后一个原元素
void InitStack(SqStack &S){
  S.top = -1;
}
*/

// 初始化 - 方案二:top指向下一个要插入的元素
void InitStack(SqStack &S){
  S.top = 0;
}

// 判空 - 方案一:top指向最后一个原元素
/*
bool StackEmpty(SqStack S){
  return S.top==-1;
}
*/

// 判空 - 方案二:top指向下一个要插入的元素
bool StackEmpty(SqStack S){
  return S.top==0;
}

// 进栈 - 方案一:top指向最后一个原元素
/*
bool Push(SqStack &S, int x){
  if(S.top==MaxSize-1)
    return false;
  S.data[++S.top] = x
  return true;
}
*/

// 进栈 - 方案二:top指向下一个要插入的元素
bool Push(SqStack &S, int x){
  if(S.top==MaxSize)
    return false;
  S.data[S.top++] = x;
  return true;
}

// 出栈 - 方案一:top指向最后一个原元素
/*
bool Pop(SqStack &S, int &x){
  if(S.top==-1)
    return false;
  x = S.data[S.top--];
  return true;
}
*/

// 出栈 - 方案二:top指向下一个要插入的元素
bool Pop(SqStack &S, int &x){
  if(S.top==0)
    return false;
  x = S.data[--S.top];
  return true;
}

// 读栈顶 - 方案一:top指向最后一个原元素
/*
bool GetTop(SqStack S, int &x){
  if(S.top==-1)
    return false;
  x = S.data[S.top];
  return true;
}
*/

// 读栈顶 - 方案二:top指向下一个要插入的元素
bool GetTop(SqStack S, int &x){
  if(S.top==-1)
    return false;
  x = S.data[S.top];
  return true;
}

int main(){
  // 声明顺序栈
  SqStack S;
  // 初始化
  InitStack(S);
  // 进栈
  Push(S,1);
  Push(S,2);
  Push(S,3);
  Push(S,4);
  Push(S,5);
  Push(S,6);
  Push(S,7);
  Push(S,8);
  Push(S,9);
  Push(S,10);
  Push(S,11);
  // 获取栈顶
  int x;
  GetTop(S,x);
  printf("%d\n",x); // -> 10
  // 出栈
  Pop(S,x);
  printf("%d ",x);
  Pop(S,x);
  printf("%d ",x);
  Pop(S,x);
  printf("%d\n",x); // -> 10 9 8

  return 0;
}

栈的链式存储结构

和链表类似

习题

栈和队列具有相同的( )。 A. 抽象数据类型 B.逻辑结构 C．存储结构 D. 运算
【答案】：C->B。栈和队列的逻辑结构都是相同的，都属于线性结构，只是它们对数据的运算不同。
栈是（） A. 顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存储点的非线性结构
【答案】：C
（）不是栈的基本操作。 A. 删除栈顶元素 B. 删除栈底元素 C. 判断栈是否为空 D. 将栈置为空栈
【答案】：B
假定利用数组a[n]顺序存储一个栈，用top表示栈项指针，用 top==-1 表示栈空，并已知栈未满，当元素 × 进栈时所执行的操作为（）。 A. a[--top]=x B. a[top--]=x C. a[++top]=x D. a[top++]=x
【答案】：C
设有一个空栈，栈顶指针为 1000H，每个元素需要一个存储单元，执行 Push、Push、Pop、Push、 Pop、 Push、Pop、Push操作后，栈顶指针的值为（）。 A. 1002H B. 1003H C. 1004H D. 1005H
【答案】：A
和顺序栈相比，链栈有一个比较明显的优势，即（） A. 通常不会出现栈满的情況 B. 通常不会出现栈空的情況 C. 插入操作更容易实现 D. 删除操作更容易实现
【答案】：A
设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是（） A. 只有表头结点指针，没有表尾指针的双向循环链表 B. 只有表尾结点指针，没有表头指针的双向循环链表 C. 只有表头结点指针，没有表尾指针的单向循环链表 D. 只有表尾结点指针，没有表头指针的单向循环链表
【答案】：C。对于C，第n个节点需要指向第一个新节点，所以需要一次O(n)的寻找尾结点。
向一个栈顶指针为top的链栈（不带头结点）中插入一个x结点，则执行( ). A. top->next=x B. x->next=top->next；top->next=x C. x-›next=top； top=x D. x-›next=top； top=top-›next
【答案】：D->C
链栈（不带头结点）执行Pop操作，并将出栈的元素存在x中，应该执行( ). A. x=top; top=top-›next B. x=top-›data C. top=top-›next; x=top-›data D. x=top-›data; top=top-›next
【答案】：D
经过以下栈的操作后，变量x的值为（） InitStack (st); Push (st, a); Push (st, b); Pop(st, x); Pop(st, x) A. a B. b C. NULL D. FALSE
【答案】：A
3个不同元素依次进栈，能得到（）种不同的出栈序列。 A. 4 B. 5 C. 6 D. 7
【答案】：B
设a.b,c,d,e,f以所给的次序进栈，若在进栈操作时，允许出栈採作，则下西得不到的序列为（） A. fedcba B. bcafed C. dcefba D. cabdef
【答案】：D
用S表示进栈操作，用x表示出栈操作，若元素的进栈顺序是1234，为了得到 1342 的出栈顺序，相应的S和X的操作序列为（）。 A. SXSXSSXX B. SSSXXSXX C. SXSSXXSX D. SXSSXSXX
【答案】：D
若一个栈的输入序列是1，2，3,...,n输出序列的第一个元素是n，则第i个输出元素是（） A. 不确定 B. n-i C. n-i-1 D. n-i+1
【答案】：D
一个栈的输入序列为1,2,3，…，n，输出序列的第一个元素是i，则第j个输出元素是(）。 A. i-i-1 B. i-i C. i-i+1 D.不确定
【答案】：D
某栈的输入序列为a,b,c,d，下面的4个序列中，不可能为其输出序列的是（）. A. a,b,c,d B. c, b, d, a C. d, c, a, b D. a, c, b, d
【答案】：C
若一个栈的输入序列是P1, P2, …，Pn，输出序列是1,2,3，n，若P3=1，则P1的值（）。 A. 可能是2 B. 一定是2 C. 不可能是2 D. 不可能是2
【答案】：A->C
已知一个栈的入栈序列是1，2，3，4，其出栈序列为P1，P2，P3，P4，则P2,P4不可能是(） A. 2,4 B. 2,1 C. 4.3 D. 3.4
【答案】：C
设栈的初始状态为空，当宇符序列“n1_”作为栈的输入时，输出长度为3，且可用做C语言标识符的序列有（）个， A. 4 B. 5 C. 3 D. 6
【答案】：_1n, n1_, n_1, 1_n, 1n_，C
来用共享栈的好处是（）。 A. 减少存取时间，降低发生上溢的可能 B. 节省存储空问，降低发生上溢的可能 C. 滅少存取时间，降低发生下溢的可能 D. 节省存储空问，降低发生下溢的可能
【答案】：B
设有一个顺序共享栈 Share [0:n-1]，其中第一个栈顶指针topl的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是（）。 A. top2-top1==1 B. top1-top2==1 C. topl==top2 D. 以上都不对
【答案】：A
【2009统考真题】设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且了个元素出队的顺序是bdcfeag，则栈S的容量至少是（） A. 1 B. 2 C. 3 D. 4
【答案】：3，C
【2010统考真题】若元素a,b,c,d,e,f依次进栈，允许进栈、退栈探作交替进行，但不允许连续3次进行退栈操作，不可能得到的出栈序列是( )。 A. dcebfa B. cbdaef C. bcaefd D. afedcb
【答案】：D
【2011 统考真题】元素a,b,C,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是( ） A. 3 B.4 C. 5 D. 6
【答案】：B
【2013 统考真题】一个栈的入栈序列为 1，2,3，⋯，n，出栈序列是P1，P2，B3,..., Pn，若P2=3，则P3可能取值的个数是（）。 A. n-3 B. n-2 C. n-1 D.无法确定
【答案】：C
【2017 统考真题】下列关于栈的叙述中，错误的是（） I. 采用非递归方式重写递归程序时必须使用栈 II. 函数调用时，系统要用栈保存必要信息 III. 只要确定入栈顺序，就能确定出栈顺序 IV. 栈是一种受限的线性表，允许在共两进行 A.仅I B.仅I、II、III C.仅II、III、IV D.仅I、III、IV
【答案】：C
【2018 统考真题】若栈 S1 中保存整数，栈S2 中保存运算符，函数F（)依次执行下述各步操作：
1）从S1 中依次弹出两个操作数a和b。 2）从S2 中弹出一个运算符。p。 3）执行相应的运算b op a. 4）将运算结果压入S1 中。假定 S1 中的操作数依次是5,8,3,2（2在栈顶），S2中的运算符依次是*、-、+（+在栈顶)。调用3次F（后，S1 栈顶保存的值是（）。 A. -15 B. 15 C. -20 D. 20
【答案】：2+3 = 5，8-5 = 3，5*3 = 15，B
【2020 统考真题】对空栈S进行Push 和Pop 操作，入栈序列为a,b,c,d，e，经过Push, Push. Pop、 Push. Pop、 Push.Push、 Pop 操作后得到的出栈序列是（）。 A. b, a, c B. b, a, e C. b, c, a D. b,c, e
【答案】：D
有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次市中，第一个出栈元素为C且第二个出栈元素为D的出栈序列有哪几个？
【答案】：AB [C] [D] E ，3个
若元素的进栈序列为A，B，C，D，E，运用栈操作，能否得到出栈序列B,C,A,E,D和D,B,A,C,E？为什么？
【答案】：B,C,A,E,D可以，D,B,A,C,E不可以，因为D第一个出栈后剩下的是[ABC]。B不能直接出栈

假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，可以操作的序列称为合法序列，否则称为非法序列。

下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO
【答案】：A,D

通过对 1）的分析，写出一个算法，判定所给的探作序列是否合法。若合法，返回 true，否则返回 false (假定被判定的操作序列已存入一维数组中），

【答案】


bool valid(char *array, int len){
  int count = 0;
  for(int i=0;i<len;i++){
    if(array[i]=='I')
      count++;
    else
      count--;
    if(count<0)
      return false;
  }
  return count==0;
}

设单链表的表头指针为L，结点结构由data 和next两个城构成，其中data 域为字符型。试设计算法判断该链表的全部n 个宇符是否中心对称。例如xyx、xyyx 都是中心对称。


int length(LinkList L){
  int len = 0;
  while(L->next!=NULL){
    len++;
    L = L->next;
  }
  return len;
}

bool IsDuiChen(LinkList L){
  LinkList T = NULL;
  LNode *p = L->next;
  Lnode *temp = NULL;
  int len = length(L);
  for(int i=0;i<len/2;i++){
    temp = p;
    p=p->next;
    temp->next = T;
    T = temp;
  }
  if(len%2==1)
    p = p->next;
  for(int i=0;i<len/2;i++){
    if(p->data!=T->data) return false;
    T->next = T;
    p=p->next;
  }
}

设有两个栈S1、S2 都采用顺序栈方式，并共享一个存储区 [0, ..., maxsize-1]，为了尽量利用空间，减少溢出的可能，可来用栈顶相向、迎面增长的存储方式。试设计 S1、S2有关入栈和出栈的操作算法。


bool push(Stack &S, int i, int num){
  if(S.len2-S.len1==1) return false;
  if(i==1){
    S[++S.len1] = sum;
  }else if(i==2){
    S[--S.len2] = sum;
  }else{
    return false;
  }
  return true;
}

bool pop(Stack &S, int i, int &num){
  if(i==1){
    if(S.len1==-1) return false;
    num = S[++S.len1];
  }else if(i==2){
    if(S.len2==S.maxsize) return false;
    num = S[S.len2++];
  }else{
    return false;
  }
  return true;
}