栈与队列基本操作及其应用
生活随笔
收集整理的這篇文章主要介紹了
栈与队列基本操作及其应用
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
文章目錄
- 一、棧
- 棧的實現(xiàn)
- 順序棧
- 棧的應(yīng)用
- 1.數(shù)制轉(zhuǎn)換(十進制轉(zhuǎn)換為R進制)
- 2.括號匹配的檢驗
- 二、隊列
- 隊列的實現(xiàn)
- 1.隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)
- 2.循環(huán)隊列-隊列的順序表示和實現(xiàn)
- 隊列的應(yīng)用
- 1.用循環(huán)隊列模擬銀行窗口排隊
一、棧
棧的實現(xiàn)
順序棧
#include <iostream> using namespace std;#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 //不可執(zhí)行 #define OVERFLOW -2#define STACK_INIT_SIZE 100 //存儲空間初始分配量 #define STACKINCREMENT 10 //存儲空間分配增量typedef int SElemType; typedef int Status;//存儲結(jié)構(gòu) typedef struct {SElemType* base; //棧構(gòu)造之前和銷毀之后，值都為NULLSElemType* top; //棧頂指針int stacksize; //當(dāng)前已分配的存儲空間，以元素為單位 }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;elsereturn 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; }棧的應(yīng)用
1.數(shù)制轉(zhuǎn)換(十進制轉(zhuǎn)換為R進制)
將十進制數(shù)N轉(zhuǎn)換為R進制數(shù)
#include <iostream> using namespace std;#define OK 1 #define ERROR 0 #define INFEASIBLE -1 //不可執(zhí)行 #define OVERFLOW -2#define STACK_INIT_SIZE 100 //存儲空間初始分配量 #define STACKINCREMENT 10 //存儲空間分配增量typedef int SElemType; typedef int Status;//存儲結(jié)構(gòu) typedef struct {SElemType* base; //棧構(gòu)造之前和銷毀之后，值都為NULLSElemType* top; //棧頂指針int stacksize; //當(dāng)前已分配的存儲空間，以元素為單位 }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;} } /*十進制轉(zhuǎn)換為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; //棧當(dāng)前的存儲空間 }; /*初始化*/ 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;elsereturn 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 << "括號匹配成功";elsecout << "缺少右括號！";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 << "括號匹配成功";elsecout << "缺少右括號！";cout << endl;}int main() {SqStack s;//初始化空棧InitStack(s);char ch[100];cout << "輸一個含義有()[]{}的括號表達式:\n";// gets(ch);cin >> ch;Parentheses_match(s,ch);return 0; }二、隊列
隊列的實現(xiàn)
1.隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)
#include <iostream> using namespace std;#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 //不可執(zhí)行 #define OVERFLOW -2#define STACK_INIT_SIZE 100 //存儲空間初始分配量 #define STACKINCREMENT 10 //存儲空間分配增量typedef int QElemType; typedef int Status;/*--------單鏈隊列-隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)--------*/ /*線性表的單鏈表的存儲結(jié)構(gòu)*/ 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;elsereturn 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.循環(huán)隊列-隊列的順序表示和實現(xiàn)
#include <iostream> using namespace std;#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 //不可執(zhí)行 #define OVERFLOW -2#define STACK_INIT_SIZE 100 //存儲空間初始分配量 #define STACKINCREMENT 10 //存儲空間分配增量typedef int QElemType; typedef int Status;#define MAXQSIZE 100 //最大隊列長度/*--------單鏈隊列-隊列的順序存儲結(jié)構(gòu)--------*/ /*線性表的單鏈表的存儲結(jié)構(gòu)*/ 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;elsereturn 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; }隊列的應(yīng)用
1.用循環(huán)隊列模擬銀行窗口排隊
具體要求如下：
① 用整數(shù)代表排隊客戶的編號。
② 入隊和出隊的調(diào)用序列可直接寫在代碼中 （但要足夠多以覆蓋到各種情況）。
③ 每次執(zhí)行完入隊或出隊操作后，打印隊列中的全部元素。
④ 極端情況 （如滿時入隊、空時出隊）發(fā)生時，打印提示信息。
#include <iostream> #include <random> using namespace std;#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 //不可執(zhí)行 #define OVERFLOW -2typedef 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;elsereturn 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; }總結(jié)
以上是生活随笔為你收集整理的栈与队列基本操作及其应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
