栈与队列基本操作及其应用

你的名字 2022-10-08 14:22 210阅读 0赞

### 文章目录 ###

*   *  一、栈
     *   *  栈的实现
         *   *  顺序栈
         *  栈的应用
         *   *  1.数制转换(十进制转换为R进制)
             *  2.括号匹配的检验
     *  二、队列
     *   *  队列的实现
         *   *  1.队列的链式表示和实现
             *  2.循环队列-队列的顺序表示和实现
         *  队列的应用
         *   *  1.用循环队列模拟银行窗口排队

## 一、栈 ##

### 栈的实现 ###

#### 顺序栈 ####

#include <iostream>
    using namespace std;
    
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1 //不可执行
    #define OVERFLOW -2
    
    #define STACK_INIT_SIZE 100 //存储空间初始分配量
    #define STACKINCREMENT 10 //存储空间分配增量
    
    typedef int SElemType;
    typedef int Status;
    
    //存储结构
    typedef struct {
        
        SElemType* base; //栈构造之前和销毁之后，值都为NULL
        SElemType* top; //栈顶指针
        int stacksize; //当前已分配的存储空间，以元素为单位
    }SqStack;
    
    /*初始化*/
    Status InitStack(SqStack& S) {
        
        S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
        if (!S.base) //存储分配失败
            exit(OVERFLOW);
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
        return OK;
    
    }
    /*返回栈顶元素
    用e返回栈顶元素，返回OK；若为空，返回ERROR*/
    Status GetTop(SqStack S, SElemType& e) {
        
        if (S.top == S.base)
            return ERROR;
        return OK;
    }
    /*插入*/
    Status Push(SqStack& S, SElemType e) {
        
        //e 新的栈顶元素
        if (S.top - S.base >= S.stacksize) {
        
            S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
            if (!S.base)
                exit(OVERFLOW);
            S.top = S.base + S.stacksize;
            S.stacksize += STACKINCREMENT;
        }
        *S.top++ = e;
        return OK;
    }
    /*删除栈顶元素并返回其值*/
    Status Pop(SqStack& S, SElemType& e) {
        
        if (S.top == S.base)
            return ERROR;
        e = *--S.top;
        return OK;
    }
    
    /*判断栈是否为空*/
    int StackEmpty(SqStack S)
    {
        
        if (S.base == S.top)
            return 1;
        else
            return 0;
    }
    
    
    int main()
    {
        
        SqStack S;
        InitStack(S);
        int n;
        cout << "请输入栈的长度：";
        cin >> n;
        int e1;
        for (int i = 0; i < n; i++) {
        
            cout << "请输入栈中第" << i + 1 << "个元素的值：";
            cin >> e1;
            Push(S, e1);
        }
        cout << "出栈：";
        int e;
        while (!StackEmpty(S))
        {
        
            Pop(S, e);
            cout << e << " ";
    
        }
    
        return 0;
    }

### 栈的应用 ###

#### 1.数制转换(十进制转换为R进制) ####

将十进制数N转换为R进制数

#include <iostream>
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1 //不可执行
    #define OVERFLOW -2
    
    #define STACK_INIT_SIZE 100 //存储空间初始分配量
    #define STACKINCREMENT 10 //存储空间分配增量
    
    typedef int SElemType;
    typedef int Status;
    
    //存储结构
    typedef struct {
        
        SElemType* base; //栈构造之前和销毁之后，值都为NULL
        SElemType* top; //栈顶指针
        int stacksize; //当前已分配的存储空间，以元素为单位
    }SqStack;
    
    /*初始化*/
    Status InitStack(SqStack& S) {
        
        S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
        if (!S.base) //存储分配失败
            exit(OVERFLOW);
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
        return OK;
    
    }
    
    /*插入*/
    Status Push(SqStack& S, SElemType e) {
        
        //e 新的栈顶元素
        if (S.top - S.base >= S.stacksize) {
        
            S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
            if (!S.base)
                exit(OVERFLOW);
            S.top = S.base + S.stacksize;
            S.stacksize += STACKINCREMENT;
        }
        *S.top++ = e;
        return OK;
    }
    /*删除并输出*/
    Status Pop(SqStack& S, SElemType& e) {
        
        if (S.top == S.base)
            return ERROR;
        e = *--S.top;
        return OK;
    }
    /*判断是否为空 为空则返回TRUE*/
    bool Stackmpty(SqStack S) {
        
        if (S.top == S.base) {
        
            return true;
        }
        else {
        
            return false;
        }
    }
    /*十进制转换为R进制*/
    void conversion() {
        
        SqStack S;
        InitStack(S);
        int e;
        int N;
        cin >> N;
        int M = N;
        int R;
        cin >> R;
        
        while (M)
        {
        
            Push(S, M % R);
            M = M / R;
        }
        while (!Stackmpty(S))
        {
        
            Pop(S, e);
            if (e >= 0 && e <= 9) {
        
                cout << e;
            }
            else {
        
                cout << char('a' + e - 10);
            }
           
        }
     
    }
    
    int main()
    {
        
        
        conversion();
    
        return 0;
    }

#### 2.括号匹配的检验 ####

#include <iostream>
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    
    #define STACK_INIT_SIZE 100 //存储空间初始分配量
    #define STACKINCREMENT 10 //存储空间分配增量
    
    typedef int SElemType;
    typedef int Status;
    
    struct SqStack {
        
        int* base; //栈底
        int* top;  //栈顶
        int stacksize;   //栈当前的存储空间
    };
    /*初始化*/
    Status InitStack(SqStack& S) {
        
        S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
        if (!S.base) //存储分配失败
            exit(OVERFLOW);
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
        return OK;
    
    }
    /*插入*/
    Status Push(SqStack& S, SElemType e) {
        
        //e 新的栈顶元素
        if (S.top - S.base >= S.stacksize) {
        
            S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
            if (!S.base)
                exit(OVERFLOW);
            S.top = S.base + S.stacksize;
            S.stacksize += STACKINCREMENT;
        }
        *S.top++ = e;
        return OK;
    }
    /*删除*/
    Status Pop(SqStack& S, SElemType& e) {
        
        if (S.top == S.base)
            return ERROR;
        e = *--S.top;
        return OK;
    }
    int StackEmpty(SqStack S)
    {
        
        if (S.base == S.top)
            return 1;
        else
            return 0;
    }
    /*括号匹配的检验*/
    void Parentheses_match()
    {
        
        SqStack s;//初始化空栈
        InitStack(s);
        char ch[100], * p; int e;
        p = ch;
        cout << "输一个含义有()[]{}的括号表达式:\n";
        // gets(ch);
        cin >> ch;
        while (*p)
        {
        
            switch (*p)
            {
        
            case '{':
            case '[':
            case '(': Push(s, *p++); break;//只要是左括号就入栈
            case '}':
            case ']':
            case ')':Pop(s, e);
                if ((e == '{' && *p == '}') || (e == '[' && *p == ']') || (e == '(' && *p == ')'))
                    p++;
                else
                {
        
                    cout << "括号不匹配!"; exit(OVERFLOW);
                }
                break;
            default:p++;//其他字符就后移
            }
        }
        if (StackEmpty(s))
            cout << "括号匹配成功";
        else
            cout << "缺少右括号！";
        cout << endl;
    
    }
    
    int main() {
        
        Parentheses_match();
    
        return 0;
    }

/*括号匹配的检验*/
    void Parentheses_match(SqStack s,char* ch)
    {
        
        int e;
        char* p;
        p = ch;
        while (*p)
        {
        
            switch (*p)
            {
        
            case '{':
            case '[':
            case '(': Push(s, *p++); break;//只要是左括号就入栈
            case '}':
            case ']':
            case ')':Pop(s, e);
                if ((e == '{' && *p == '}') || (e == '[' && *p == ']') || (e == '(' && *p == ')'))
                    p++;
                else
                {
        
                    cout << "括号不匹配!"; exit(OVERFLOW);
                }
                break;
            default:p++;//其他字符就后移
            }
        }
        if (StackEmpty(s))
            cout << "括号匹配成功";
        else
            cout << "缺少右括号！";
        cout << endl;
    
    }
    
    int main() {
        
        SqStack s;//初始化空栈
        InitStack(s);
        char ch[100];
        
        cout << "输一个含义有()[]{}的括号表达式:\n";
        // gets(ch);
        cin >> ch;
        Parentheses_match(s,ch);
    
        return 0;
    }

## 二、队列 ##

### 队列的实现 ###

#### 1.队列的链式表示和实现 ####

#include <iostream>
    using namespace std;
    
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1 //不可执行
    #define OVERFLOW -2
    
    #define STACK_INIT_SIZE 100 //存储空间初始分配量
    #define STACKINCREMENT 10 //存储空间分配增量
    
    typedef int QElemType;
    typedef int Status;
    
    /*--------单链队列-队列的链式存储结构--------*/
    /*线性表的单链表的存储结构*/
    typedef struct QNode {
        
    	QElemType data;
    	struct QNode* next;
    }QNode,*QueuePtr;
    typedef struct {
        
    	QueuePtr front; //队头指针
    	QueuePtr rear; //队尾指针
    }LinkQueue;
    
    Status InitQueue(LinkQueue& Q) {
        
    	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    	if (!Q.front)
    		exit(OVERFLOW);
    	Q.front->next = NULL;
    	return OK;
    }
    Status DestoryQueue(LinkQueue& Q) {
        
    	while (Q.front)
    	{
        
    		Q.rear = Q.front->next;
    		free(Q.front);
    		Q.front = Q.rear;
    	}
    	return OK;
    }
    /*插入元素e为Q的新的队尾元素*/
    Status EnQueue(LinkQueue& Q, QElemType e) {
        
    	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    	if (!p)
    		exit(OVERFLOW);
    	p->data = e;
    	p->next = NULL;
    	Q.rear->next = p;
    	Q.rear = p;
    	return OK;
    }
    /*若队列不为空则删除Q的队头元素，用e返回其值，并返回ok；否则返回ERROR*/
    Status DeQueue(LinkQueue& Q, QElemType& e) {
        
    	if (Q.front == Q.rear)
    		return ERROR;
    	QueuePtr p = Q.front->next;
    	e = p->data;
    	Q.front->next = p->next;
    	if (Q.rear == p)
    		Q.rear = Q.front;
    	free(p);
    	return OK;
    }
    /*判断队列是否为空*/
    Status QueueEmpty(LinkQueue Q) {
        
    	if (Q.front == Q.rear)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    int main() {
        
    	LinkQueue q;
    	InitQueue(q);
    	int n;	
    	cout << "请输入队列的长度：";
    	cin >> n;
    	int e1;
    	for (int i = 0; i < n; i++) {
        
    		cout << "请输入队列中第" << i+1 << "个元素的值：";		
    		cin >> e1;
    		EnQueue(q, e1);
    	}
    	cout << "出队：";
    	int e;
    	while (!QueueEmpty(q))
    	{
        
    		DeQueue(q, e);
    		cout << e << " ";
    	}
    	
    	return 0;
    }

#### 2.循环队列-队列的顺序表示和实现 ####

#include <iostream>
    using namespace std;
    
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1 //不可执行
    #define OVERFLOW -2
    
    #define STACK_INIT_SIZE 100 //存储空间初始分配量
    #define STACKINCREMENT 10 //存储空间分配增量
    
    typedef int QElemType;
    typedef int Status;
    
    #define MAXQSIZE 100 //最大队列长度
    
    /*--------单链队列-队列的顺序存储结构--------*/
    /*线性表的单链表的存储结构*/
    typedef struct QNode {
        
    	QElemType* base;
    	int front;
    	int rear;
    }SqList;
    
    
    Status InitQueue(SqList& Q) {
        
    	Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
    	if (!Q.base)
    		exit(OVERFLOW);
    	Q.front = Q.rear = 0;
    	return OK;
    }
    
    int QueueLength(SqList Q) {
        
    	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
    }
    
    /*插入元素e为Q的新的队尾元素*/
    Status EnQueue(SqList& Q, QElemType e) {
        
    	if ((Q.rear + 1) % MAXQSIZE == Q.front)
    		return ERROR;
    	Q.base[Q.rear] = e;
    	Q.rear = (Q.rear + 1) % MAXQSIZE;
    	return OK;
    }
    
    /*若队列不为空则删除Q的队头元素，用e返回其值，并返回ok；否则返回ERROR*/
    Status DeQueue(SqList& Q, QElemType& e) {
        
    	if (Q.front == Q.rear)
    		return ERROR;
    	e = Q.base[Q.front];
    	Q.front = (Q.front + 1) % MAXQSIZE;
    	return OK;
    }
    /*判断队列是否为空*/
    Status QueueEmpty(SqList Q) {
        
    	if (Q.front == Q.rear)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    int main() {
        
    	SqList q;
    	InitQueue(q);
    	int n;
    	cout << "请输入队列的长度：";
    	cin >> n;
    	int e1;
    	for (int i = 0; i < n; i++) {
        
    		cout << "请输入队列中第" << i + 1 << "个元素的值：";
    		cin >> e1;
    		EnQueue(q, e1);
    	}
    	int e;
    	cout << "出队：";
    	while (!QueueEmpty(q))
    	{
        
    		DeQueue(q, e);
    		cout << e << " ";
    	}
    	/*while ((q.rear + 1) % MAXQSIZE != q.front)
    	{
    		cout << q.base[q.rear]<<" ";
    		q.rear++;
    	}*/
    
    	return 0;
    }

### 队列的应用 ###

#### 1.用循环队列模拟银行窗口排队 ####

具体要求如下：

① 用整数代表排队客户的编号。

② 入队和出队的调用序列可直接写在代码中 （但要足够多以覆盖到各种情况）。

③ 每次执行完入队或出队操作后，打印队列中的全部元素。

④ 极端情况 （如满时入队、空时出队）发生时，打印提示信息。

#include <iostream>
    #include <random>
    using namespace std;
    
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1 //不可执行
    #define OVERFLOW -2
    
    
    
    typedef int QElemType;
    typedef int Status;
    
    #define MAXQSIZE 20 //最大队列长度
    
    typedef struct QNode {
        
    	QElemType* base;
    	int front;
    	int rear;
    }SqList;
    
    
    Status InitQueue(SqList& Q) {
        
    	Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
    	if (!Q.base)
    		exit(OVERFLOW);
    	Q.front = Q.rear = 0;
    	return OK;
    }
    
    
    /*插入元素e为Q的新的队尾元素*/
    Status EnQueue(SqList& Q, QElemType e) {
        
    	if ((Q.rear + 1) % MAXQSIZE == Q.front)
    		return ERROR;
    	Q.base[Q.rear] = e;
    	Q.rear = (Q.rear + 1) % MAXQSIZE;
    	return OK;
    }
    
    /*若队列不为空则删除Q的队头元素，用e返回其值，并返回ok；否则返回ERROR*/
    Status DeQueue(SqList& Q, QElemType& e) {
        
    	if (Q.front == Q.rear)
    		return ERROR;
    	e = Q.base[Q.front];
    	Q.front = (Q.front + 1) % MAXQSIZE;
    	return OK;
    }
    /*判断队列是否为空*/
    Status QueueEmpty(SqList Q) {
        
    	if (Q.front == Q.rear)
    		return TRUE;
    	else
    		return FALSE;
    }
    /*取出队头元素，不删除*/
    Status GetHead(SqList Q, QElemType& e) {
        
    	if (Q.front == Q.rear)
    		return ERROR;
    	e = Q.base[Q.front];
    	return OK;
    }
    int QueueLength(SqList Q) {
        
    	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
    }
    int main() {
        
    	SqList q;
    	InitQueue(q);
    	int e;
    	
    	int t = 0, s = 0;
    	int j = -1;
    	int c=1;
    	int dui = 1;
    	while (c)
    	{
        
    		cout << "               =================================" << endl;
    		cout << "               | 1.入队                        |" << endl;
    		cout << "               | 2.出队                        |" << endl;		
    		cout << "               | 0.退出                        |" << endl;
    		cout << "               =================================" << endl;
    		cout << "请输入你的选择：" << endl;
    		cin >> c;
    		switch (c)
    		{
        
    		case 1:
    			int a[10];
    			int b[100];
    			for (int i = 0; i < 10; i++) {
        
    				a[i] = rand() % 2;
    				cout << a[i] << "  ";
    			}
    			cout << endl;
    			
    			/*如果是0入队*/
    			for (int i = 0; i < 10; i++) {
        
    				t = t + 1;
    				if (a[i] == 0) {
        
    					s++;
    					if (s == 1) {
        
    						cout << "入队:";
    					}
    					j=j+1;
    					b[j] = t;
    					if (EnQueue(q, t)==ERROR) {
        
    						dui = 0;
    						cout << "满队列！！！";
    					}
    					
    				}
    			}
    			if (dui) {
        
    				for (int i = 0; i < QueueLength(q); i++) {
        
    					cout << b[i] << " ";
    				}
    			}
    			
    			cout << endl;
    			break;
    		case 2:
    			cout << "出队：";
    			if (QueueEmpty(q)) {
        
    				cout << "空队列!!!!";
    			}
    			while (!QueueEmpty(q))
    			{
        
    				DeQueue(q, e);
    				cout << e << " ";
    			}
    			cout << endl;
    			break;
    		case 0:
    			break;
    		
    		default:
    			break;
    		}
    
    	}
    	
    
    	return 0;
    }