栈与队列

Posted:   October 10, 2019

Status:   Completed

Tags :   数据结构

Categories :  

Were equations, pictures or diagrams not properly rendered, please refresh the page. If the problem persists, you can contact me.

一、栈

1.栈的基本概念

  1. 栈的基本定义
    • 栈顶：线性表允许进行插入和删除的那一端（我这不怕题目变了嘛，记清楚没坏处）
    • 栈底：固定的，不允许进行插入和删除的那一端
    • 空栈：不含任何元素的空表
    • 操作特性：后进后出（我怎么记得这个地方老是考）
  2. 栈的基本操作
    • 这个地方的意思就是这些函数不用你再复写一遍，直接用不客气

2.栈的顺序存储结构

  1. 栈顶指针：S.top，初始时设置为S.top = -1；栈顶元素：S.data[S.top]

  2. 进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素

  3. 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1

  4. 栈空条件：S.top = -1

  5. 栈满条件：S.top = MAXSIZE - 1

  6. 栈长：S.top + 1

  7. 基本实现

    #include <stdio.h>
#include <stdlib.h>
#define MaxSize 50
#define TRUE 1
#define FALSE 0
   
typedef struct{
  int data[MaxSize]; //存放栈中元素
  int top; //栈顶指针
}SqStack;
   
void InitStack(SqStack *S){
  S->top = -1; //初始化栈顶指针
}
   
int StackEmpty(SqStack S){
    if(S.top == -1){
      return TRUE; //栈空
    }
    else{
      return FALSE; //不空
    }
}
   
int Push(SqStack *S,int x){
  if(S->top==MaxSize - 1){
    return FALSE; //栈满了
  }
  else{
    S->data[++S->top] = x;
    return TRUE; //栈还没有满，指针+1，数据入栈
  }
}
   
int Pop(SqStack *S){
  if(S->top==-1){
    return FALSE; //栈是空的，报错
  }
  else{
    return S->data[S->top--]; //先出栈，然后指针-1
  }
}
   
int GetTop(SqStack S){
  if(S.top == -1){
    return FALSE; //栈空
  }
  else{
    return S.data[S.top];
  }
}
   
int main() {
  SqStack S;
  InitStack(&S);
  printf("%d\n",S.top);
  printf("%d\n",StackEmpty(S));
  Push(&S,666);
  printf("%d\n", S.data[0]);
  printf("%d\n",S.top);
  printf("%d\n",GetTop(S));
  printf("%d\n", Pop(&S));
  printf("%d\n",S.top);
  return 0;
}

  8. 共享栈

    • 这种方法对存取效率没什么影响
    • 更有效利用存储空间

3.栈的链式存储结构

  1. #include <stdio.h>
#include <stdlib.h>
   
typedef struct Node{
  int data;
  struct Node *next;
}Node,*Stack;
   
typedef struct LinkStack{
  Node* top; //栈顶指针
  int count; //元素个数
}LinkStack;
   
LinkStack InitStack(){
  LinkStack stack;
  stack.top = NULL;
  stack.count = 0;
  return stack;
}
   
void Push(LinkStack* stack,int x){
  Node* s;
  s = (Node*)malloc(sizeof(Node));
  s->next = stack->top; //这个地方是因为栈顶结点在单链表表头哦
  s->data = x;
  stack->top = s;
  stack->count++;
}
   
int  Pop(LinkStack* stack){
  if(stack->top != NULL){
    Node* s = stack->top;
    int x = stack->top->data;
    stack->top = stack->top->next;
    free(s);
    return x;
  }
}
   
void PrintS(LinkStack stack){
  Node* s = stack.top;
  while(s != NULL){
    printf("%d\n", s->data);
    s = s->next;
  }
  printf("\n");
}
   
int main(int argc, char const *argv[]) {
  LinkStack stack = InitStack();
  Push(&stack,1);
  Push(&stack,2);
  Push(&stack,5);
  PrintS(stack);
  return 0;
}

二、队列

1.队列的定义

  1. 队列的顺序存储结构

    • 队头：允许删除的一端

    • 队尾：允许插入的一端

    • 空队列：不含任何元素的空表

      队列的基本操作

    • 队空条件：Q.front = Q.rear = 0

    • 进队操作：队不满时，先送值到队尾元素，再将队尾指针加1

    • 出队操作：队不空时，先取队头元素值，再将队头指针加1

    • 不能用Q.rear = MAXSIZE作为队满的条件，因为有可能假溢出

  2. 循环队列

    • #include <stdio.h>
#include <stdlib.h>
     
#define MaxSize 6
#define TRUE 1
#define FALSE 0
     
typedef struct{
  int data[MaxSize];
  int front,rear;
}SqQueue;
     
//循环队列
     
void InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0; //初始化队首，队尾指针 
}
     
int isEmpty(SqQueue Q){
  if(Q.rear == Q.front){
    return TRUE;
  }
  else{
    return FALSE;
  }
}
     
int EnQueue(SqQueue *Q,int x){
  if((Q->rear+1)%MaxSize == Q->front){
    return FALSE;
  }
  else{
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear+1)%MaxSize;
    return TRUE;
  }
}
     
int DeQueue(SqQueue *Q){
    if(Q->rear == Q->front){
      return FALSE; //队列是空的，不行
    }
    else{
      Q->front = (Q->front+1)%MaxSize;
      return TRUE;
    }
}
     
int main(int argc, char const *argv[]) {
  SqQueue Q;
  InitQueue(&Q);
  printf("%d\n", Q.rear);
  EnQueue(&Q,10);
  printf("%d\n", Q.rear);
  EnQueue(&Q,10);
  printf("%d\n", Q.rear);
  EnQueue(&Q,10);
  printf("%d\n", Q.rear);
  EnQueue(&Q,10);
  printf("%d\n", Q.rear);
  EnQueue(&Q,10);
  printf("%d\n", Q.rear);
  EnQueue(&Q,10);
  printf("%d\n", Q.rear);
  //printf("%d\n", Q.front);
  return 0;
}

    • 区分队空还是队满的情况，有三种处理方式

      1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，预定以“队头指针在队尾指针的下一个位置作为队满的标志”
        • 队满条件：(Q.rear + 1)%MAXSIZE = Q.front
        • 队空条件：Q.front = Q.rear = 0
        • 队列中的元素个数：(Q.rear - Q.front + MAXSIZE)%MAXSIZE
      2. 类型中增设表示元素个数的数据成员
        • 队空条件：Q.size = 0
        • 队满条件：Q.zize = MAXSIZE
      3. 类型中增加tag数据成员，以区分是队满还是队空。
        • tag = 0，因删除导致Q.front = Q.rear，队空
        • tag = 1，因插入导致Q.front = Q.rear，队满

2.队列的链式存储结构

  1. #include <stdio.h>
#include <stdlib.h>
   
#define TRUE 1
#define FALSE 0
   
typedef struct{ //链式队列的结点
  int data;
  struct LinkNode *next;
}LinkNode;
   
typedef struct{
  LinkNode *front,*rear; //链式队列队头队尾指针
}LinkQueue;
   
void InitQueue(LinkQueue *Q){
    Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode)); //建立头结点
    Q->front->next = NULL;
}
   
int IsEmpty(LinkQueue Q){
  if(Q.rear == Q.front){
    return TRUE;
  }
  else{
    return FALSE;
  }
}
   
void EnQueue(LinkQueue *Q,int x){
  LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
  s->data = x;
  s->next = NULL;
  Q->rear->next = s;
  Q->rear = s;
}
   
int DeQueue(LinkQueue *Q){
  if(Q->rear == Q->front){
    return FALSE;
  }
  else{
    LinkNode *p = Q->front->next;
    Q->front->next = p->next;
    if(Q->rear == p){
      Q->rear=Q->front;
    }
    free(p);
    return TRUE;
  }
}
   
int main(int argc, char const *argv[]) {
  LinkQueue Q;
  InitQueue(&Q);
  printf("%d\n", Q.front->next);
  printf("%d\n", IsEmpty(Q));
  return 0;
}

3.双端队列（略）

Comments

😅 Commenting is disabled on this post.
You can use extended GitHub flavored markdown in your comment. Commenting FAQs & Guidelines