?? 寫在最前：這篇文章將學習棧這種結構，以及該結構的一些基本操作的實現(xiàn)，包括順序存儲棧和鏈式存儲棧的基本操作的實現(xiàn)。
??：點求個關注，讓我們一起探索計算機的奧秘！
一、棧的定義
所謂的棧就是一種特殊的線性表，對于棧這種邏輯結構來說他和線性表最大的區(qū)別就是棧它刪除元素或者添加元素的話只能發(fā)生在表的一端，要么就是表尾部，要么就是表頭。
如上圖所顯示的那樣，這就是棧的結構，當然這是將棧這種邏輯結構使用順序存儲的方式表示出來了。
- 棧頂：這個特殊的線性表允許插入元素和刪除元素的一端
- 棧底：是固定的，不允許進行插入和刪除的一端
所以不難發(fā)現(xiàn)，由于棧的插入元素和刪除元素操作都只能發(fā)生在線性表的一端，對于這種結構來說，其元素的進出是遵循后進先出的
對于先進入的元素（元素進入稱為進棧），在取出的時候（元素被取出稱為出棧），也會是最先被取出的。
二、棧的基本操作
在定義完一個數(shù)據(jù)的邏輯結構就應該給出相應的基本操作，來操作這個邏輯結構，對于棧這種邏輯結構，是給出了以下幾種常用操作。
- 初始化操作
- 判斷棧是否為空
- 元素進棧
- 元素出棧
- 讀棧頂元素，但是不出棧
- 銷毀棧
三、棧不同的存儲結構的基本操作實現(xiàn)
在學習線性表時，也是學習了線性表這個邏輯結構在順序存儲下的基本操作的實現(xiàn)以及在鏈式存儲下的基本操作的實現(xiàn)，所以存儲結構不同，用代碼具體實現(xiàn)這些操作的步驟和思想也是不同的。
①棧的順序存儲
定義好棧的邏輯結構，對于棧這個邏輯結構使用順序存儲，這里使用靜態(tài)數(shù)組來實現(xiàn)順序存儲，定義如下結構。
#define maxsize 100
typedef int Element;
typedef struct {
Element data[maxsize]; //存放棧元素
int top; //棧頂指針（這里使用靜態(tài)數(shù)組，即使用下標指向棧頂）
}SqStack;
文件結構：
包含三個文件，一個SqStack.h文件用于定義數(shù)據(jù)結構和數(shù)據(jù)結構的基本操作，一個SqStack.cpp文件，該文件用于具體實現(xiàn)這些基本操作，一個test.cpp用于測試實現(xiàn)的函數(shù)是否正確。
初始化操作
SqStack.h的內容
#pragma once
#include<stdio.h>
#include<stdlib.h>
#define maxsize 100
typedef int Element;
typedef struct {
Element data[maxsize]; //存放棧元素
int top; //棧頂指針（這里使用靜態(tài)數(shù)組，即使用下標指向棧頂）
}SqStack;
// 初始化操作
bool InitStack(SqStack &SqS);
SqStack.cpp的內容
#include"SqStack.h"
// 初始化操作
bool InitStack(SqStack &SqS) {
SqS.top = -1; //將棧頂指向-1，為空
return true;
}
test.cpp的內容
#include"SqStack.h"
int main() {
SqStack SqS1;
//初始化棧
InitStack(SqS1);
printf("%d\n", SqS1.top);
return 0;
}
棧的判空操作
SqStack.h的內容
//棧的判空操作
bool IsStackEmpty(SqStack SqS);
SqStack.cpp的內容
// 判斷棧是否為空
bool IsStackEmpty(SqStack SqS)
{
if (SqS.top == -1) {
return true;
}
else {
return false;
}
}
test.cpp的內容
#include"SqStack.h"
int main() {
SqStack SqS1;
//初始化棧
InitStack(SqS1);
printf("%d\n", SqS1.top);
//棧判空
bool t = IsStackEmpty(SqS1);
if (t == true) {
printf("棧為空！\n");
}
return 0;
}
進棧
SqStack.h的內容
// 元素進棧
bool Push(Element e, SqStack &SqS);
//打印棧
void PrintStack(SqStack SqS);
SqStack.cpp的內容 （這里將打印棧的操作也寫在其中，沒有單獨寫這個打印操作）
// 元素進棧
bool Push(Element e, SqStack& SqS) {
if (SqS.top == maxsize-1) {
printf("棧滿，進棧失敗\n");
return false;
}
else {
SqS.top++;
SqS.data[SqS.top] = e;
return true;
}
}
//打印棧
void PrintStack(SqStack SqS) {
if (SqS.top == -1) {
printf("棧為空！");
}
else {
printf("打印順序：棧頂<----棧底\n");
for (int j = SqS.top; j >= 0; j--) {
printf("<--%d", SqS.data[j]);
}
}
}
test.cpp的內容
#include"SqStack.h"
int main() {
SqStack SqS1;
//初始化棧
InitStack(SqS1);
printf("%d\n", SqS1.top);
//棧判空
bool t = IsStackEmpty(SqS1);
if (t == true) {
printf("棧為空！\n");
}
//進棧
Push(2, SqS1);
Push(3, SqS1);
PrintStack(SqS1);
return 0;
}
出棧
SqStack.h的內容
// 元素出棧
Element Pop(SqStack &SqS);
SqStack.cpp的內容
// 元素出棧
Element Pop(SqStack &SqS) {
if (SqS.top == -1) {
printf("?？諏е鲁鰲Ｊn");
exit;
}
else {
Element ele = SqS.data[SqS.top];
SqS.top--;
return ele;
}
}
test.cpp的內容
#include"SqStack.h"
int main() {
SqStack SqS1;
//初始化棧
InitStack(SqS1);
printf("%d\n", SqS1.top);
//棧判空
bool t = IsStackEmpty(SqS1);
if (t == true) {
printf("棧為空！\n");
}
//進棧
Push(2, SqS1);
Push(3, SqS1);
PrintStack(SqS1);
Element tmp = Pop(SqS1);
printf("出棧元素為%d\n", tmp);
return 0;
}
讀棧頂元素
該操作與pop操作的區(qū)別是，這個只是讀出棧頂?shù)脑?，該元素并不出?！?/strong>SqStack.h的內容
// 讀棧頂元素，但是不出棧
Element GetTop(SqStack SqS);
SqStack.cpp的內容
// 讀棧頂元素，但是不出棧
Element GetTop(SqStack SqS) {
if (SqS.top == -1) {
printf("棧頂無元素\n");
return -1;
}
else {
Element tmp = SqS.data[SqS.top];
return tmp;
}
}
test.cpp的內容
#include"SqStack.h"
int main() {
SqStack SqS1;
//初始化棧
InitStack(SqS1);
printf("%d\n", SqS1.top);
//棧判空
bool t = IsStackEmpty(SqS1);
if (t == true) {
printf("棧為空！\n");
}
//進棧
Push(2, SqS1);
Push(3, SqS1);
PrintStack(SqS1);
Element tmp = Pop(SqS1);
printf("出棧元素為%d\n", tmp);
printf("棧頂元素為%d\n", GetTop(SqS1));
return 0;
}
銷毀棧
這里的銷毀棧，其實只需要將top的值至為-1就行，因為這個棧空間并不是由malloc函數(shù)開辟的，所以不需要free()函數(shù)來回收空間，在程序結束之后，會自動的回收空間。
②棧的鏈式存儲
棧的初始化
SqStack.h的內容
#include<stdlib.h>
typedef int ElementType;
typedef struct LinkStackNode {
ElementType data; //節(jié)點數(shù)據(jù)
struct LinkStackNode *next;
}LinkStackNode,*LinkStack;
//棧的初始化
int InitStack(LinkStack &LinkS);
SqStack.cpp的內容
#include"LinkStack.h"
//棧的初始化
int InitStack(LinkStack &LinkS) {
LinkS = (LinkStackNode*)malloc(sizeof(LinkStackNode)); //LinkS--->頭節(jié)點 申請了一個頭節(jié)點
// printf("%p", LinkS);
if (LinkS == NULL) {
printf("空間申請失敗導致初始化失敗\n");
return -1;
}
else {
LinkS->next = NULL; //頭節(jié)點的next指向空
return 1;
}
}
test.cpp的內容
#include"LinkStack.h"
int main() {
LinkStack l1;
if (InitStack(l1)) {
printf("初始化成功\n");
}
return 0;
}
棧的判空操作
SqStack.h的內容
//棧的判空操作
bool IsStackEmpty(LinkStack Links);
SqStack.cpp的內容
//棧的判空操作
bool IsStackEmpty(LinkStack Links) {
if (Links->next == NULL) {//頭節(jié)點的next為空，就其頭節(jié)點后無元素
return true;
}
else {
return false;
}
}
test.cpp的內容
#include"LinkStack.h"
int main() {
LinkStack l1;
if (InitStack(l1)) {
printf("初始化成功\n");
}
if (IsStackEmpty(l1)) {
printf("棧為空\n");
}
return 0;
}
進棧
在這一部分將打印棧的操作也寫在這一部分了SqStack.h的內容
//進棧
bool Push(LinkStack Links, ElementType e);
//打印棧
void PrintStack(LinkStack Links);
SqStack.cpp的內容
//進棧
bool Push(LinkStack Links, ElementType e) {
LinkStackNode* node = (LinkStackNode*)malloc(sizeof(LinkStackNode));
if (node == NULL) {
printf("空間申請失敗導致進棧失敗\n");
return false;
}
else {
node->next = Links->next;
Links->next = node;
node->data = e;
return true;
}
}
//打印棧
void PrintStack(LinkStack Links) {
if (Links == NULL) {
printf("無效的棧，無法打印\n");
return;
}
if (Links->next == NULL) {
printf("棧為空！");
return;
}
else {
printf("打印順序：棧頂<----棧底\n");
LinkStackNode* tmp = NULL;
for (tmp = Links->next; tmp != NULL; tmp = tmp->next) {
printf("<--%d", tmp->data);
}
printf("\n");
}
}
test.cpp的內容
#include"LinkStack.h"
int main() {
LinkStack l1;
if (InitStack(l1)) {
printf("初始化成功\n");
}
if (IsStackEmpty(l1)) {
printf("棧為空\n");
}
Push(l1, 3);
Push(l1, 4);
PrintStack(l1);
return 0;
}
出棧
SqStack.h的內容
//出棧
ElementType Pop(LinkStack Links);
SqStack.cpp的內容
//出棧
ElementType Pop(LinkStack Links) {
if (Links->next == NULL) {
printf("棧為空\n");
return -1;
}
else {
ElementType datatmp = Links->next->data;
LinkStackNode* tmp = Links->next;
Links->next = Links->next->next;
free(tmp);
return datatmp;
}
}
test.cpp的內容
#include"LinkStack.h"
int main() {
LinkStack l1;
if (InitStack(l1)) {
printf("初始化成功\n");
}
if (IsStackEmpty(l1)) {
printf("棧為空\n");
}
Push(l1, 3);
Push(l1, 4);
PrintStack(l1);
Push(l1, 7);
printf("此時pop的元素為%d\n", Pop(l1));
return 0;
}
讀棧頂元素
SqStack.h的內容
//讀棧頂元素
ElementType GetEle(LinkStack Links);
SqStack.cpp的內容
//讀棧頂元素
ElementType GetEle(LinkStack Links) {
if (Links->next == NULL) {
printf("此時棧頂為空\n");
return -1;
}
else {
ElementType tmp = Links->next->data;
return tmp;
}
}
test.cpp的內容
#include"LinkStack.h"
int main() {
LinkStack l1;
if (InitStack(l1)) {
printf("初始化成功\n");
}
if (IsStackEmpty(l1)) {
printf("棧為空\n");
}
Push(l1, 3);
Push(l1, 4);
PrintStack(l1);
Push(l1, 7);
printf("此時pop的元素為%d\n", Pop(l1));
printf("此時棧頂?shù)脑貫?d\n", GetEle(l1));
return 0;
}
銷毀棧
SqStack.h的內容
//銷毀棧
void DestoryStack(LinkStack &links);
SqStack.cpp的內容
//銷毀棧
void DestoryStack(LinkStack &links) {
LinkStackNode* tmp = links->next;
while (tmp != NULL){
LinkStackNode* t = tmp;
tmp = tmp->next;
free(t);
}
free(links); //free掉頭節(jié)點
links = NULL;
}
test.cpp的內容文章來源：http://www.zghlxwxcb.cn/news/detail-852097.html
#include"LinkStack.h"
int main() {
LinkStack l1 = NULL;
if (InitStack(l1)) {
printf("初始化成功\n");
}
if (IsStackEmpty(l1)) {
printf("棧為空\n");
}
Push(l1, 3);
Push(l1, 4);
PrintStack(l1);
Push(l1, 7);
printf("此時pop的元素為%d\n", Pop(l1));
printf("此時棧頂?shù)脑貫?d\n", GetEle(l1));
DestoryStack(l1);
PrintStack(l1);
return 0;
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-852097.html
到了這里，關于數(shù)據(jù)結構 第四章 棧的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
