王道数据结构【栈队列及其应用】部分代码实现（C语言）

判断链表是否中心对称

struct Link {
	union {
		char letter;
	}type;
	struct Link *next;
};
struct Stack {
	char *arr;
	int len;
	int top;
};
#define _CRT_SECURE_NO_WARNINGS
#include 
void isSymmetry(Link *h) {
	int size;
	struct Stack *s;
	Stack *createStack(int);
	bool push(Stack *,char);
	bool empty(Stack *);
	char *top(Stack *);
	bool pop(Stack *);
	void destory(Stack *);
	printf("请输入要创建的栈的大小：size=");
	scanf("%d",&size);
	s = createStack(size);
	struct Link *fast = h->next, *slow = h->next;
	while (fast->next&&fast->next->next) {
		fast = fast->next->next;
		slow = slow->next;
	}
	fast = h->next;
	while (slow->next) {//将中间元素的后面节点依次入栈
		push(s,slow->next->type.letter);
		slow = slow->next;//我总是忘记往下走
	}
	while (!empty(s)) {
		if (fast->type.letter != *top(s) ) {
			printf("该链表非中心对称");
			break;
		}
		fast = fast->next;
		pop(s);
	}
	if(empty(s))printf("该链表是中心对称的");
	destory(s);//最后销毁栈
}
int main() {
	struct Link *head;
	Link *createLink(int);
	head = createLink(1);
	isSymmetry(head);
	return 0;
}

实现共享栈

#include
#include
#include
#define TYPE char 
struct Stack
{
	TYPE* arr;	//内存首地址
	int top[2]; 	//栈的下标
};


//创建一个栈
Stack *createStack(int size) {
	struct Stack *stack = (struct Stack*)malloc(sizeof(struct Stack));//给栈分配空间
	stack->arr = (TYPE *)malloc(sizeof(TYPE)*size);//给内存首地址分配空间，大小用户指定
	stack->top[0] = -1;//栈顶下标，当前无元素，故为-1
	stack->top[1] = size;//栈顶下标，当前无元素，故为-1
	return stack;
}
//判断栈满
bool full(Stack *stack) {
	return stack->top[1]-stack->top[0] == 1;
}
//判断栈空
bool empty(int i,Stack *stack,int size) {
	switch (i) {
	case 0:
		return stack->top[0] == -1; 
	case 1:
			return stack->top[0] == size;

	}
}
//入栈(具体值)
bool push(Stack *stack, TYPE data,int i) {
	if (full(stack)) return false;
	switch (i) {
	case 0:
		*(stack->arr + ++stack->top[i]) = data;
	case 1:
		*(stack->arr + --stack->top[i]) = data;
	}
	return true;
}

//出栈
bool pop(int i,Stack *stack,int size) {
	if (empty(i,stack,size)) return false;
	switch (i) {
	case 0:
		stack->top[i]--;
	case 1:
		stack->top[i]++;
	}
	return true;

}

创建栈

#include
#include
#include
#define TYPE int
//#define TYPE biTree*
//#define TYPE char
//#define TYPE Recursion
struct biTree {
	char data;
	struct biTree *lchild;
	struct biTree *rchild;
};
struct Recursion {
	int no;
	int val;
};
struct Stack
{
	TYPE* arr;	//内存首地址
	int  len;	//栈的容量
	int top; 	//栈的下标
};


//创建一个栈
Stack *createStack(int size) {
	struct Stack *stack = (struct Stack*)malloc(sizeof(struct Stack));//给栈分配空间
	stack->arr = (TYPE *)malloc(sizeof(TYPE)*size);//给内存首地址分配空间，大小用户指定
	stack->len = size;//栈容量
	stack->top = -1;//栈顶下标，当前无元素，故为-1
	return stack;
}
//判断栈满
bool full(Stack *stack) {
	return stack->top + 1 >= stack->len;
}
//判断栈空
bool empty(Stack *stack) {
	return stack->top == -1;
}
//入栈
bool push(Stack *stack, TYPE p) {
	if (full(stack)) return false;
	*(stack->arr + ++stack->top) = p;
	return true;
}

//出栈
bool pop(Stack *stack) {
	if (empty(stack)) return false;
	stack->top--;
	return true;

}

//查看栈顶元素
TYPE top(Stack *stack) {
	if (empty(stack)) return NULL;
	return *(stack->arr + stack->top);
}

//销毁
void destory(Stack *stack) {
	free(stack->arr);
	free(stack);

}
//判断是否含有某个元素
bool contain(Stack *stack, TYPE r) {
	if (empty(stack)) return false;
	for (int i = stack->top; i >= 0; i--) {
		if (r == *(stack->arr + i) ){//疯了，我居然把==写成了=
			return true;
		}
	}
	return false;
}

创建链队

//#define TYPE biTree* 
#define TYPE char
//#define TYPE int
struct biTree {//新增树节点
	char data;
	struct biTree *lchild;
	struct biTree *rchild;

};
struct Link {
	//TYPE data;
	TYPE node;
	struct Link *next;
};
struct LinkQueue {
	struct Link *front, *rear;
};
#include 
#include 

//创建一个空链表
Link* createLink() {
	int n, data;
	char letter;
	struct Link *q;
	struct Link *head = (struct Link*) malloc(sizeof(struct Link));
	head->next = NULL;
	q = head;
	return head;
}
//创建链队
LinkQueue *create() {
	struct Link *h,*p;
	struct LinkQueue *lq=(struct LinkQueue *)malloc(sizeof(struct LinkQueue));
	h = createLink();
	p = h->next;
	lq->front = lq->rear = h;
	return lq;
}
//判断空
bool isEmpty(LinkQueue *lq) {
	return lq->front == lq->rear;
}
//入队
bool enQueue(LinkQueue *lq,TYPE data) {//队尾插入
	struct Link *newd = (struct Link *)malloc(sizeof(struct Link));
	newd->node = data;
	lq->rear->next = newd;
	lq->rear = newd;
	lq->rear->next = NULL;
	return true;
}
//出队
bool deQueue(LinkQueue *lq,TYPE *data) {
	if (isEmpty(lq))return false;
	struct Link *p = lq->front->next;//保存下一个节点
	*data = lq->front->next->node;//取出队首节点值
	lq->front->next = p->next;//删除队首节点
	if (lq->rear==p) {
		lq->rear = lq->front;
	}
	free(p);
	return true;
}
//打印队列中元素
void printQ(LinkQueue *lq) {
	Link *p = lq->front->next;
	while (p!=NULL) {
		printf("%c",p->node);
		p = p->next;
	}
};

tag队列

#include 
#include 
#define TYPE int 
struct Squeue {
	TYPE *arr;
	int front, rear;
	int tag;
};

//创建队列
Squeue *create(int n) {
	struct Squeue *sq = (struct Squeue *)malloc(sizeof(struct Squeue));
	sq->arr = (TYPE *)malloc(sizeof(TYPE)*n);//数组大小
	sq->front = 0;
	sq->rear = 0;
	sq->tag = 0;
	return sq;
}
//判断队满
bool isFull(Squeue *sq, int maxSize) {
	return (sq->rear == sq->front) && (sq->tag == 1);
}
//判断队空
bool isEmpty(Squeue *sq) {
	return (sq->front == sq->rear) && sq->tag==0;
}
//判断队列中元素个数
int count(Squeue *sq, int maxSize) {
	return (sq->rear - sq->front + maxSize) % maxSize;
}
//入队
bool enQueue(Squeue *sq, int data, int maxSize) {
	if (isFull(sq, maxSize)) return false;
	sq->arr[sq->rear] = data;
	sq->rear = (sq->rear + 1) % maxSize;
	sq->tag = 1;
	return true;
}
//出队
bool deQueue(Squeue *sq, int &data, int maxSize) {
	if (isEmpty(sq)) return false;
	data = sq->arr[sq->front];
	sq->front = (sq->front + 1) % maxSize;
	sq->tag = 0;
	return true;
}

利用栈逆置队列中的元素

//createStack.cpp

#include
#include
#include
#define TYPE int
//#define TYPE biTree*
//#define TYPE char
//#define TYPE Recursion
struct biTree {
	char data;
	struct biTree *lchild;
	struct biTree *rchild;
};
struct Recursion {
	int no;
	int val;
};
struct Stack
{
	TYPE* arr;	//内存首地址
	int  len;	//栈的容量
	int top; 	//栈的下标
};


//创建一个栈
Stack *createStack(int size) {
	struct Stack *stack = (struct Stack*)malloc(sizeof(struct Stack));//给栈分配空间
	stack->arr = (TYPE *)malloc(sizeof(TYPE)*size);//给内存首地址分配空间，大小用户指定
	stack->len = size;//栈容量
	stack->top = -1;//栈顶下标，当前无元素，故为-1
	return stack;
}
//判断栈满
bool full(Stack *stack) {
	return stack->top + 1 >= stack->len;
}
//判断栈空
bool empty(Stack *stack) {
	return stack->top == -1;
}
//入栈
bool push(Stack *stack, TYPE p) {
	if (full(stack)) return false;
	*(stack->arr + ++stack->top) = p;
	return true;
}

//出栈
bool pop(Stack *stack) {
	if (empty(stack)) return false;
	stack->top--;
	return true;

}

//查看栈顶元素
TYPE top(Stack *stack) {
	if (empty(stack)) return NULL;
	return *(stack->arr + stack->top);
}

//销毁
void destory(Stack *stack) {
	free(stack->arr);
	free(stack);

}
//判断是否含有某个元素
bool contain(Stack *stack, TYPE r) {
	if (empty(stack)) return false;
	for (int i = stack->top; i >= 0; i--) {
		if (r == *(stack->arr + i) ){//疯了，我居然把==写成了=
			return true;
		}
	}
	return false;
}

括号匹配

// createStack.cpp
#include
#include
#include
#define TYPE int
//#define TYPE biTree*
//#define TYPE char
//#define TYPE Recursion
struct biTree {
	char data;
	struct biTree *lchild;
	struct biTree *rchild;
};
struct Recursion {
	int no;
	int val;
};
struct Stack
{
	TYPE* arr;	//内存首地址
	int  len;	//栈的容量
	int top; 	//栈的下标
};


//创建一个栈
Stack *createStack(int size) {
	struct Stack *stack = (struct Stack*)malloc(sizeof(struct Stack));//给栈分配空间
	stack->arr = (TYPE *)malloc(sizeof(TYPE)*size);//给内存首地址分配空间，大小用户指定
	stack->len = size;//栈容量
	stack->top = -1;//栈顶下标，当前无元素，故为-1
	return stack;
}
//判断栈满
bool full(Stack *stack) {
	return stack->top + 1 >= stack->len;
}
//判断栈空
bool empty(Stack *stack) {
	return stack->top == -1;
}
//入栈
bool push(Stack *stack, TYPE p) {
	if (full(stack)) return false;
	*(stack->arr + ++stack->top) = p;
	return true;
}

//出栈
bool pop(Stack *stack) {
	if (empty(stack)) return false;
	stack->top--;
	return true;

}

//查看栈顶元素
TYPE top(Stack *stack) {
	if (empty(stack)) return NULL;
	return *(stack->arr + stack->top);
}

//销毁
void destory(Stack *stack) {
	free(stack->arr);
	free(stack);

}
//判断是否含有某个元素
bool contain(Stack *stack, TYPE r) {
	if (empty(stack)) return false;
	for (int i = stack->top; i >= 0; i--) {
		if (r == *(stack->arr + i) ){//疯了，我居然把==写成了=
			return true;
		}
	}
	return false;
}

车厢调度

#include 
#include 
struct Stack {
	char *arr;
	int len;
	int top;
};
void trainArrange(char *arrA,char *arrB,Stack *s) {//传入入口车厢，出口车厢，栈
	int i = 0, j = 0;
	char *c;//接收出栈硬座
	bool push(Stack *,char );
	char *top(Stack *);
	bool pop(Stack *);
	bool empty(Stack *);
	while (i<10) {
		if (arrA[i]=='H') {//硬座，入栈
			push(s,arrA[i]);
		}
		else {//软座，入B
			arrB[j++] = arrA[i];
		}
		i++;
	}
	while (!empty(s)) {//若栈中还有硬座，全部入B
		c = top(s);
		pop(s);
		arrB[j++] = *c;
	}

}
int main() {
	char arrA[10] = {'H','S','S','H','H','S','S','S','H','H' };//用H代表硬座，S代表软座
	char arrB[10] = { 0 };//B数组初始为空
	Stack *createStack(int);
	Stack *s;
	s = createStack(10);//创建栈
	trainArrange(arrA,arrB,s);
	for (int i = 0; i < 10;i++) {//打印重排后的车厢
		printf("%c",arrB[i]);

	}
	return 0;
}

利用栈实现递归函数的非递归计算

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
struct Recursion {
	int no;
	int val;
};
struct Stack {
	Recursion *arr;
	int len;
	int top;
};
int getP(Stack *s,int n,int x) {//该算法函数,传入栈，n和x
	if (n==0) {
		return 1;
	}
	int fv1 = 1, fv2 = 2 * x;
	for (int i = n; i >= 2;i--) {//将序号入栈，从上至下，从2到n
		s->top++;
		s->arr[s->top].no = i;
	}
	while (s->top>=0) {//边出栈边计算
		s->arr[s->top].val = 2 * x*fv2 - 2 * (s->arr[s->top].no - 1)*fv1;
		fv1 = fv2;
		fv2 = s->arr[s->top].val;
		s->top--;
	}
	return fv2;
}
int main() {
	Stack *s;
	//声明各类方法
	Stack *createStack(int);
	bool push(Stack *,Recursion *);
	bool full(Stack *);
	bool empty(Stack *);
	bool top(Stack *);
	bool pop(Stack *);

	int n, x;//题目所要用到的n和x
	int p;//用于接收结果
	printf("请输入n和x: n");
	printf("n=");
	scanf("%d",&n);
	printf("x=");
	scanf("%d", &x);

	//创建大小为n的栈
	s = createStack(n);
	p=getP(s,n,x);
	printf("%d",p);
	return 0;
}

车辆调度

#include 

struct Stack {
	int *arr;
	int len;
	int top;
};
void manageCar(int *arrCar, int *arrArrange, Stack *s) {
	int i = 0, passengerCar = 0, j = 0;
	int *c;//接收出栈硬座
	bool push(Stack *, int);
	int *top(Stack *);
	bool pop(Stack *);
	bool empty(Stack *);
	for (; arrCar[i] == 1 || arrCar[i] == 2; i++) {
		if (arrCar[i] == 2 && passengerCar < 4) {//如果是货车且之前还没有4辆客车，入栈
			push(s, arrCar[i]);
		}
		else {//若是客车，直接入arrArrange
			if (passengerCar == 4) {//若之前已有连续4辆客车，出栈入货车
				if (!empty(s)) {
					c = top(s);
					pop(s);
					arrArrange[j++] = *c;
					passengerCar = 0;//重新计数
				}
			}
			arrArrange[j++] = arrCar[i];
			passengerCar++;//连续客车数加一
		}
	}
	while (!empty(s)) {//栈内元素不空，加入到arrArrange
		c = top(s);
		pop(s);
		arrArrange[j++] = *c;
	}

}
int main() {

	int arrCar[] = { 2,1,2,1,1,1,1,2,2,2,1,1 };//我们用1代表客车，用2发表货车,arrCar代表当前的车序列，然后我们需要重排
	int arrArrange[20] = { 0 };//初始化为0，接收重排的车队
	Stack *createStack(int);
	Stack *s;
	s = createStack(20);//创建一个栈
	manageCar(arrCar, arrArrange, s);
	for (int i = 0; i < 10; i++) {//取10辆车出来
		printf("%d ", *(arrArrange + i));
	}
	return 0;
}

王道数据结构【栈队列及其应用】部分代码实现（C语言）

C/C++/C#相关栏目本月热门文章