数据结构习题集（二）—— 栈，队列，数组

• 第2章 栈，队列，数组
• • 2.4 单链表表头指针h，判断该链表前个字符是否中心对称
  • 2.5 S1，S2为共享存储区[0,Maxsize]的顺序栈，栈顶相向，迎面增长；设计S1和S2有关入栈和出栈的算法
  • 2.6 为利用循环队列空间，设置标志域tag以区分队头指针front和队尾指针rear相同时队列的状态是“空”还是“满”，写出对应的入队和出队算法
  • 2.7 Q是队列，S是空栈，将队列中的元素逆置
  • *2.8 用两个栈模拟一个队列

bool dc(LinkLNode *h,int n) {
    char s[n/2];	//存放前 n/2 个元素入栈
    int i;
    LinkLNode *p = h->next;
    for(i = 0;i < n / 2;i++) {
        s[i] = p->data;
        p = p->next;
    }
    i--;
    if(n % 2 == 1)		//如果n是奇数，跳过中心位置
        p = p->next;
    while(p != NULL && p->data == s[i]) {
		i--;
        p = p->next;
    }
    if(i == -1)
        return true;
    else
        return false;
}

typedef struct {
    int top[2];
    int stack[Maxsize];
}Stack;

Stack s;

// 入栈
Status Push(int id,ElemType x) {
	if(id != 1 || id != 2) {	//栈号不对
        perror("栈号错误n");
        return ERROR;
    }
    
    if(s.top[1] - s.top[0] == 1) {	//栈满
     	perror("栈满n");
        return ERROR;
    }
    
    switch(id){
      	case 1:
            s.stack[++s.top[0]] = x;
            return OK;
            break;
        case 2:
            s.stack[--s.top[1]] == x;
            return OK;
            break;
    }
}


// 出栈
Status Pop(int id,ElemType &x) {
    if(id != 1 || id != 2) {	//栈号不对
        perror("栈号错误n");
        return ERROR;
    }
    switch(id){
        case 1:
            if(s.top[0] == -1) {
                perror("S1已空n");
                return ERROR;
            }
            else {
                x = s.stack[s.top[0]];
                s.top[0] --;
                return OK;
            }
            break;
        case 2:
            if(s.top[1] == Maxsize) {
                perror("S2已空n");
                return ERROR;
            }
            else{
                x = s.stack[s.top[1]];
                s.top[1]++;
                return OK;
            }
            break
    }
}

struct SqQueue{
    int front;
    int rear;
    bool tag;
    ElemType data[Maxsize];
}

// 入队
Status EnQueue(SqQueue &Q,ElemType x) {
    if(Q.front == Q.rear && tag = 0)		//队满
        return ERROR;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1)%Maxsize;
    Q.tag = 1;
    return OK;
}

// 出队
Status DeQueue(SqQueue &Q,ElemType &x) {
    if(Q.front == Q.rear && tag = 0)		//队空
        return ERROR;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1)%Maxsize;
    Q.tag = 0;
    return OK;
}

void reverse(Queue &Q,Stack S){
    while(!QueueEmpty(Q)){
        DeQueue(Q,x);	//队列中元素出队
        Push(S,x);		//依次入栈
    }
    while(!StackEmpty(S)) {
        Pop(S,x); 		//出栈
        EnQueue(Q,x);	//依次入队
    }
}

已知栈的四个运算定义如下：

• Push(S，x) //元素x入栈S

• Pop(S,x) //S出栈，并将出栈的值赋给x

• StackEmpty(S) //判断栈是否为空

• StackOverflow(S) //判断栈是否满

实现EnQueue()，DeQueue()，QueueEmpty()

 


Status EnQueue(Stack &S1,Stack &S2,ElemType x) {
    if(!StackOverflow(S1)) {	// S1未满
        Push(S1,x);			//正常入栈
        return OK;
    }
    if(StackOverflow(S1) && !StackEmpty(S2))	//S1满，S2非空，不能入队
        return ERROR;
    if(StackOverflow(S1) && StackEmpty(S2)) {		//S1满，S2空，把S1全部插入S2，再入队
    	while(!StackEmpty(S1)) {
            Pop(S1,temp);
            Push(S2,temp);
        }
        Push(S1,x);
        return OK;
    }
}


Status DeQueue(Stack &S1, Stack &S2,ElemType &x) {
    if(StackEmpty(S2) && StackEmpty(S1))		//栈均为空，不能出队
        return ERROR;
    if(!StackEmpty(S2)) {		//S2非空，直接出队
        Pop(S2,x);
        return OK;
    }
    if(StackEmpty(S2) && !StackEmpty(S1)){		//S2为空，S1非空，把S1全部插入S2
        while(!StackEmpty(S1)){
            Pop(S1,temp);
            Push(S2,temp);
        }
        Pop(S2,x);
        return OK;
    }
}


bool QueueEmpty(Stack S1,Stack S2){
    if(!StackEmpty(S1) && !StackEmpty(S2))
        return true;
    return false;
}
  if(StackEmpty(S2) && StackEmpty(S1))		//栈均为空，不能出队
        return ERROR;
    if(!StackEmpty(S2)) {		//S2非空，直接出队
        Pop(S2,x);
        return OK;
    }
    if(StackEmpty(S2) && !StackEmpty(S1)){		//S2为空，S1非空，把S1全部插入S2
        while(!StackEmpty(S1)){
            Pop(S1,temp);
            Push(S2,temp);
        }
        Pop(S2,x);
        return OK;
    }
}


bool QueueEmpty(Stack S1,Stack S2){
    if(!StackEmpty(S1) && !StackEmpty(S2))
        return true;
    return false;
}