栈与队列

栈

顺序栈

• 结构定义

  #define Stack_Size 1024
  
  typedef struct {
      StackElementType elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
      int top;                /*用来存放栈顶元素的下标，top为-1表示空栈*/
  } SeqStack, Stack, *StackPtr;

• 初始化

  void InitStack(StackPtr *S) {
      (*S)->top = -1;		//栈顶指针置为空
  }

• 进栈

  bool Push(StackPtr S, StackElementType x) {
      if (IsFull(S)) return false;
  
      S->elem[++S->top] = x;
  
      return true;
  }

• 获取栈顶元素

  bool GetTop(StackPtr S, StackElementType *x) {
      if (IsEmpty(S)) return false;
  
      *x = S->elem[S->top];
      
      return true;
  }

• 出栈

  bool Pop(StackPtr S, StackElementType *x) {
      if (!GetTop(S, x)) return false;
      --S->top;
  
      return true;
  }

链栈

• 初始化

  typedef struct node {
      StackElementType data;
      struct node *next;
  } LinkStackNode, *LinkStackNodePtr, LinkStack, Stack, *StackPtr;

• 初始化

  void InitStack(StackPtr *S) {
      (*S) = (StackPtr)malloc(sizeof(LinkStackNode));
      (*S)->next = NULL;	//栈顶指针置空
  }

• 进栈

  bool Push(StackPtr S, StackElementType x) {
      LinkStackNodePtr temp = (LinkStackNodePtr)malloc(sizeof(LinkStackNode));
      if (temp == NULL) return false;
  
      //链表的头插法
      temp->data = x;
      temp->next = S->next;
      S->next = temp;
  
      return true;
  }

• 获取栈顶元素

  bool GetTop(StackPtr S, StackElementType *x) {
      if (IsEmpty(S)) return false;
  
      *x = S->next->data;
  
      return true;
  }

• 出栈

  bool Pop(StackPtr S, StackElementType *x) {
      //在链表头部删除节点
      LinkStackNodePtr temp = S->next;
      if (temp==NULL) return false; //empty
  
      *x = temp->data;
      S->next = temp->next;
      free(temp);
  
      return true;
  }

队列

顺序队列（so easy，略）

链队列

• 结构定义

  typedef struct Node {
      QueueElementType data;     /*数据域*/
      struct Node *next;     /*指针域*/
  } LinkQueueNode, *LinkQueueNodePtr;
  
  typedef struct {
      LinkQueueNode *front;	/*队头指针*/
      LinkQueueNode *rear;	/*队尾指针*/
  } LinkQueue, Queue, *QueuePtr;

• 初始化

  void InitQueue(QueuePtr Q) {
      /* 将Q初始化为一个空的链队列 */
      Q->front = (LinkQueueNodePtr)malloc(sizeof(LinkQueueNode));
      Q->front->next = NULL;	/*队头指针的指向为空*/
      Q->rear = Q->front;	/*队尾指针指向队头*/
  }

• 入队

  bool EnterQueue(QueuePtr Q, QueueElementType x) {
      /* 将数据元素x插入到队列Q中 */
      LinkQueueNode *NewNode = (LinkQueueNodePtr)malloc(sizeof(LinkQueueNode));
      NewNode->data = x;
      NewNode->next = NULL;
  
      Q->rear->next = NewNode;
      Q->rear = NewNode;
  
      return true;
  }

• 出队

  bool DeleteQueue(QueuePtr Q, QueueElementType *x) {
      /* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */
      if (IsEmpty(Q)) return false;
  
      LinkQueueNodePtr p = Q->front->next;
  
      *x = p->data;
      Q->front->next = p->next;
      if (Q->rear == p) Q->rear = Q->front;
      free(p);
  
      return true;
  }

循环队列

• 结构定义

  #define MAXSIZE 50  /*队列的最大长度*/
  
  typedef struct
  {
  	QueueElementType element[MAXSIZE];  /* 队列的元素空间*/
  	int front;  /*头指针指示器*/
  	int rear;  /*尾指针指示器*/
  } SeqQueue, Queue, *QueuePtr;

• 初始化

  void InitQueue(QueuePtr Q) {
      /* 将*Q初始化为一个空的循环队列 */
      Q->front = Q->rear = 0;	/*头尾指针均置空*/
  }

• 判断队列是否为空

  bool IsEmpty(QueuePtr Q) {
      return Q->front == Q->rear;
  }

• 判断队列是否已满

  bool IsFull(QueuePtr Q) {
      return _modinc(Q->rear) == Q->front;
  }

• 入队

  bool EnterQueue(QueuePtr Q, QueueElementType x) {
      /*将元素x入队*/
      if (IsFull(Q)) /*队列已经满了*/
          return false;
  
      Q->element[Q->rear] = x;
      Q->rear = _modinc(Q->rear);
  
      return true;
  }

• 出队

  bool DeleteQueue(QueuePtr Q, QueueElementType *x) {
      /*删除队列的队头元素，用x返回其值*/
      if (IsEmpty(Q))  /*队列为空*/
          return false;
  
      *x = Q->element[Q->front];
      Q->front = _modinc(Q->front);
  
      return true;
  }