基本概念及相關(guān)術(shù)語：
棧是只允許在一端進(jìn)行插入和刪除操作的線性表。
由此可見，棧也是線性表的一種，只是棧的操作受限制的線性表。
棧頂（top）：線性表允許插入和刪除的那一段。值得注意的是，棧頂指針top的指向是有些兩種方式的，一種是指向棧頂當(dāng)前元素，一種是指向棧頂?shù)南乱晃恢?。兩種指向方式對棧的操作影響不大，只是在判斷棧頂位置的時(shí)候略有差異，本文以指向當(dāng)前棧頂元素為例。另一種指向方式讀者可以自行實(shí)踐。
棧底（bottom）：固定的，不允許進(jìn)行插入和刪除的另一端。
空棧：不含有任何元素的空表。
棧的存儲方式：
棧有兩種基本存儲方式:
- 順序存儲：利用一段連續(xù)的內(nèi)存空間進(jìn)行存儲。
- 鏈?zhǔn)酱鎯Γ豪梅沁B續(xù)的內(nèi)存空間存儲，元素之間使用指針進(jìn)行鏈接。（通常單鏈表實(shí)現(xiàn)，棧頂是表頭，棧底的表尾）
鏈棧的優(yōu)點(diǎn)：
- 便于多個(gè)棧共享存儲空間，提高空間效率；
- 不存在棧滿上溢的情況
棧的特性：
先進(jìn)后出
棧的基本操作--順序存儲：
棧的基本操作大致包括6個(gè)：
- InitStack(&s):初始化一個(gè)空棧；
- StackEmpty(s):判斷一個(gè)在棧是否為空；
- Push(&s,x):入棧，若棧S未滿，這將x加入棧，使之稱為棧頂；
- Pop(&s):出棧，若棧S非空，則彈出棧頂元素；
- GetTop(s,x):讀棧頂元素；
- DestroyStack(&s):銷毀棧，釋放棧S所占用內(nèi)存空間；
1.InitStack(&s):初始化一個(gè)空棧：
創(chuàng)建一個(gè)空棧后，將棧頂指針指向-1；
void stackinit(sq& s)
{
s.top = -1;
}2.StackEmpty(s):判斷一個(gè)在棧是否為空：
bool stackempty(sq s)
{
if (s.top == -1) return true; //為空返回true
else return false; //不為空返回false
}3.Push(&s,x):入棧，若棧S未滿，這將x加入棧，使之稱為棧頂：
bool push(sq& s, int x)
{
if (s.top == maxsize - 1) return false; //如果?？臻g滿，則不能再插入元素，否則導(dǎo)致內(nèi)存溢出，直接返回false；
s.data[++s.top] = x; //棧不滿，則可以插入元素，將棧頂指針上移，再將需要插入的元素賦值給棧頂
return true;
}4.Pop(&s):出棧，若棧S非空，則彈出棧頂元素：
void pop(sq& s)
{
if (s.top == -1) cout << "?？?<<endl; //棧為空，則不能出棧。
s.top--; //棧不空，能出棧，棧頂指針下移
}5.GetTop(s,x):讀棧頂元素：
int gettop(sq s)
{
int x; //接收棧頂元素
if (s.top == -1) return -1; //?？眨瑹o法讀取元素
x = s.data[s.top]; //棧不空，將當(dāng)前棧頂元素賦值給x
return x; //返回x的值，即讀取x的值
}6.DestroyStack(&s):銷毀棧，釋放棧S所占用內(nèi)存空間：
void destorystack(sq &s) {
if (s.top!=-1) free(s.data); //若棧不空，釋放棧所占用的內(nèi)存空間
s.top = -1;
}整體代碼：
#include<iostream>
using namespace std;
#define maxsize 10
typedef struct {
int data[maxsize];
int top;
}sq;
void stackinit(sq& s)
{
s.top = -1;
}
bool stackempty(sq s)
{
if (s.top == -1) return true;
else return false;
}
bool push(sq& s, int x)
{
if (s.top == maxsize - 1) return false;
s.data[++s.top] = x;
return true;
}
void pop(sq& s)
{
if (s.top == -1) cout << "?？?<<endl;
s.top--;
}
int gettop(sq s)
{
int x;
if (s.top == -1) return -1;
x = s.data[s.top];
return x;
}
void destorystack(sq &s) {
if (s.top!=-1) free(s.data);
s.top = -1;
}
int main() {
sq s1;
stackinit(s1);
for (int i = 0; i < 10; i++)
{
push(s1, i);
}
while (!stackempty(s1))
{
cout << gettop(s1)<< " ";
s1.top--;
}
cout << endl;
for (int i = 0; i < 10; i++)
{
push(s1, i);
}
pop(s1);
while (!stackempty(s1))
{
cout << gettop(s1) << " ";
s1.top--;
}
destorystack(s1);
return 0;
}執(zhí)行結(jié)果：
鏈表的基本操作--鏈?zhǔn)酱鎯?/span>
鏈?zhǔn)酱鎯褪菍︽湵淼牟僮?，在這里可以設(shè)置頭節(jié)點(diǎn)也可以不設(shè)置頭節(jié)點(diǎn)。
我這里以單鏈表有頭結(jié)點(diǎn)的頭插法為例。
鏈棧的節(jié)點(diǎn)定義：
typedef struct Linknode {
int data;
struct Linknode* next;
};1.InitStack(*head):初始化一個(gè)空棧：
void initlink(Linknode *head) {
if (head == nullptr) cout << "分配失敗" << endl;
else head->next = nullptr;
}2.StackEmpty(*head):判斷一個(gè)在棧是否為空：
bool isempty(Linknode* head) {
if (head->next == nullptr) return true;
else return false;
}3.Push(*head,x):入棧:
void enqueue(Linknode* head,int x) {
Linknode* L = new Linknode[sizeof(Linknode)];
L->data = x;
L->next = head->next;
head->next = L;
}4.Pop(*head):出棧:
void dequeue(Linknode* head)
{
Linknode* L = new Linknode[sizeof(Linknode)];
L = head->next;
head->next = L->next;
delete[] L;
}5.GetTop(s,x):讀棧頂元素：
void gethead(Linknode* head)
{
int x;
x = head->next->data;
cout << x << endl;
}6.DestroyStack(&s):銷毀棧:
void DestroyStack(Linknode* head) {
Linknode* p = new Linknode[sizeof(Linknode)];
p = head->next;
if (!isempty(head)) {
while (head->next != nullptr)
{
head->next = p->next;
delete[]p;
p = head->next;
}
}
delete[]p;
}整體代碼：
#include<iostream>
using namespace std;
typedef struct Linknode {
int data;
struct Linknode* next;
};
void initlink(Linknode *head) {
//head = new Linknode[sizeof(Linknode)];
if (head == nullptr) cout << "分配失敗" << endl;
else head->next = nullptr;
}
bool isempty(Linknode* head) {
if (head->next == nullptr) return true;
else return false;
}
void enqueue(Linknode* head,int x) {
Linknode* L = new Linknode[sizeof(Linknode)];
L->data = x;
L->next = head->next;
head->next = L;
}
void dequeue(Linknode* head)
{
Linknode* L = new Linknode[sizeof(Linknode)];
L = head->next;
head->next = L->next;
delete[] L;
}
void gethead(Linknode* head)
{
int x;
x = head->next->data;
cout << x << endl;
}
void DestroyStack(Linknode* head) {
Linknode* p = new Linknode[sizeof(Linknode)];
p = head->next;
if (!isempty(head)) {
while (head->next != nullptr)
{
head->next = p->next;
delete[]p;
p = head->next;
}
}
delete[]p;
}
int main() {
Linknode* h = new Linknode[sizeof(Linknode)];
initlink(h);
if (isempty(h)) cout << "鏈表空" << endl;
for (int i = 0; i < 10; i++)
{
enqueue(h, i);
}
gethead(h);
dequeue(h);
gethead(h);
DestroyStack(h);
return 0;
}執(zhí)行結(jié)果：文章來源：http://www.zghlxwxcb.cn/news/detail-713158.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-713158.html
到了這里，關(guān)于棧的概念及其基本操作--詳細(xì)（C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
