数据结构简单入门/复习(三)-栈与队列(C语言)(2021/3/30更新)

这里的栈用的是顺序栈(数组),队列用的是链表队列(链表)。

2021/3/25: 加了共享顺序栈。我以前有够懒的噢,不过我现在也有够懒的,所以其他存储结构后面再补。
2021/3/30: 加了完全利用空间的循环顺序队列,加了入队退队时间复杂度为O(1)且不浪费出队结点空间的循环链式队列。

定义与结构

栈是一种限定在表尾进行插入/删除的线性表,表尾,被称作栈顶,表头,被称作栈底,薯片桶就是一种栈。

栈是一种后进先出的线性表。举个例子,有三个元素1、2、3,其中,1是第一个进的,2是第二个进的,3是第三个进的,那么在栈底的元素是1,栈顶的元素是3,若进行删除操作,出来的是栈顶的3。

#define SElemType int    //设置栈中元素的类型为int
typedef struct{
    SElemType *base;     //栈底
    SElemType *top;      //栈顶
    int stacksize;       //注意,这里的栈的大小是指总大小,而不是指用了几个,只在重新分配空间时会变化。
}SqStack;

顺序栈的使用

SqStack S;

//初始化栈
S.base = (SElemType*)malloc(100*sizeof(SElemType));  //为栈分配空间,大小为100.
S.top = S.base;      //栈顶位置设置,因为此时栈是空栈。
S.stacksize = 100;   //将栈的大小设置为100,及最开始分配空间的大小。

//插入
if(S.top-S.base >= S.stacksize){    //这部分的判断是为了解决栈空间不足。
    S.base = (SElemType*)realloc(S.base, S.stacksize+10)*sizeof(SElemType));  //realloc是一个重新分配内存空间的函数,这里用来给栈增加10个空间。
    S.top = S.base + S.stacksize;  //栈底的地址因为realloc函数改变了,因此栈顶要重新设置。
    S.stacksize += 10;             //将栈的大小记录值增加。
}
*S.top++ = 123;

//删除
if(S.top == S.base) print("已空");  //栈顶和栈底指针相同,意味着是空栈。
else --S.top;                       //栈直接退后即可,不用释放内存。

//获得栈顶数据
printf("%d", *(S.top-1));           //top位置是用来存储新数据的,栈顶位置是在top-1的地方。

顺序共享栈

#include <stdio.h>
#include <stdlib.h>

#define STACK_LENGTH 5

typedef struct shareStack {
	int* data;
	int maxSize;
	int leftTop;
	int rightTop;
}shareStack;

shareStack* initializeStack();
void enlargeStack(shareStack* s);
void pushLeftStack(shareStack* s, int value);
int popLeftStack(shareStack* s);
int stackLeftEmpty(shareStack* s);
void pushRightStack(shareStack* s, int value);
int popRightStack(shareStack* s);
int stackRightEmpty(shareStack* s);


int main(){
	shareStack* s = initializeStack();
	int value;
	int pos;
	puts("left stack test: push element more than stack size");
	for (pos = 0; pos < STACK_LENGTH ; pos++) {
		pushLeftStack(s, pos);
	}
	while (stackLeftEmpty(s) != 1) {
		value = popLeftStack(s);
		printf("%d ", value);
	}
	puts("\n\nright stack test: push element more than stack size");
	for (pos = 0; pos < STACK_LENGTH * 2; pos++) {
		pushRightStack(s, pos);
	}
	while (stackRightEmpty(s) != 1) {
		value = popRightStack(s);
		printf("%d ", value);
	}
	puts("\n\nmix stack test: push leftStack and RightStack then pop all");
	for (pos = 0; pos < STACK_LENGTH * 2; pos++) {
		pushLeftStack(s, pos);
		pushRightStack(s, pos);
	}
	for (pos = 0; pos < STACK_LENGTH * 2; pos++) {
		value = popLeftStack(s);
		printf("%d ", value);
		value = popRightStack(s);
		printf("%d ", value);
	}

	system("PAUSE");
	return 0;
}


shareStack* initializeStack() {	//栈初始化
	shareStack* s;
	s = malloc(sizeof(shareStack));
	s->maxSize = STACK_LENGTH;
	s->data = malloc(sizeof(int) * s->maxSize);
	s->leftTop = 0;
	s->rightTop = s->maxSize - 1;
	return s;
}

void enlargeStack(shareStack* s) {	//栈扩容
	printf("enlargeing...\n");
	s->maxSize += STACK_LENGTH;
	s->data = realloc(s->data, sizeof(int) * s->maxSize);
	int pos;
	for (pos = s->maxSize - STACK_LENGTH - 1; pos > s->rightTop; pos--) {
		s->data[pos + STACK_LENGTH] = s->data[pos];
	}
	s->rightTop += STACK_LENGTH;
}

void pushLeftStack(shareStack* s, int value) {	//左栈进栈
	if (s->rightTop == s->leftTop) {
		enlargeStack(s);
	}
	s->data[s->leftTop] = value;
	s->leftTop += 1;
}

int popLeftStack(shareStack* s) {	//左栈退栈一次,返回退栈的值
	s->leftTop -= 1;
	return s->data[s->leftTop];
}

int stackLeftEmpty(shareStack* s) {	//左栈为空时,返回1,否则为0
	return s->leftTop == 0 ? 1 : 0;
}

void pushRightStack(shareStack* s, int value) {	//右栈进栈
	if (s->rightTop == s->leftTop)
		enlargeStack(s);
	s->data[s->rightTop] = value;
	s->rightTop -= 1;
}

int popRightStack(shareStack* s) {	//右栈退栈一次,返回退栈的值
	s->rightTop += 1;
	return s->data[s->rightTop];
}

int stackRightEmpty(shareStack* s) {	//右栈为空时,返回1,否则为0
	return s->rightTop == s->maxSize - 1 ? 1 : 0;
}

队列

定义与结构

队列是一种先进先出的线性表,元素从表头插入,从表尾退出。

队列的形式与日常的排队相似,但是没有插队这个说法。

//队列元素:
#define QElemType int
typedef struct QNode{
    QElemType data;      //元素数据
    struct QNode *next;  //后排元素
}QNode;
//队列存储:
typedef struct{
    QNode *front;    //队头指针
    QNode *rear;     //队尾指针
}LinkQueue;

链式队列的使用

//创建
LinkQueue Q;
Q.front = Q.rear = (QNode*)malloc(sizeof(QNode));   //队头不放元素,仅作指示

//插入
QNode *p = (QNode*)malloc(sizeof(QNode)); //分配新元素内存空间
p->data = 123;       //设置新元素值
p->next = NULL;      //新元素后没有元素
Q.rear->next = p;    //将队尾的下一个元素设置成新元素
Q.rear = p;          //将新元素设置为新的队尾

//删除
if(Q.front == Q.rear) print("队列已空");
else {
    QNode *temp = Q.front->next;           //创建临时指针指向队头
    Q.front->next = temp->next;            //将队头设置成第二位的元素
    if(Q.rear == temp) Q.rear = Q.front;   //如果队头是最后一个元素,将队尾的指针调整为队头指针,此时为空队列
    free(temp);                            //释放退出的队头
}

//获得队头值
if(Q.front == Q.rear) printf("队列已空");
else print("%d", Q.front->next->data);

循环顺序队列-完全利用空间

#include <stdio.h>
#include <stdlib.h>

#define QUEUE_LENGTH 5

typedef struct cycleQueue {
	int* data;
	int front;
	int rear;
	int isEmpty;
}cycleQueue;

cycleQueue* initializeCycleQueue();
int enqueue(cycleQueue* q, int ele);
int dequeue(cycleQueue* q, int* ele);

int main(){
	cycleQueue* q = initializeCycleQueue();
	int value;
	int pos;
	int pass;

	puts("队列大小为5,进7个,退7个:");
	for (pos = 0; pos < QUEUE_LENGTH + 2; pos++) {
		pass = enqueue(q, pos);
		if(pass) printf("%d enqueue, front: %d, rear: %d\n", pos, q->front, q->rear);
	}
	for (pos = 0; pos < QUEUE_LENGTH + 2; pos++) {
		pass = dequeue(q, &value);
		if(pass)printf("%d dequeue, front: %d, rear: %d\n", value, q->front, q->rear);
	}

	puts("\n队列大小为5,进7个,退2个,进7个,并输出队列情况:");
	for (pos = 0; pos < QUEUE_LENGTH + 2; pos++) {
		pass = enqueue(q, pos);
		if (pass) printf("%d enqueue, front: %d, rear: %d\n", pos, q->front, q->rear);
	}
	for (pos = 0; pos < 2; pos++) {
		pass = dequeue(q, &value);
		if (pass)printf("%d dequeue, front: %d, rear: %d\n", value, q->front, q->rear);
	}
	for (pos = 10; pos < QUEUE_LENGTH + 12; pos++) {
		pass = enqueue(q, pos);
		if (pass) printf("%d enqueue, front: %d, rear: %d\n", pos, q->front, q->rear);
	}
	for (pos = 0; pos < QUEUE_LENGTH; pos++) {
		printf("%d ", q->data[pos]);
	}

	system("PAUSE");
	return 0;
}


cycleQueue* initializeCycleQueue() {
	cycleQueue* q = malloc(sizeof(cycleQueue));
	q->front = 0;	//头指针指向队头的下一个位置
	q->rear = 0;	//尾指针指向队尾的下一个位置
	q->data = malloc(sizeof(int) * QUEUE_LENGTH);
	q->isEmpty = 1;	//1表示队列空
	return q;
}

int enqueue(cycleQueue* q, int ele) {
	if (q->front == q->rear && q->isEmpty == 0) {
		printf("Queue full, error enqueue operation.\n");
		return 0;
	}
	q->isEmpty = 0;
	q->data[q->rear] = ele;
	q->rear = (q->rear + 1) % QUEUE_LENGTH;
	return 1;
}

int dequeue(cycleQueue* q, int* ele) {
	if (q->front == q->rear && q->isEmpty == 1) {
		printf("Queue empty, error dequeue operation.\n");
		return 0;
	}
	q->front = (q->front + 1) % QUEUE_LENGTH;
	if (q->front == q->rear) q->isEmpty = 1;
	*ele = q->data[(q->front - 2 + (QUEUE_LENGTH + 1)) % QUEUE_LENGTH];
	return 1;

}

循环链式队列-不浪费退队空间,且入队退队时间复杂度O(1)。

#include <stdio.h>
#include <stdlib.h>

#define QUEUE_LENGTH 2

typedef struct queueNode {
	struct queueNode* next;
	int data;
}queueNode;

typedef struct queue {
	queueNode* front;
	queueNode* rear;
}queue;

queue* initializeQueue();
void enqueueBin(queue* qBin, queueNode* node);
queueNode* dequeueBin(queue* qBin);
int dequeue(queue* q, queue* qBin);
void enqueue(queue* q, queue* qBin, int val);
void printQueue(queue* q);

int main(){
	queue* q = initializeQueue();
	queue* qBin = initializeQueue();
	int value;
	int pos;
	int pass;

	puts("进4个,退4个:");
	for (pos = 0; pos < QUEUE_LENGTH + 2; pos++) {
		enqueue(q, qBin, pos);
		printf("%d enqueue\n", pos);
	}
	for (pos = 0; pos < QUEUE_LENGTH + 2; pos++) {
		value = dequeue(q, qBin); 
		printf("%d  dequeue\n", value);
	}
	printQueue(q);

	puts("\n,进4个,退2个,进4个:");
	for (pos = 10; pos < QUEUE_LENGTH + 12; pos++) {
		enqueue(q, qBin, pos);
		printf("%d enqueue\n", pos);
	}
	for (pos = 0; pos < 2; pos++) {
		value = dequeue(q, qBin);
		printf("%d   dequeue\n", value);
	}
	for (pos = 20; pos < QUEUE_LENGTH + 22; pos++) {
		enqueue(q, qBin, pos);
		printf("%d enqueue\n", pos);
	}
	printQueue(q);

	system("PAUSE");
	return 0;
}

queue* initializeQueue() {
	queue* q = malloc(sizeof(queue));
	q->front = q->rear = NULL;
	return q;
}

void enqueueBin(queue* qBin, queueNode* node) {
	if (qBin->front == NULL) {
		qBin->front = qBin->rear = node;
	}
	else {
		qBin->rear->next = node;
		qBin->rear = node;
		node->next = NULL;
	}
}

queueNode* dequeueBin(queue* qBin) {
	if (qBin->front == NULL) {
		return malloc(sizeof(queueNode));
	}
	else {
		queueNode *res = qBin->front;
		qBin->front = qBin->front->next;
		return res;
	}
}

int dequeue(queue* q, queue* qBin) {
	if (q->rear == NULL) {
		printf("queue empty, error.\n");
		return 0;
	}
	queueNode* node = q->front;
	if (q->front == q->rear) {
		q->front = q->rear = NULL;
	}
	else {
		q->rear->next = q->front->next;
		q->front = q->front->next;
	}
	enqueueBin(qBin, node);
	return node->data;
}

void enqueue(queue* q, queue* qBin, int val) {
	queueNode *node = dequeueBin(qBin);
	node->data = val;
	if (q->front == NULL) {
		node->next = node;
		q->front = q->rear = node;
	}
	else {
		node->next = q->front;
		q->rear->next = node;
		q->rear = node;
	}
}

void printQueue(queue* q) {
	queueNode* node = q->front;
	if (node) do {
		printf("%d ", node->data);
		node = node->next;
	} while (node != q->front);
	puts("");
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注